[알고리즘] 최소 비용 신장 트리 :: 늦깎이 IT

[신장트리란?]

신장트리 (Spanning Tree)는 그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 말한다.

N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다.

4개의 노드로 이루어진 아래와 같은 그래프를 보면, 신장트리를 구성하는 방법은 유일하지 않음을 알 수 있다.

[최소 비용 신장트리란?]

최소 비용 신장트리 (Minimum Spanning Tree)는 그래프에서 가능한 신장트리들 중에서 가중치의 합이 최소인 신장트리를 말한다. 위의 그림에서는 간선의 가중치가 없기때문에 최소신장트리(MST)를 찾을 수 없다.

그러나, 아래의 그림과 같이 간선마다 가중치가 주어질 경우, 간선의 합이 최소이면서 신장트리의 조건을 만족하는 임의의 신장트리. 즉, 최소신장트리를 찾을 수 있다.

[크루스칼 알고리즘]

크루스칼 (Kruscal) 알고리즘은 그래프의 모든 정점을 최소 비용으로 연결하는 알고리즘이다.

크루스칼 알고리즘의 동작 원리는 다음과 같다.

• 간선들을 가중치의 오름차순으로 정렬한다.
• 간선들을 그 순서대로 하나씩 선택하되, 이미 선택된 간선들과 사이클이 형성되면 선택하지 않는다.
• N - 1 개의 간선이 선택되면 종료한다.

크루스칼 알고리즘에서 사이클이 형성이 되는지 아닌지를 확인하는 방법은 [ Disjoint Set ]를 사용한다.

[사이클 검사]

크루스칼 알고리즘의 과정 중에서 "사이클이 형성되면 선택하지 않는다." 라고 했다. 이 과정에 초점을 맞춰 어떻게 최소비용 신장트리를 구성하는지 살펴본다.

[초기 상태]

• 그래프의 초기상태에서는 아래 그림과 같이 나타낼 수 있다. 
• 각각의 노드(a, b, .... i)가 집합으로 표현되고, 각 노드들을 연결하는 간선의 가중치가 표현되어 있다.
• 각 간선의 가중치를 오름차순으로 정렬한 후, 그 간선들을 차례대로 선택한다.
• 이 상태에서 최소 신장 트리를 반환할 집합 A를 공집합으로 초기화하고 조건을 만족하는 간선들을 집합 A에 추가시킨다.

간선 E(h, g) 확인

• 간선 E(h, g)를 선택함에 따라 사이클이 형성되는지 확인한다.
• 사이클을 확인하는 방법은 노드 h와 g가 같은 집합에 속해있는지 확인하면 된다.
• 노드 h와 g가 각각 다른 집합에 속해있으므로 집합 A에 간선 E(h, g)를 추가하고 집합 h와 g를 합집합한다.

간선 E(c, i) 확인

• 노드 c와 i는 같은 집합에 속하지 않으므로, 간선 E(c, i)를 집합 A에 추가하고, 집합 c와 i를 합집합한다.

간선 E(f, g) 확인

• 노드 f와 g는 같은 집합에 속하지 않으므로, 간선 E(f, g)를 집합 A에 추가하고, 집합 f와 g를 합집합한다.

간선 E(a, b) 확인

• 노드 a와 b는 같은 집합에 속하지 않으므로, 간선 E(a, b)를 집합 A에 추가하고, 집합 a와 b를 합집합한다.

간선 E(c, f) 확인

• 노드 c와 f는 같은 집합에 속하지 않으므로, 간선 E(c, f)를 집합 A에 추가하고, 집합 c와 f를 합집합한다.

간선 E(i, g) 확인

• 노드 i와 g는 같은 집합에 속하므로, 간선 E(i, g)를 집합 A에 추가하지 않고 건너뛴다.

간선 E(i, h) 확인

• 노드 i와 h는 같은 집합에 속하므로, 간선 E(i, h)를 집합 A에 추가하지 않고 건너뛴다.

간선 E(c, d) 확인

• 노드 c와 d는 같은 집합에 속하지 않으므로, 간선 E(c, d)를 집합 A에 추가하고, 집합 c와 d를 합집합한다.

간선 E(b, c) 확인

• 노드 b와 c는 같은 집합에 속하지 않으므로, 간선 E(b, c)를 집합 A에 추가하고, 집합 b와 c를 합집합한다.

간선 E(a, h) 확인

• 노드 a와 h는 같은 집합에 속하므로, 간선 E(a, h)를 집합 A에 추가하지 않고 건너뛴다.

간선 E(d, e) 확인

• 노드 d와 e는 같은 집합에 속하지 않으므로, 간선 E(d, e)를 집합 A에 추가하고, 집합 d와 e를 합집합한다.
• N - 1 개의 간선을 선택했으므로 종료한다.

[의사 코드]

MST-KRUSKAL(G, W)
    A is empty
    for each vertex v ∈ V[G]
        do MAKE-SET(v)
    sort edges of E order by weight asc
    
    for each edge(u,v) ∈ E 
        if FIND-SET(u) != FIND-SET(v)
            then A ← A U {(u,v)}
                UNION(u, v)
 
    return A

2)번 라인에서 MST를 담는 집합 A를 공집합으로 초기화한다.

3)번 라인에서 모든 노드에 대해서 MAKE-SET 연산을 수행한다.

5)번 라인에서 모든 간선들을 오름차순으로 정렬한다.

7)번 라인에서 각각의 간선들을 확인하며 임의의 간선 E(u, v)에 대해서 사이클이 발생하는지 확인한다.

9)번 라인에서 사이클이 발생하지 않으면, 집합 A에 간선 E(u, v)를 포함시키고 UNION 연산을 수행한다.

[시간 복잡도]

Make-Set의 시간 복잡도는 O(N)이다.

모든 간선을 오름차순으로 정렬하는 시간 복잡도는 간선의 갯수를 M이라고 할 때, O(MlongM)이다.

모든 간선을 순회하는데 걸리는 시간은 O(M)이고, 각각의 순회마다 Find와 Union 하는 연산은 O(1)이다.

결론적으로, 크루스칼 알고리즘의 시간 복잡도는 O(MlogM)이다.

[JAVA 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class Kruskal {
 
    static int N = 9;
 
    public static void main(String[] args) {
 
        Graph graph = new Graph(N);
        graph.addEdge(1, 2, 4);
        graph.addEdge(2, 3, 8);
        graph.addEdge(3, 4, 7);
        graph.addEdge(4, 5, 9);
        graph.addEdge(5, 6, 10);
        graph.addEdge(6, 7, 2);
        graph.addEdge(7, 8, 1);
        graph.addEdge(8, 9, 7);
        graph.addEdge(1, 8, 8);
        graph.addEdge(2, 8, 11);
        graph.addEdge(3, 6, 4);
        graph.addEdge(3, 9, 2);
        graph.addEdge(4, 6, 14);
        graph.addEdge(7, 9, 6);
 
        kruskalMST(graph);
    }
 
    public static void kruskalMST(Graph graph) {
 
        Collections.sort(graph.list);
 
        Edge[] result = new Edge[graph.V];
        int mst = 0;
        int e = 1;
        int idx = 0;
 
        while (e < graph.V - 1) {
 
            Edge edge = graph.list.get(idx++);
 
            if (find(graph.subset, edge.src) != find(graph.subset, edge.dest)) {
                union(graph.subset, edge.src, edge.dest);
                mst += edge.weight;
                result[e++] = edge;
            }
        }
        for (int i = 1; i < e; i++)
            System.out.println((char) (result[i].src - 1 + 'a') + " <-> " + (char) (result[i].dest - 1 + 'a') + " : "
                    + result[i].weight);
        System.out.println("Kruskal MST : " + mst);
    }
 
    public static int find(Subset[] subset, int u) {
 
        if (subset[u].parent == u)
            return u;
        else
            return subset[u].parent = find(subset, subset[u].parent);
    }
 
    public static void union(Subset[] subset, int u, int v) {
 
        int uRoot = find(subset, u);
        int vRoot = find(subset, v);
 
        if (uRoot == vRoot)
            return;
 
        if (subset[uRoot].rank < subset[vRoot].rank)
            subset[uRoot].parent = vRoot;
        else if (subset[uRoot].rank > subset[vRoot].rank)
            subset[vRoot].parent = uRoot;
        else {
            subset[uRoot].parent = vRoot;
            subset[vRoot].rank += 1;
        }
    }
}
 
class Graph {
 
    int V;
    List<Edge> list;
    Subset[] subset;
 
    public Graph(int size) {
        this.V = size + 1;
        list = new ArrayList<>();
        subset = new Subset[V];
        for (int i = 1; i < V; i++) {
            subset[i] = new Subset(i, 0);
        }
    }
 
    public void addEdge(int src, int dest, int weight) {
        list.add(new Edge(src, dest, weight));
    }
}
 
class Edge implements Comparable<Edge> {
    int src;
    int dest;
    int weight;
 
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Edge e) {
        return this.weight - e.weight;
    }
}
 
class Subset {
    int parent;
    int rank;
 
    public Subset(int parent, int rank) {
        this.parent = parent;
        this.rank = rank;
    }
 
}

[ 프림의 알고리즘 ]

크루스칼 알고리즘은 간선들의 가중치를 오름차순으로 정렬하고, 가중치가 작은 간선들부터 선택하기 때문에 여러 개의 작은 트리가 하나의 더 큰 트리로 합쳐지는 방법이라고 볼 수 있다.

이에 반해, 프림의 알고리즘은 임의의 노드부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다.

프림 알고리즘의 동작 방식은 다음과 같다.

• 임의의 노드를 출발 노드로 선택한다.
• 출발 노드를 포함하는 트리를 점점 확장해간다.
• 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택한다.

아래 그림을 보자.

그림 (a)에서는 노드 a를 출발 노드로 선택하고 집합 S에 추가한다. 그 다음, 집합 S에 속한 노드로부터 집합 S에 속하지 않은 노드들간의 간선을 비교하여 최소 가중치를 갖는 간선을 선택한다. 즉, (b) 그림처럼 간선 e(a, b)와 e(a, h)를 비교후, 더 작은 가중치를 갖는 e(a, b)를 선택하고 노드 b를 집합 S에 추가한다.

그림 (c)에서도 집합 S에 속한 노드 a, b와 집합 S에 속하지 않은 노드들간의 가중치를 비교하고, 가장 작은 가중치를 갖는 노드를 집합 S에 추가한다. 그림 (c)에서는 노드 c가 선택되었다. 이와 같은 방법으로 그림 (d)에서 노드 i 가 선택되었다.

그림 (e)에서는 노드 f를, 그림 (f)에서는 노드 g를 선택했다.

그림 (g)에서는 노드 h를, 그림 (h)에서는 노드 d를 선택했다.

마지막으로 그림 (i)에서 노드 e를 선택한다. 집합 S가 노드의 갯수 N과 같아졌으므로 알고리즘을 종료한다.

[ 초기 상태 ]

프림의 알고리즘 동작 과정을 조금 더 자세히 설명한다. 집합 Va에 포함된 노드들과 Va에 포함되지 않은 노드들을 연결하며 진행한다.

Va에 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지한다.

• key(v) : 이미 Va에 속한 노드와 자신을 연결하는 간선들 중 가중치가 최소인 w(u, v)의 가중치
• π(v) : 그 간선 (u, v)의 끝점 u

아래 그림을 보자.

집합 Va에는 노드 a, b, c, i가 포함되어 있다. 집합 Va에 속하지 않는 노드 d, e, f, g, h에 대해서 key와 π값을 갱신한다.

• 노드 d를 살펴보자. 노드 d와 Va에 속한 노드들간에 연결된 간선은 e(c, d)밖에 없다. 그러므로 key(d) = 7이고, π(d) = c이다.
• 노드 e를 살펴보자. 노드 e와 Va에 속한 노드들간에 연결된 간선은 존재하지 않는다. 그러므로 key(c) = ∞이고, π(c) = a이다.  π(c) = a는 무시해도 된다.
• 노드 f를 살펴보자. 노드 f와 Va에 속한 노드들간에 연결된 간선은 e(c, f)밖에 없다. 그러므로 key(f) = 4이고, π(f) = c이다.
• 노드 g를 살펴보자. 노드 g와 Va에 속한 노드들간에 연결된 간선은 e(g, i)밖에 없다. 그러므로 key(g) = 6이고, π(g) = i이다.
• 노드 h를 살펴보자. 노드 h와 Va에 속한 노드들간에 연결된 간선은 e(a, h)와 e(b, h), e(h, i)가 있다. 이중 가장 작은 가중치를 갖는 간선은 e(h, i)이므로, key(h) = 7이고, π(h) = i이다.

집합 Va에 속하지 않는 모든 노드들에 대하여 key값과  π값을 갱신했다면, 이중 가장 작은 key값을 갖는 노드를 Va 집합에 포함시킨다. 가장 작은 키 값은 key(f) = 4 이므로, 집합 Va에 노드 f를 포함시킨다. 아래 그림을 보자.

집합 Va에 노드 f를 추가한 뒤에 Va에 속하지 않은 모든 노드들의 key값과 π값을 갱신해야 한다. 

• 노드 d를 살펴보자. 노드 d와 Va에 속한 노드들간에 연결된 간선은 e(c, d)와 e(d, f)이다. 기존의 key(d) = 7 보다 e(d, f) = 14의 값이 더 크므로 key(d) = 7로 유지된다.
• 노드 e를 살펴보자. 노드 e와 Va에 속한 노드들간에 연결된 간선은 e(d, e)이다. 기존의 key(e) = ∞ 보다 e(d, e) = 10의 값이 더 작으므로 key(e) = 10, π(e) = f로 갱신된다.
• 노드 g를 살펴보자. 노드 g와 Va에 속한 노드들간에 연결된 간선은 e(g, i), e(f, g)이다. 기존의 key(g) = 6 보다 e(g, f) = 2의 값이 더 작으므로 key(g) = 2, π(g) = f로 갱신된다.

이때 노드 h에 대한 key값과 π값을 갱신하지 않는 이유는 무엇일까?

노드 f를 집합 Va에 추가하기전과 추가한 이후에 변하는 것은 오로지 노드 f가 집합 Va에 속해있는지 아닌지이다.

그러므로, 노드 f와 인접하지 않은 노드 h에 대해서는 갱신 여부를 확인할 필요조차 없는 것이다.

[ 의사 코드 ]

MST-PRIM(G, w, r) // r은 시작 노드
    for each u ∈ V do
        key[u] ← ∞
        π[u] ← null
    end
    
    Va ← {r}
    key[r] ← 0
 
    while |Va| < N do
        find u ∉ Va the minimum key
        Va ← Va U {u}
        for each v ∉ Va adjacent to u do
            if key[v] > w(u, v) then
                key[v] ← w(u, v)
                π[v] ← u
            end
        end
    end

2)~5)번 라인에서 각각의 노드에 대한 key 값과 π값을 초기화한다.

7)번 라인에서 시작 노드 r을 집합 Va에 추가한다.

10)번 라인에서 집합 Va의 크기가 N보다 작을 때 까지 반복을 수행한다.

11)번 라인에서 집합 Va에 포함되지 않는 노드들 중 key 값이 최소인 노드 u를 찾는다.

12)번 라인에서 집합 Va에 노드 u를 포함시킨다.

13)번 라인에서 노드 u와 인접한 모든 노드 v에 대해서 이미 저장된 key값과 w(u, v) 값을 비교해 갱신한다.

[ 시간 복잡도 ]

그래프 G에 포함된 노드의 갯수를 N이라 하자.

집합 Va의 크기가 N과 같아질 때 까지 반복을 수행하므로 while 문은 N - 1번 반복하므로 시간 복잡도는 O(N)이다.

집합 Va에 속하지 않은 최소 key 값을 갖는 노드 u를 찾는 연산은 최대 N번이므로 시간 복잡도는 O(N)이다.

최소 key 값을 갖는 노드 u에 인접한 노드들은 최대 degree(u) = N - 1이므로 시간 복잡도는 O(N)이다.

노드 u와 인접한 노드 v의 key 값을 비교해서 갱신하는 시간 복잡도는 O(1)이다.

즉, 전체 시간 복잡도는 O( N * ( N +( N * 1 ) ) ) = O(N^2) 이다.

[ 더 생각해보기 ]

위의 의사코드를 살펴보면, 집합 Va에 속하지 않은 노드들 중 가장 작은 key값을 갖는 노드를 찾는 연산을 반복하고, 이때의 시간 복잡도는 O(N)이라고 했다.

이때, 최소 힙 우선순위 큐를 사용하면 최소 key 값을 찾는 연산을 O(logN)시간에 수행할 수 있다. 

[ 의사 코드 ]

MST-PRIM(G, w, r) // r은 시작 노드
    for each u ∈ V do
        key[u] ← ∞
        π[u] ← null
    end
    
    key[r] ← 0
    Q ← V[G]
    while Q != ∅
        do u ← EXTRACT-MIN(Q)
            for each v ∈ Adj[u]
                do if v ∈ Q and w(u, v) < key[v]
                    then π[v] ← u
                         key[v] ← w(u, v)

2)~5)번 라인에서 각각의 노드에 대한 key 값과 π값을 초기화한다.

8)번 라인에서 모든 노드들을 우선순위 큐에 저장한다.

9)번 라인에서 큐에 저장된 노드들의 갯수만큼 반복한다.

10)번 라인에서 큐에 저장된 노드들 중 가장 작은 key값을 갖는 노드 u를 찾는다.

11)번 라인에서 노드 u에 인접한 모든 노드들 v를 찾는다.

12)번 라인에서 노드 v가 큐에 속해있고, key[v] 값이 w(u, v)보다 크다면 갱신한다. 노드 v가 큐에 속해있다는 것은 집합 Va에 포함되지 않았다는 뜻과 같다.

13), 14)번 라인에서 key 값과 π 값을 갱신한다. 

[ 시간 복잡도 ]

그래프 G에 포함된 노드의 갯수를 N, 간선의 갯수를 M개라고 하자.

큐의 사이즈가 0일때 까지 반복을 수행하므로 시간 복잡도는 O(N)이다.

큐에서 최소 값을 갖는 노드 u를 찾는 시간 복잡도는 O(logN)이다.

노드 u에 인접한 모든 노드 v를 찾는 시간 복잡도는 모든 노드들의 차수의 합만큼 반복하므로 아래 식을 만족한다.

"모든 노드들의 차수의 합은 간선의 갯수에 2배를 한 것과 같다" 라는 성질을 이용한 것이다.

노드 u와 인접한 노드 v의 key 값을 비교해서 갱신하는 시간 복잡도는 O(logN)이다.

즉, 전체 시간 복잡도는 O(NlogN + MlogN) = O(MlogN)이다.

[ JAVA 코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
public class Prim {
 
    static class Node {
        int dest;
        int weight;
 
        public Node(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
 
    static class Node2 implements Comparable<Node2> {
        int key;
        int node;
        int prev;
 
        public Node2(int key, int node, int prev) {
            this.key = key;
            this.node = node;
            this.prev = prev;
        }
 
        public int compareTo(Node2 o) {
            if (this.key < o.key)
                return -1;
            else if (this.key == o.key) {
 
                return this.node - o.node;
 
            } else
                return 1;
        }
    }
 
    int size;
    Node2[] status;
    List<List<Node>> list;
 
    public Prim(int size) {
 
        this.size = size + 1;
        status = new Node2[this.size];
        list = new ArrayList<>();
 
        for (int i = 0; i < this.size; i++) {
            status[i] = new Node2(Integer.MAX_VALUE, i, -1);
            List<Node> item = new ArrayList<>();
            list.add(item);
        }
    }
 
    public void addEdge(int src, int dest, int weight) {
        list.get(src).add(new Node(dest, weight));
        list.get(dest).add(new Node(src, weight));
    }
 
    public void primMST(int start) {
 
        int sum = 0;
        status[start].key = 0;
        status[start].prev = 0;
 
        boolean[] mst = new boolean[this.size];
        PriorityQueue<Node2> q = new PriorityQueue<>();
 
        for (int i = 1; i < this.size; i++)
            q.offer(status[i]);
 
        while (!q.isEmpty()) {
 
            Node2 node = q.poll();
            mst[node.node] = true;
            sum += node.key;
 
            for (int i = 0; i < list.get(node.node).size(); i++) {
 
                Node adj = list.get(node.node).get(i);
 
                if (!mst[adj.dest]) {
                    if (status[adj.dest].key > adj.weight) {
                        q.remove(status[adj.dest]);
                        status[adj.dest].key = adj.weight;
                        status[adj.dest].prev = node.node;
                        q.add(status[adj.dest]);
                    }
                }
            }
        }
        for (int i = 1; i < this.size; i++) {
            if (i != start)
                System.out.println((char) (status[i].prev - 1 + 'a') + " -> " + (char) (i - 1 + 'a'));
        }
        System.out.println("Prim MST : " + sum);
    }
 
    public static void main(String[] args) {
        Prim prim = new Prim(9);
        prim.addEdge(1, 2, 4);
        prim.addEdge(2, 3, 8);
        prim.addEdge(3, 4, 7);
        prim.addEdge(4, 5, 9);
        prim.addEdge(5, 6, 10);
        prim.addEdge(6, 7, 2);
        prim.addEdge(7, 8, 1);
        prim.addEdge(8, 9, 7);
        prim.addEdge(1, 8, 8);
        prim.addEdge(2, 8, 11);
        prim.addEdge(3, 6, 4);
        prim.addEdge(3, 9, 2);
        prim.addEdge(4, 6, 14);
        prim.addEdge(7, 9, 6);
 
        prim.primMST(1);
    }
 
}