최소신장트리(Minimum Spanning Tree)-크러스컬(Kruskal) 알고리즘

최소신장트리를 생성하기위한 알고리즘으로 크러스컬 알고리즘을 설명한다.

만약 최소신장트리가 무엇인지 모른다면 최소신장트리(Minimum Spanning Tree) 를 먼저 학습해야한다.

 

Q. 크러스컬 알고리즘은 무엇인가 ?

크러스컬 알고리즘은 최소신장트리를 생성하기위한 알고리즘 중하나로 핵심은 모든 그래프 G 에 연결된 모든 에지들의 가중치를 오름차순으로 정렬하고 에지 중 가장 작은 것부터 하나씩 이어 나가는 방법이다. 

주의 할 점은 이어 붙일 때 그래프에 사이클이 생기지 않도록 해야(신장트리가 되려면 사이클이 없다고 얘기했다.) 한다는것이다. 

그림으로 설명하면...

 

크러스컬 알고리즘

STEP (a) 그래프에서 에지의 가중치가 가장 작은 E = (h,g)를 젤 먼저 선택한다.

이어서 가중치가 낮은 순서대로 하나씩 선택해 나간다. 

STEP(b) E = (h,g) 다음으로 가중치가 낮은게 E = (c, i) 와 (g,f) 가 있는데 뭐 아무거나 선택해도 된다. 여기서는 (c, i)를 선택한다.

STEP(c) E = (g, f)를 선택한다

≈

STEP(e) E = (c, f)를 선택한다

STEP(f) 그 다음 작은 것인  E = (i, g) 인데 만약 이걸 선택하게되면 사이클(cycle)이 생겨 신장트리가 될 수 없으니 선택하면안됨

STEP(g) E = (c, d)를 선택한다.

STEP(h) E = (h, i)를  선택하려 하니 사이클이 생기게 되므로 skip 한다.

STEP(i) E = (a, h)를 선택한다.

STEP(j) E = (b, c)를  선택하려 하니 사이클이 생기게 되므로 skip 한다.

STEP(k) E = (d, e)를 선택한다.

STEP(l) E = (e, f)를 선택하려 하니 사이클이 생기게 되므로 skip 한다.

STEP(m) E = (b, h)를 선택하려 하니 사이클이 생기게 되므로 skip 한다.

STEP(n) E = (d, h)를 선택하려 하니 사이클이 생기게 되므로 skip 한다.

사실 STEP(k) 이후 부터는 할 필요 없다, 왜냐면 이미 k 까지 하면 노드개수 N= 9개일때 신장트리인경우 에지개수 N-1 8개가 이미 성립하기 때문에 더 이상 진행할 필요 없는것이다.

 

그림으로는 매우 명확하고 단순한데 이걸 코드로 어찌 구현할까 ??

 

Q. 전체적으로 에지를 정렬하고 작은 것부터 하나씩 선택하면서 신장트리가 될때까 지 반복하는건 알겠는데 해당 노드 선택시 사이클이 있는지 없는지 어떻게 알수 있나?

답은 [그래프]Union-Find: Disjoint Set 를 알아야만 한다.   

여기서 학습하기엔 좀 길어질 거 같아 별도 주제로 분리 한다.

읽고 왔다면 Disjoint Set 을 이용하여 어떻게 사이클이 있는지 알 수 있을까? 사실 잘 감이 안잡히긴한데... 

[그래프] 그래프내에서 사이클 찾는 방법들(Detect Cycle in an Graph) 에서 감을 잡도록 한다.

 

 

Q. 구현 어찌 하오리까 ?

여기까지 왔으면  의사코드(Pseudocode)는 대충 다음과 같다.

MAKE-SET (처음 정점들을 disjoint 한 집합을 만들기위해 각각 루트트리로 만드는 것을 말함) 이나 FIND-SET, UINON 부분은  [그래프]Union-Find: Disjoint Set 부분이다. 

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

코드중 MinPriority, Graph, Edge 클래스는 별도 설명이 필요 없을것이라 판단되어 약식 코드만 게재하다.

FULL 코드는  KruskalMST 소스코드 를 참고하면 된다.

public class KruskalMST {
 
    // Kruskal 알고리즘을 통해 사이클이 없는  에지들을 에지 가중치가 작은 순서(큐)로 저장
    private Queue<Edge> mst = new Queue<Edge>();  
 
 
    public KruskalMST(Graph G) {
        // 에지 가중치를 낮은 순으로 졍렬한다. 여기서는 최소값부터 뽑으면 되니 최소힙을 이용한다.
        MinPriority<Edge> pq = new MinPriority<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }
 
        // UF는 disjoint 자료구조 클래스임.
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            // 에지가 낮은 것부터 뽑아서 
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            // 연결하려는 v -> w 가 사이클이 없는 경우만 union 을 수행한다.
            if (!uf.connected(v, w)) { 
                uf.union(v, w);   
                mst.enqueue(e);  // add edge e to mst
               
            }
        } 
    }
 
}

레퍼런스

• https://www.geeksforgeeks.org/union-find/
• KruskalMST 소스코드
• [권호흠 알고리즘 강좌] : http://alg.pknu.ac.kr/t/topic/576 
• https://algs4.cs.princeton.edu/43mst/KruskalMST.java.html