15 Feb 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.

1. MST(Minimum Spanning Tree. 최소 신장 트리)

Spanning Tree : 그래프의 모든 노드를 포함하고, 노드들이 서로 연결되어 있으면서 사이클이 없는 트리

MST(Minimum Spanning Tree) : 엣지의 가중치가 최소인 Spanning Tree

예를 들어보자. 그래프의 노드 1, 2, 3, 4가 있을 때 이 그래프의 Spanning Tree는 다음과 같다.

위의 그림과 같이 Spanning Tree를 만드는 경우의 수는 다양하다.
다음으로 MST의 예를 보자. 아래의 그래프가 있을 때, 가중치가 최소인 엣지를 골라 모든 노드가 서로 연결되도록 트리를 만들면(=MST) 다음과 같다.

그렇다면 이러한 MST를 구하기 위해서는 어떻게 해야할까? 바로 크루스칼 알고리즘과 프림 알고리즘을 이용하면 된다! 지금부터 공부해보자.

cf) 앞서 배운 최단경로와 MST를 헷갈리면 안된다. 최단경로는 한 노드에서 한 노드로, 한 노드에서 여러 노드로, 혹은 여러 노드끼리 방문할 수 있는 최단거리를 구하는 것이고, MST는 모든 노드들이 서로 연결되어 있는 가장 짧은 트리이다. 즉, 위의 그림에서 MST를 구했다고 하더라도 노드 1에서 6까지의 경로가 최단경로라고 보장할 수 없다.

2-1. Kruskal Algorithm(크루스칼 알고리즘)

그래프에서 가중치가 최소인 엣지를 사이클이 존재하지 않도록 순서대로 고르며 트리를 만들어 MST를 구성하는 알고리즘

크루스칼 알고리즘은 Disjoint Set을 자료구조로 활용한다. 알고리즘 수행 과정은 다음과 같다.

1. 모든 노드에 대해 make-set 연산 수행

2. 모든 엣지의 가중치를 오름차순 정렬

3. 가중치가 최소인 엣지 순서대로 사이클이 존재하지 않도록 트리를 구성

   How?　 union-find 연산을 통해 엣지가 연결된 두 노드가 서로 다른 셋임을 확인하면서!

그림으로 크루스칼 알고리즘을 이해해보자.

(a)를 보자. 전체 엣지 중 가중치가 최소인 $(h, g)$를 찾아 연결한다. 그 다음으로 최소인 엣지인 $(c, i)$를 찾아 연결한다. 결과는 (b)와 같다.

이어서 (c)처럼 $(g, f)$도 이어주고, (d)처럼 $(a, b)$도 이어준다. 쉽다… 계속 진행해보자.

(e)처럼 해주고 난 다음, 가중치가 최소인 엣지는 $(i, g)$ = 6이다. 그런데 이 때, $(i, g)$를 이어버리면 사이클이 생기게 된다. 따라서! $(i, g)$는 이어주지 않고 그대로 넘어간다.

그 다음 가중치가 최소인 엣지인 $(c, d)$를 이어주면 (g)처럼 된다. 이후, $(h, i)$를 이어주게 되면 또 사이클이 발생하기 때문에 역시 이어주지 않고 넘어간다. 나머지는 그림으로 설명을 대체한다.

이것으로 MST를 최종적으로 완성할 수 있다.

2-2. Kruskal Algorithm 시간복잡도

먼저, 모든 노드에 대해 make-set 연산을 수행하므로, 노드의 개수가 $V$일 때 $O(V)$ 가 소요된다.

그리고 엣지의 개수가 $E$일 때, 먼저 모든 엣지의 가중치를 오름차순으로 정렬하므로, 가장 빠른 정렬알고리즘인 퀵소트와 같이 $O(E\log E)$가 소요된다. 따라서 $O(V) + O(E\log E) = O(E\log E)$ 이다.

크루스칼 알고리즘의 시간복잡도를 증명해보자. 크루스칼 알고리즘은 Greedy Algorithm임에도 불구하고 최적해를 구할 수 있는 것으로 증명되어 있다. 귀류법을 사용하면 된다.

만약 크루스칼 알고리즘이 선택하는 간선 중 MST에 포함되지 않는 간선이 있다고 하자. 그리고 이 중 가장 가중치가 작은(처음으로 선택되는) 간선을 $l(u, v)$라고 하자. MST는 이 간선을 포함하지 않으므로 당연히 $u$와 $v$는 다른 간선 $L$로 연결되어 있을 것이다. 이 때, 크루스칼 알고리즘은 오름차순으로 정렬되어 있는 간선 중 가장 가중치가 작은 간선부터 선택하기 때문에 $l(u, v)$는 반드시 $L$보다 작거나 같다. 따라서 $l(u, v)$를 연결해도 Spanning Tree가 유지되면서 전체 가중치는 더 작아질 수 있다. 즉, $L$을 버리고 $l(u, v)$를 선택하면 이 결과는 MST이기 때문에 기존 명제와 모순된다. 따라서 크루스칼 알고리즘은 반드시 참이다.

3-1. Prim Algorithm(프림 알고리즘)

시작 정점과 가장 인접한 정점을 선택해 트리를 확장하고, 만들어진 트리와 가장 인접한 정점을 선택해 트리를 확장해나가는 과정을 반복하며 MST를 구성하는 알고리즘

앞서 배운 크루스칼 알고리즘이 전체 엣지를 대상으로 작은 순서대로 MST를 만들었다면, 프림 알고리즘은 시작정점을 대상으로 가장 인접한 노드를 이어 트리를 만들고, 이 트리를 대상으로 또 다시 인접한 노드를 찾아 트리를 확장하는 방식이다. 이 프림 알고리즘은 최단 경로 알고리즘인 다익스트라, 벨만-포드와 그 방식이 유사한데, 다익스트라와 벨만-포드가 시작정점에서 노드를 잇고, 그 노드에서 다시 인접한 노드를 잇는 방식이라면 프림 알고리즘은 노드를 잇고 그 다음엔 트리와 노드를 잇는 방식이다. 즉, 마지막에 이어진 노드만을 대상으로 하는 것이 아니라 그 트리에 속한 전체 노드를 대상으로 인접한 노드를 잇는 방식인 것이다. 헷갈리지 말자!

프림 알고리즘의 전체적인 과정은 다음과 같다.

1. 시작노드 설정
2. 시작노드와 가장 인접한 노드를 찾아 이어 트리를 만듬
3. 2에서 만들어진 트리와 가장 인접한 노드를 찾아 또 트리를 만듬
4. 3의 과정을 반복

이제 그림으로 이해해보자.

먼저 시작노드를 $a$로 설정한다. 이후 $a$와 가장 인접한 노드인 $b$를 이어주며 트리를 만든다. 결과는 (b)와 같다.

그 다음, $(a, b)$와 인접한 노드인 $c$, $h$ 중 가장 인접한 노드인 $c$와 기존 트리를 이어준다. 결과는 (c)와 같다. 그 다음, $(a, b, c)$와 인접한 노드인 $d, h, i, f$중 가장 인접한 노드인 $i$와 기존 트리를 이어준다. 결과는 (d)와 같다.

이제 귀찮으니 설명은 생략하고 그림으로 이를 대체한다.

위 과정을 다 마치면 (i)처럼 깔끔한 MST를 만들 수 있다.

3-2. Prim Algorithm 시간복잡도

프림 알고리즘을 사용하기 위해 최대/최소값을 찾는 것에 특화된 알고리즘인 Heap(힙)을 사용한다고 하자. 노드의 개수를 $V$, 엣지의 개수를 $E$라 할 때, 먼저 모든 노드를 초기화 하는 데에 $O(V)$ 시간이 소요된다. 이후 Heap의 리프노드부터 루트노드까지 이동하는데 $O(\log V)$이 소요되고, 이것을 노드에 연결된 엣지의 수만큼 탐색해야하므로 $O(\log V) * O(V) = O(V\log V)$가 소요된다.

따라서 총 시간복잡도는 $O(V) * O(V\log V) = O(V^2\log V)$이고, $V^2 \approx E$ 이므로 최종 시간복잡도는 $E\log V$이다.

4. MST 관련 잡다한 지식들

• 연결되어 있는 그래프 두 개를 이어서 최단 경로를 만들 수 있는가?

  애초에 두 그래프가 원래 MST였는데 잘려져있는 것이라고 생각한다면, 두 그래프를 가로지르는 가장 작은 엣지를 선택한다면 최단경로가 될 수 있음

• 크루스칼 알고리즘과 프림 알고리즘 중, dense grpah와 sparse graph에 효율적인 알고리즘은?

  크루스칼 알고리즘 : 모든 간선을 정렬하므로 dense할 경우 시간이 오래 걸릴 수 있다. 따라서 sparse graph에 효율적이다.

  프림 알고리즘 : 모든 간선 살펴볼 필요 없이 시작 정점에서 차근차근 진행되므로 dense graph, sparse graph 모두 효율적으로 적용할 수 있다.