[Algorithm] Kruskal's Algorithm (크루스칼 알고리즘)

1. Kruskal's Algorithm

 

크루스칼 알고리즘은 edge를 그리디하게 선택하여 MST를 구성하는 알고리즘이다.

edge를 가중치 기준으로 오름차순으로 정렬한 후 가장 작은 edge부터 순서대로 subtree에 추가하여 MST를 구성한다. 이때 해당 edge가 cycle을 이루는지 확인을 해야하는데, 이때 union-find 알고리즘은 사용하는데, 각 정점에 index를 주어서 정점들이 연결될 때마다 해당 그룹의 정점들이 모두 같은 index를 가지도록 하여 이를 비교하여 같은 index를 가지는 경우 cycle로 인식한다.

 

 

2. 크루스칼 알고리즘 구현

 

1) 그래프의 간선을 오름차순으로 정렬한다.

2) 가장 작은 간선을 선택하여 cycle을 그리는지 확인한다.

3) cycle을 그리는 경우는 다음 간선을 선택하고 그렇지 않는 경우 spanning tree에 해당 edge를 추가한다.

4) cycle확인을 위해 index를 일치시키는 union 작업을 수행한다.

5) V-1개의 간선을 추가할 때까지 2) ~ 4) 을 반복한다.

 

    // union-find 알고리즘을 통해 해당 그룹의 index 찾기
    public int find(int v) {
        if(visited[v] == v) return v;
        return find(visited[v]);
    }

    private void kruskal() {
        // Edge를 priority queue를 사용하여 오름차순으로 정렬
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < i; j++) {
                graph[i][j] = -1;
            }
            for(int j = i + 1; j < N; j++) {
                pq.add(new Edge(i, j, graph[i][j]));
                graph[i][j] = -1;
            }
        }

        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            int v1 = edge.v1, v2 = edge.v2;
            int p1 = find(v1), p2 = find(v2);   // 각 정점 그룹의 index를 찾아서 cycle 여부를 판단한다.
            if(p1 == p2)
                continue;
            visited[p1] = p2; // 한 그룹으로 연결된 정점들의 index를 하나로 통일한다. 
            graph[v1][v2] = graph[v2][v1] = edge.weight;
            weight += edge.weight;
        }
    }

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Graph/Kruskal/Kruskal.java

 

 

3) 시간 복잡도

 

시간 복잡도는 O(E log E) 또는 O(E log V)가 된다.

처음 간선의 정렬에 O(E log E)의 시간 복잡도가 걸리고, 모든 간선에 대해 unionfind를 수행하는데 E * log V가 걸리기 때문에 이를 더하면 O(E log E) + O(E log V)가 된다. 이때 E는 최대 V²이 될 수 있는데, 결국 O(log V)와 O(log E)는 같게 되기때문에 최종 시간 복잡도는 O(E log E) 또는 O(E log V)가 된다.

 

 

[reference]

- https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks