[알고리즘] Kruskal 알고리즘

오늘은 최소 신장 트리를 만드는 알고리즘 중 Kruskal 알고리즘에 대해서 알아보겠습니다.

 

---

Kruskal 알고리즘이란?

Kruskal 알고리즘은 MST(최소 신장 트리)를 만드는 알고리즘 중 하나입니다.

이 알고리즘은 그리디 알고리즘을 이용하여 구현합니다.

 

각 간선마다의 weight를 고려하여 매순간 최소의 weight를 선택합니다. 그 후, 선택한 간선을 넣었을 때 사이클이 생긴다면 해당 간선을 버리는 방식으로 진행됩니다.

 

아래의 예시를 통해서 조금 더 자세히 알아봅시다.

이전에 MST를 다룬 글에서 예시로 들었던 그래프를 사용해보겠습니다.

 

그림 1

각 간선마다 이러한 가중치를 가지는 그래프가 있다고 해봅시다.

 

우리는 우선, 각 가중치 순으로 정렬하여 우측에 정리해보겠습니다.

 

자, 이제 우리는 가장 작은 가중치대로 선택해가면서 싸이클을 만드는지만 확인하고 그렇지 않으면 MST의 한 간선으로 잡아줍시다.

 

(4, 6)이 가장 먼저 선택되고 첫 간선이므로 바로 채택되겠네요.

 

 

이제 (1, 6)을 이어줍시다. 싸이클이 생기지 않으니 괜찮습니다. (3, 5)까지 한번에 진행해줍시다.

 

 

 

이제 (1, 4)를 할 차례네요. 하지만 (1, 4)를 추가하게 되면 싸이클이 아래처럼 생기게 됩니다.

 

 

따라서, (1, 4) 는 버려주고 다음 (2, 5)를 진행합니다.

 

이러한 식으로 계속 반복하게 되면 아래와 같은 MST가 생성됩니다.

 

 

이전 글에서 확인했던 MST의 모양과 똑같네요!!

 

 

MST의 구현

그럼 이제 MST를 코드로 구현해보겠습니다.

 

우선, 간선이 가중치를 가지고 있다는 점에서 기존과 다르므로 Edge 클래스를 아래와 같이 정의합니다.

public class Edge {
    int vertex, adjVertex; // 간선의 양 끝 점
    int weight;	// 간선의 가중치

    public Edge(int vertex, int adjVertex, int weight) {
        this.vertex = vertex;
        this.adjVertex = adjVertex;
        this.weight = weight;
    }
}

 

 

또한, Kruskal 알고리즘을 이해하기 위해서 우리는 Union Find라는 개념을 알아야합니다.

Union-Find는 이전 글에서 다루었으므로 자세한 설명은 생략합니다.

 

Union-Find의 코드 또한 그대로 사용하므로, 이전 글을 참고해주시면 감사하겠습니다.

 

 

이제 Kruskal의 코드를 확인해봅시다.

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class KruskalMST {
    int N, M;
    List<Edge>[] graph;
    UnionFind uf;
    Edge[] tree;

    static class Weight_Comparison implements Comparator<Edge>{

        @Override
        public int compare(Edge e, Edge f) {
            if(e.weight > f.weight) return 1;
            else if(e.weight < f.weight) return -1;
            else return 0;
        }
    }

    public KruskalMST(List<Edge>[] adjList, int numOfEdges){
        N = adjList.length;
        M = numOfEdges;
        graph = adjList;
        uf = new UnionFind(N);
        tree = new Edge[N-1];
    }

    public Edge[] mst(){
        Weight_Comparison BY_WEIGHT = new Weight_Comparison();

        PriorityQueue<Edge> pq = new PriorityQueue<>(M, BY_WEIGHT);

        for(int i=0; i<N; i++){
            for (Edge e : graph[i]) {
                pq.add(e);
            }
        }

        int count = 0;
        while(!pq.isEmpty() && count < N-1){
            Edge e = pq.poll();
            int u = e.vertex;
            int v = e.adjVertex;
            if(!uf.isConnected(u, v)){
                uf.union(u, v);
                tree[count++] = e;
            }
        }

        return tree;
    }
}

 

이 알고리즘에서는, 가장 짧은 간선의 weight를 가져오기 위해 우선순위 큐라는 것을 이용했습니다.

우선순위 큐는 큐에 들어간 데이터 중 우선순위가 가장 높은 것부터 나오게하는 자료구조입니다.

 

따라서, compare를 override하여 이용했음을 기억합시다.

 

 

mst() 메서드에서 주의깊게 봐야할 것은 uf.isConnected(u, v)입니다.

만약 uf.isConnected(u, v)가 true라면 이 두 정점은 같은 최상위 노드를 갖습니다. 즉, 사이클을 만들게 됩니다.

 

사이클을 만들 때, 해당 정점에서 최상위 노드가 같다는 것을 꼭 기억해야합니다.

 

 

이러한 부분을 제외하면 어려운 부분이 없으므로 간단히 넘어갑시다.

 

만약 우리가 그림 1과 같은 트리를 기준으로 Kruskal 알고리즘을 진행하여 결과를 얻는다면 아래와 같은 결과를 얻을 수 있습니다.

 

 

해당 간선만을 살려놓으면 아래와 같습니다.

 

저희가 직접 그려본 것과 같네요!! 

 

 

 

Kruskal 알고리즘의 수행 시간

Kruskal 알고리즘에서 가장 시간이 많이 소요되는 작업은 간선의 가중치를 정렬하는 것입니다. 앞선 글에서 다루지는 않았지만, 정렬에 있어 사용되는 알고리즘의 시간복잡도는 O(mlogm)입니다.

 

따라서 해당 알고리즘의 시간 복잡도는 O(m log m)이고, m은 간선의 개수를 의미합니다.

---

오늘은 MST를 찾는 알고리즘 중 Kruskal 알고리즘을 알아봤습니다. 이 외에도 Prim, Sollin이 있는데요, 다음에는 Prim에 대해서 알아봅시다. 감사합니다.