최소 신장 트리

MST; minimum spanning tree

그래프 $G = (V, E)$ 가 있을 때

트리란, 사이클이 없는 연결 그래프이다.
$G$ 의 신장 트리란, $G$ 의 부분 그래프로서 $G$ 의 모든 정점을 포함하는 트리이다.
$G$ 의 최소 신장 트리란, $G$ 의 신장 트리 중 가중치의 합이 최소가 되도록 하는 트리이다.

최소 신장 트리를 구하는 알고리즘으로는 대표적으로 kruskal's algorithm과 prim's algorithm이 있다. 둘 다 한 번 한 결정을 번복하지 않는 욕심쟁이(greedy) 알고리즘이다.

Kruskal's Algorithm

희소한 그래프에 유리하다.

비용이 가장 적은 간선을 찾는다.
해당 간선을 추가해도 사이클이 생기지 않으면 이를 추가한다.
모든 정점이 연결될 때까지 이를 반복한다.

증명

두 가지를 증명해야한다. 이렇게 만든것이 신장 트리이긴 한지, 가중치의 합이 최소가 되는지. 먼저 신장 트리가 되는지 확인하자. 신장 트리가 되려면 다음의 세 조건을 만족해야한다.

사이클이 없어야 하고
연결 그래프여야 하고
모든 정점을 포함해야한다.

귀류법으로 확인해보자. 가중치가 있는 연결 그래프 $G$ 에서 Kruskal 알고리즘으로 최소 신장 트리 $K$ 를 구했다고 하자.

$K$ 에는 사이클이 없다. 간선을 추가할 때 사이클이 생기는지 확인하고 추가하니까 당연하다.

$K$ 는 연결 그래프이다. $G$ 가 이미 연결 그래프이기 때문에 $K$ 가 연결 그래프가 아니려면 $G$ 의 특정 간선을 추가하지 않았어야 한다. 그 간선을 추가하지 않으려면 간선을 추가함으로써 사이클이 생긴다는 건데, 사이클이 있다는건 이미 연결된 상태라는 소리니까 말도 안 되는 소리다.

$K$ 는 $G$ 의 모든 정점을 포함한다. $G$ 가 이미 연결 그래프이기 때문에 $K$ 에 사이클이 없고 끝까지 돈다면 모든 정점을 포함할 수 밖에 없다.

따라서 kruskal 알고리즘으로 만든 $K$ 는 신장 트리이긴 하다. 그렇다면 가중치의 합이 최소가 되긴 하는가?

최소 신장 트리가 존재하긴 할테다. 최소 신장 트리의 간선의 집합을 $T_{mst}$ 라고 라고, kruskal 알고리즘으로 만든 트리의 간선의 집합을 $T_k$ 라고 하자. 이 둘이 다르다고 가정하고 모순을 찾아보자. 귀류법이다.

처음에는 $T_k$ 에 아무것도 없을 테니 $T_k \subset T_{mst}$ 이다. 그런데 어느 순간에 $T_{mst}$ 에는 없는 간선 $\{u, v\}$ 가 추가되어 $T_k \not\subset T_{mst}$ 가 된다.

$T_{mst}$ 에는 왜 $\{u, v\}$ 가 없을까? $u$ 와 $v$ 가 간접적으로 연결되어 있기 때문에 추가하는 순간 사이클이 생기기 때문일 것이다.

그런데 말입니다. $T_k$ 와 $T_{mst}$ 둘 다 신장 트리의 간선의 집합이기 때문에 그 크기가 같다. 즉 $T_{mst}$ 는 $u$ 와 $v$ 를 연결하기 위해 다른 간선을 썼다는 뜻이다. 허나 kruskal 알고리즘은 간선을 비용이 낮은 순으로 연결하기 때문에 $T_{mst}$ 가 $\{u, v\}$ 대신 고른 간선보다 비용이 작거나 같다. $T_{mst}$ 가 최소 신장 트리라고 했으니 더 작을 수는 없고 같을 것이다. 따라서 $T_{mst}$ 의 비용과 $T_k$ 비용이 같으므로 $T_k$ 도 최소 신장 트리이다.

구현

구현의 핵심은 두 가지이다. 첫째, 간선들을 어떻게 정렬할 것인가? 둘째, 사이클이 있는지는 어떻게 확인할 것인가?

간선 정렬은 그냥 정렬해도 되지만 최소 힙을 사용하여 해결할 수도 있다.

사이클이 있는지는 DFS나 BFS를 이용하여 확인할 수도 있지만 그보다 UnionFind 자료구조를 이용하는 편이 효율적이다.

위키피디아에 예쁜 의사코드가 있다.

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

시간 복잡도

$O(E \log E)$

Prim's Algorithm

밀집 그래프에 유리

정점 v를 고른다. (이거다 싶은거 아무거나 고른다)
정점 v의 간선 중 비용이 가장 적은 간선을 추가한다. 이젠 정점이 두 개다.
두 정점의 간선 중 (서로를 연결하는거 말고) 비용이 가장 적은 간선을 추가한다.
...
PROFIT!!

증명

마찬가지로 두 가지를 증명해야한다. 이렇게 만든것이 신장 트리이긴 한지, 가중치의 합이 최소가 되는지.

먼저 신장 트리가 되는지는 Kruskal 알고리즘과 같은 이유이다.

그렇다면 가중치의 합이 최소가 되는가? 아까와 같은 방법으로 해보자. 그래프 $G$ 에 대해 어딘가 어떤 형태로든 존재하는 최소 신장 트리의 간선의 집합을 $T_{mst}$ 라고 하고, Prim 알고리즘으로 만들어낸 간선의 리스트를 $T_p$ 라고 하자. 처음에는 $T_p \subset T_{mst}$ 인데 $T_p$ 에 $\{u, v\}$ 가 추가되는 순간 $T_p \not\subset T_{mst}$ 가 되었다고 하자. 왜 $T_{mst}$ 에는 간선 $\{u, v\}$ 가 없을까? $T_{mst}$ 는 신장 트리, 즉 연결 그래프이기 때문에 이미 정점 $u$ 와 $v$ 는 연결되어 있다. 따라서 간선 $\{u, v\}$ 를 추가하면 사이클이 생기게 된다.

둘 다 신장 트리이므로 간선의 수는 같다. $\{u, v\}$ 대신 다른 간선이 그 역할을 하고 있다는 뜻이다. 그런데 Prim 알고리즘은 가중치가 작은 순으로 간선을 추가하므로 간선 $\{u, v\}$ 는 그 다른 간선보다 비용이 같거나 더 작다. $T_{mst}$ 가 최소 신장 트리라고 했으므로 더 작을 수는 없고 같을 것이다. $\therefore T_p$ 는 최소 신장 트리이다.

시간 복잡도

$O(V^2+E) → O(E \log V)$

참고자료

네이버캐스트/최소 비용 신장 트리 알고리즘: 가장 적은 비용으로 연결하려면?