Prim·Kruskal은 모든 MST를 찾을 수 있는가

MST는 유일하지 않을 수 있다. Prim과 Kruskal 모두 한 번 돌리면 한 가지 MST를 내놓는다. 그런데 알고리즘을 다른 조건으로 여러 번 돌리면 가능한 모든 MST를 다 볼 수 있을까?

여러 MST가 가능한 그래프

MST가 유일하지 않을 수 있다는 사실은 이미 봤다. 핵심은 가중치 동률(tie) 이다. 다만 동률 간선이 한 사이클에 있다는 것만으로는 갈림이 생기지 않는다.

삼각형 A–B(1), B–C(1), A–C(5)를 보자. 사이클 위에 가중치 1인 간선이 둘 있지만 MST는 {A–B, B–C} 하나뿐이다. 두 간선이 동률이어도 둘 다 뽑혀야 그래프가 이어지므로 고를 일이 없다.

갈림은 동률 간선이 같은 자리를 두고 맞설 때 생긴다. 하나를 넣으면 다른 하나가 사이클을 만들어 더는 들어갈 수 없는 관계여야 한다. 삼각형의 두 간선은 그런 사이가 아니다.

작은 예를 보자. 정점이 4개고 간선이 5개인 그래프다.

간선	가중치
A–B	1
C–D	1
B–C	2
A–D	2
B–D	3

가중치 1인 A–B와 C–D는 어느 MST에도 들어간다. 남는 일은 덩어리 {A, B}와 {C, D}를 잇는 것이고, 그 자리를 두고 가중치 2의 B–C와 A–D가 맞선다. 하나를 넣으면 사이클 A–B–C–D–A가 닫혀 다른 하나는 들어갈 수 없다. 가능한 MST는 정확히 두 가지이며 가중치 합은 모두 $1 + 1 + 2 = 4$로 같다.

좌측은 {A–B, C–D, B–C}, 우측은 {A–B, C–D, A–D}. 차이는 가중치 2의 두 간선 중 어느 것이 선택되었는지뿐이다.

---

Prim의 자유도

알고리즘이 자유롭게 정할 수 있는 부분을 선택 규칙 이라 부르자. 아래에서 「조건을 바꾼다」는 말은 모두 이 선택 규칙을 바꾼다는 뜻이다.

Prim은 시작 정점에서 트리를 키워간다. 선택 규칙은 두 가지다.

• 시작 정점. 어디서 출발하든 정확성 증명에 의해 항상 어떤 MST가 나오지만, 시작 정점이 달라지면 동률을 만나는 순서도 달라져 다른 MST가 나올 수 있다.
• 동률 우선순위. 컷을 건너는 최소 가중치 간선이 여럿일 때 어느 것을 먼저 꺼내는지를 정하는 규칙이다.

위 예제에서 A에서 시작한 Prim을 따라가 보자. 초기 트리 {A}에서 인접 간선은 (A,B,1)과 (A,D,2). 작은 쪽 (A,B,1)을 추가해 트리는 {A,B}. 다음으로 인접한 간선은 (B,C,2), (A,D,2), (B,D,3). 여기서 (B,C)와 (A,D)가 가중치 2로 동률이다. 어느 쪽을 고르느냐가 최종 MST를 결정한다.

---

Kruskal의 자유도

Kruskal은 정렬된 간선 목록을 순회한다. 선택 규칙은 하나, 같은 가중치 간선 사이의 정렬 순서 다.

위 예제의 정렬: (A–B, 1), (C–D, 1), (B–C, 2), (A–D, 2), (B–D, 3). (가중치 2 짝의 순서는 정렬 구현에 따라 다를 수 있다.)

• (A,B,1) 추가 → 컴포넌트 {A,B}, {C}, {D}
• (C,D,1) 추가 → {A,B}, {C,D}
• 다음은 (B,C,2) 또는 (A,D,2). 정렬에서 어느 게 먼저 오느냐에 따라:
  • (B,C,2) 먼저: 추가 → {A,B,C,D}. MST = {A–B, C–D, B–C}
  • (A,D,2) 먼저: 추가 → {A,B,C,D}. MST = {A–B, C–D, A–D}

같은 알고리즘이라도 정렬 순서가 다르면 다른 MST가 나온다.

Stable Sort

Stable sort는 같은 키 값을 가진 원소들의 원래 순서를 유지하는 정렬이다. 입력 $(a_1, w_1), (a_2, w_2), \ldots, (a_n, w_n)$을 $w$로 오름차순 정렬할 때, $w$가 같은 원소들의 상대 순서가 입력 순서와 일치한다.

• Merge sort는 stable. 일반적인 Quick sort는 unstable.
• Kruskal이 stable sort를 쓰면 입력 간선의 순서가 동률 처리를 모두 결정한다 → 출력 MST가 결정적(deterministic).
• Unstable sort를 쓰면 동률 간선 순서가 비결정적 → 여러 MST 중 하나가 (의도치 않게) 선택.

Stable sort가 주는 결정성은 디버깅에는 좋지만 한계가 있다. 입력 순서를 고정해 두면 늘 같은 MST 하나만 나오므로, 나머지 MST는 그 순서에서 선택되지 않는다. 다른 MST를 보려면 입력 순서 자체를 바꿔야 한다.

---

알고리즘이 모든 MST를 찾을 수 있는가

질문을 명확히 하자. Prim의 시작 정점·동률 우선순위 또는 Kruskal의 정렬 순서를 모든 가능한 조합으로 돌리면, 가능한 모든 MST를 다 볼 수 있을까?

답: 그렇다.

보이는 방법을 먼저 정하고 가자. 두 MST가 동률 간선의 교환으로 이어진다는 사실만으로는 부족하다. 그것은 MST끼리의 관계일 뿐, 알고리즘이 그 교환을 실제로 수행한다는 보장이 아니다. 그래서 목표로 삼을 MST를 먼저 정해 놓고, 그것을 출력하게 만드는 선택 규칙을 직접 구성한다. 목표 MST를 $T^*$라 쓴다.

Kruskal: 목표 MST를 앞에 두는 정렬

정렬 규칙. 가중치 오름차순으로 정렬하되, 가중치가 같은 간선끼리는 $T^*$에 속한 것을 앞에 둔다.

증명. 이 순서로 돌린 Kruskal이 지금까지 받아들인 간선의 모임을 $A$라 하고, 어느 시점에나 $A \subseteq T^*$임을 처리 순서에 대한 귀납으로 보인다.

처리 중인 간선 $e$가 $T^*$에 속하는 경우. 귀납 가정에서 $A \subseteq T^*$이므로 $A \cup \{e\}$도 $T^*$의 부분집합이다. 트리의 부분집합에는 사이클이 없으므로 Kruskal은 $e$를 받아들이고, $A \subseteq T^*$가 유지된다. 곧 $T^*$의 간선은 하나도 빠짐없이 받아들여진다.

$e$가 $T^*$에 속하지 않는 경우. $T^*$에 $e$를 더하면 사이클 $C$가 생기고, $C$에서 $e$를 뺀 간선은 모두 $T^*$에 있다. $T^*$가 MST이므로 $C$ 위에서 $e$가 가장 무겁다. $C$에 $e$보다 무거운 간선 $f$가 있다면 $T^*$에서 $f$를 빼고 $e$를 넣은 것도 신장 트리이면서 더 가벼워, $T^*$가 MST라는 사실에 어긋나기 때문이다. 따라서 $C - \{e\}$의 간선은 가중치가 $w(e)$ 이하다. 그중 가중치가 더 작은 것은 앞 단계에서 처리됐고, 같은 것도 정렬 규칙이 $T^*$의 간선을 앞에 두므로 $e$보다 먼저 처리됐다. 모두 이미 받아들여져 있으므로 $e$는 사이클을 만들어 버려진다.

$T^*$의 간선은 전부 받아들여지고 나머지는 전부 버려지므로 출력은 정확히 $T^*$다. $\square$

Prim: 목표 MST를 우선하는 동률 규칙

우선순위 규칙. 컷을 건너는 최소 가중치 간선이 여럿이면 그중 $T^*$에 속한 것을 고른다.

이 규칙을 쓰려면 고를 것이 있어야 한다. 최소 가중치 간선 가운데 $T^*$의 간선이 언제나 하나는 있다는 사실이 먼저 필요하다.

보조 정리. 지금까지 자란 트리의 정점 집합을 $S$라 하고 그 간선이 모두 $T^*$에 속한다고 하자. $S$와 $V - S$를 가르는 컷을 건너는 최소 가중치 간선 중 적어도 하나는 $T^*$에 속한다.

증명. 컷을 건너는 최소 가중치 간선 하나를 $g$라 하자. $g \in T^*$이면 보일 것이 없다. $g \notin T^*$라 하자. $T^*$에 $g$를 더하면 사이클이 생기는데, 사이클은 컷을 짝수 번 건너므로 $g$ 말고도 컷을 건너는 간선이 그 사이클에 있고, 사이클에서 $g$를 뺀 간선은 모두 $T^*$에 있으므로 그 간선 $f$는 $T^*$에 속한다.

$g$가 컷 위의 최소이므로 $w(g) \le w(f)$다. 만약 $w(g) < w(f)$라면, $f$가 사이클 위에 있으므로 $T^*$에서 $f$를 빼고 $g$를 넣어도 신장 트리이며 총 가중치가 줄어 $T^*$가 MST라는 사실에 어긋난다. 따라서 $w(g) = w(f)$이고, $f$는 컷 위의 최소 가중치 간선이면서 $T^*$에 속한다. $\square$

보조 정리에 의해 우선순위 규칙은 매 단계에서 적용할 수 있고, 고른 간선이 $T^*$에 속하므로 자라는 트리는 계속 $T^*$의 부분집합으로 남는다. Prim은 정점 수보다 하나 적은 간선을 뽑아 신장 트리를 완성하는데, $T^*$의 부분집합이면서 신장 트리인 것은 $T^*$ 자신뿐이다. $\square$

표현력의 의미

$T^*$를 아무 MST로나 잡았으므로, 두 알고리즘 모두 선택 규칙을 적절히 정하면 어떤 MST든 출력할 수 있다. 이 성질은 MST의 모임이 매트로이드의 기저 모임을 이룬다는 사실과 맞닿아 있다. 서로 다른 두 MST는 동률 간선의 일대일 교환으로 이어지고, Prim과 Kruskal의 선택 규칙은 그 교환을 지정하는 손잡이 노릇을 한다.

다만 주의할 점: 한 번의 실행은 항상 한 MST다. 여러 MST를 보려면 여러 번 실행해야 한다. “모든 MST를 한 번에 출력하는” 알고리즘은 별도 문제다(가능한 MST의 수가 지수적일 수 있으므로 단순히 열거가 효율적이지 않다).

---

가중치가 모두 다르면 MST는 유일

가중치가 모두 서로 다르다고 가정하자. 동률이 아예 없으므로 선택 규칙을 어떻게 바꿔도 갈릴 자리가 없다. 실제로 이때 MST는 하나뿐이다.

두 MST $T_1, T_2$가 서로 다르다고 가정하자. 두 트리의 대칭차에서 가중치 순서로 처음으로 달라지는 간선 $e$를 잡고, 이름을 바꿔 $e \in T_1 - T_2$라고 두자. $T_2 \cup \{e\}$가 만드는 사이클에는 어떤 $e' \in T_2 - T_1$이 존재한다. $e$를 처음으로 달라지는 간선으로 골랐고 가중치가 모두 다르므로 $w(e) < w(e')$이다. 그러면 $T_2$에서 $e'$를 빼고 $e$를 넣은 신장 트리가 더 가벼워져 $T_2$가 MST라는 사실에 모순이다. 결국 서로 다르다는 가정이 불가능하므로 $T_1 = T_2$.

정리. 모든 간선 가중치가 서로 다르면 MST는 유일하다.

이 조건 아래서는 Prim과 Kruskal이 선택 규칙과 관계없이 같은 답을 낸다. 실무에서 가중치 미세 조정(예: 모든 가중치에 작은 무작위 노이즈 추가)으로 MST를 유일하게 만들어 결과가 결정적이 되도록 하는 기법은 여기에 기반한다.

---

정리

조건	MST 개수	알고리즘이 찾을 수 있는 MST
모든 가중치가 서로 다름	1개 (유일)	그 유일한 MST
동률 간선이 같은 자리를 두고 맞섬	여러 개 (최대 지수적)	선택 규칙 변경으로 모두 도달 가능

Prim과 Kruskal은 매 실행에서 한 가지 답을 낸다. 그러나 목표 MST를 정해 놓고 그것을 앞세우는 선택 규칙을 만들면 그 MST가 그대로 출력된다. 선택 규칙만 바꾸면 어느 MST든 찾을 수 있다는 뜻이다. 그래서 “Prim은 어떤 MST를 찾는가, Kruskal은 어떤 MST를 찾는가”는 결국 “선택 규칙을 어떻게 정했는가”의 문제로 환원된다.