크루스칼(Kruskal) 알고리즘 2, Union-Find를 이용한 크루스칼

---

크루스칼(Kruskal) 알고리즘 1, 최소비용신장트리 / Union-Find 원리

​

1. 크루스칼(Kruskal) 알고리즘 절차

1. 엣지를 오름차순으로 정렬

2. 각 노드 마다의 루트 부모 노드를 자기 자신으로 할당

3. 오름차순으로 한 엣지로 연결되어 있는 두 노드의 최상위 부모 노드가 다른 두 노드를 찾아 냄(find 연산)

4. 최소 비용 값을 알기 위해서 엣지의 값을 더함

5. 두 노드의 최상위 부모 노드가 다르다면 더 작은 값을 다른 노드의 부모로 할당(union 연산)

6. 3번 ~ 5번 과정을 엣지 갯수만큼 반복

​

​

1. 엣지를 비용이 적은 값부터 오름차순으로 정렬 합니다.

​

​

2. 연결되어 있는 엣지들이 아직 없으므로 각 노드 마다의 최상위 부모 노드를 자기 자신으로 할당

 

 

3. 엣지들의 오름차순으로 엣지 값이 11인 노드 5와 2의 최상위 부모 노드를 찾고(find 연산) 더 작은 값인 노드 2를 노드 5의 최상위 부모 노드로 할당합니다.(union 연산) 이것으로 엣지 11은 노드 5와 2의 정상적으로 연결 되었습니다.

​

4. 그 다음 엣지인 12의 노드 1과 4의 최상위 부모 노드인 1과 4를 찾고(find 연산) 더 작은 값인 1을 노드 4의 최상위 부모 노드로 할당합니다.(union 연산) 이것으로 엣지 12는 노드 1과 4의 정상적으로 연결되었습니다.

​

​

5. 그 다음 엣지 25의 노드 3와 6의 최상위 부모 노드를 찾고(find 연산) 더 작은 값인 3 노드를 노드 6의 루트 부모 노드로 할당합니다.(union 연산) 엣지 25가 연결되었습니다.

​

6. 그 다음 엣지인 27의 노드 1과 5의 최상위 부모 노드인 1과 2를 찾고(find 연산) 더 작은 값인 1을 노드 5의 최상위 부모 노드로 할당합니다.(union 연산) 엣지 27이 연결되었습니다. 따라서 노드 5와 연결되어 있던 노드 2의 최상위 부모 노드도 노드 1로 변경합니다.

​

​

7. 그 다음 엣지 31의 노드 7과 5의 최상위 부모 노드를 찾고(find 연산) 더 작은 값인 1 노드를 노드 7의 최상위 부모 노드로 할당합니다.(union 연산) 엣지 31이 연결 되었습니다.

​

8. 그 다음 엣지인 34의 노드 2과 4의 최상위 부모 노드인 1과 1를 찾습니다.(find 연산) 하지만, 노드 2와 4는 최상위 부모가 1로 같습니다. 따라서 엣지 34를 연결해주면 노드 2에서 노드 5로 가는 경로가 1개 이상이 됩니다. 이를 싸이클(cycle)이 발생 했다고 합니다. 따라서 엣지 34는 연결 하지 않습니다.

​

​

 

9. 그 다음 엣지 42의 노드 5와 6의 최상위 부모 노드1과 3을 찾고(find 연산) 더 작은 값인 1을 노드 6의 최상위 부모 노드로 할당 합니다.(union 연산) 엣지 42가 연결 되었습니다. 엣지 42가 연결되어 노드 3의 최상위​ 부모 노드도 1로 할당됩니다.

​

10. 그 다음 엣지인 44의 노드 1과 2의 최상위 부모 노드인 1과 1를 찾습니다.(find 연산) 하지만, 1로 같습니다. 따라서 엣지 34를 연결 해주면 싸이클(cycle)이 발생 합니다. 따라서 엣지 44는 연결 하지 않습니다.

​

​

11. 그 다음 엣지 56의 노드 1과 7의 최상위 부모 노드1과 1을 찾습니다.(find 연산). 하지만, 1로 같습니다.따라서 싸이클(cycle)이 형성되므로 엣지 56은 연결하지 않습니다.

​

12. 그 다음 엣지 58의 노드 4과 7의 최상위 부모 노드1과 1을 찾습니다.(find 연산). 하지만, 1로 같습니다. 따라서 싸이클(cycle)이 형성되므로 엣지 58은 연결하지 않습니다.

​

​

13. 그 다음 엣지 60의 노드 3과 5의 최상위 부모 노드1과 1을 찾습니다.(find 연산). 하지만, 1로 같습니다.따라서 싸이클이 형성되므로 엣지 60은 연결하지 않습니다.

​

​

14. 이렇게 해서 연결된 엣지는 위와 같습니다. 위와 같이 크루스칼 알고리즘(Kruskal)으로 얻어진 트리를 '최소 비용 신장 트리(Minimum Spanning Tree)'라고 합니다. 언뜻 보기에는 트리 모습 같지 않지만 오른쪽 그림 처럼 정리를 해주면, 트리의 모습과 같습니다.

​

​

2. Union-Find JAVA 소스

public class UnionFind {

    int getParent(int parent[], int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }

    void unionParent(int parent[], int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);
        if(a < b)
            parent[b] = a;
        else
            parent[a] = b;
    }

    boolean findParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);
        if(a == b)
            return true;
        else
            return false;
    }

    public static void main(String[] args) {
        int parent[] = new int[11];
        for(int i = 1; i <= 10; i++){
            parent[i] = i;
        }

        UnionFind unionFind = new UnionFind();
        unionFind.unionParent(parent, 1, 2);
        unionFind.unionParent(parent, 2, 3);
        unionFind.unionParent(parent, 3, 4);

        unionFind.unionParent(parent, 5, 6);
        unionFind.unionParent(parent, 6, 7);
        unionFind.unionParent(parent, 7, 8);

        System.out.printf("1과 5는 연결되어 있나요? %b", unionFind.findParent(parent, 1, 5));
        System.out.println();

        unionFind.unionParent(parent, 1, 5);
        System.out.printf("1과 5는 연결되어 있나요? %b", unionFind.findParent(parent, 1, 5));
        System.out.println();
    }
}

 

​

3. 크루스칼(Kruskal) 알고리즘 JAVA 소스

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Kruskal {

    public static void main(String[] args) {
        int n = 7;

        List<Edge> list = new ArrayList<>();
        list.add(new Edge(1, 2, 44));
        list.add(new Edge(1, 4, 12));
        list.add(new Edge(1, 5, 27));
        list.add(new Edge(1, 7, 56));
        list.add(new Edge(2, 4, 34));
        list.add(new Edge(2, 5, 11));
        list.add(new Edge(3, 5, 60));
        list.add(new Edge(3, 6, 25));
        list.add(new Edge(4, 7, 58));
        list.add(new Edge(5, 6, 42));
        list.add(new Edge(5, 7, 31));

        // 간선의 비용을 오름차순 정렬
        Collections.sort(list);

        // 각 정점이 포함된 그래프가 어디인지 저장
        int rootParents[] = new int[n];
        for (int i = 0; i < n; i++) {
            rootParents[i] = i;
        }

        // 거리의 합을 0으로 초기화
        int sum = 0;
        UnionFind uf = new UnionFind();

        for (int i = 0; i < list.size(); i++) {
            // 동일한 부모를 가르키지 않는 경우,
            // 즉 사이클이 발생하지 않을 때만 선택
            if (!uf.findParent(rootParents, list.get(i).node[0] - 1, list.get(i).node[1] - 1)) {
                sum += list.get(i).distance;
                uf.unionParent(rootParents, list.get(i).node[0] - 1, list.get(i).node[1] - 1);
            }
        }

        System.out.printf("간선의 총합 : %d", sum);
        System.out.println();
    }
}

class Edge implements Comparable<Edge> {
    int[] node;
    int distance;

    Edge(int a, int b, int distance) {
        this.node = new int[2];
        this.node[0] = a;
        this.node[1] = b;
        this.distance = distance;
    }

    @Override
    public int compareTo(Edge edge) {
        return (this.distance - edge.distance);
    }
}