[알고리즘] 최소 신장 트리

최소 신장 트리

 

• Minimum Spanning Tree (MST)
• 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법

 

 

 

1. 크루스칼 (Kruskal)

• 간선 중 최솟값을 가진 간선부터 연결한다 (간선들 정렬하고 시작)
• 사이클이 발생하면 다른 간선을 선택한다
• 간선 수가 적을 때 사용
• 알고리즘 복잡도 : O(간선 수 * log(간선 수))

static int parents[];
public int kruskal(int[][] data, int v, int e) {
    int weightSum = 0;
    
    // 간선 가중치 오름차순 정렬
    Arrays.sort(data, (x, y) -> (x[2] - y[2]));

    // union-find 배열 초기화
    parents = new int[v + 1];
    for (int i = 1; i < v; i++) {
        parents[i] = i;
    }
    
    for (int i = 0; i < e; i++) {
        // 사이클 발생하지 않으면 연결하고 weight 업데이트
        if (find(data[i][0]) != find(data[i][1])) {
            union(data[i][0], data[i][1]);
            weightSum += data[i][2];
        }
    }
    
    return weightSum;
}

public void union(int a, int b) {
    int aP = find(a);
    int bP = find(b);
    
    if (aP != bP) {
        parents[aP] = bP;
    }
}

public static int find(int a) {
    // 부모가 자기 자신이면 그냥 return
    if (a == parents[a]) {
        return a;
    }
    // 자기 자신이 아니라면 parents 타고타고 들어가기
    return parents[a] = find(parents[a]);
}

 

 

2. 프림 (Prim)

• 임의의 노드에서 시작
• 연결된 노드들의 간선 중 낮은 가중치를 갖는 갖는 간선을 선택한다
• 간선 수가 많을 때 사용
• 알고리즘 복잡도 : O(간선 수 * log(노드 수))

class Node {
    int to;
    int weight;

    public Node(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public int prim(int[][] data, int v, int e) {
    int weightSum = 0;

    // 그래프 구성
    ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    for (int i = 0; i < v + 1; i++) {
        graph.add(new ArrayList<>());
    }

    for (int i = 0; i < e; i++) {
        graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        graph.get(data[i][1]).add(new Node(data[i][0], data[i][2])); 
    }

    boolean[] visited = new boolean[v + 1];
    PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
    pq.offer(new Node(1, 0));

    int cnt = 0;
    while (!pq.isEmpty()) {
        Node cur = pq.poll();
        cnt += 1;

        // 방문한적 있는 노드면 continue
        if (visited[cur.to]) {
            continue;
        }
        visited[cur.to] = true;
        weightSum += cur.weight;

        // 모든 노드 다 연결했으면 return
        if (cnt == v) {
            return weightSum;
        }

        // 연결된 노드들 중 방문하지 않은 노드 찾기
        for (int i = 0; i < graph.get(cur.to).size(); i++) {
            Node adjNode = graph.get(cur.to).get(i);
            if (visited[adjNode.to]) { // 방문했으면 continue
                continue;
            }
            pq.offer(adjNode);
        }
    }
    return weightSum;
}