MST를 이해하는 가장 간단한 모델은 “모든 정점을 하나의 연결 성분으로 만들되, 사이클을 하나도 남기지 않고 간선 비용 합을 최소화한다”는 것입니다. 이 목표를 최단 경로, 장애 내성, 용량 제약과 분리하면 Kruskal과 Prim의 선택 근거와 적용 한계를 같은 기준으로 비교할 수 있습니다.
총 연결 비용과 최단 경로 거리
A-B 비용 2, B-C 비용 2, A-C 비용 3인 무방향 그래프를 생각해 보겠습니다. 전체 설치 비용을 최소화하려면 A-B와 B-C를 선택해 합 4로 연결합니다. 그러나 이 트리에서 A에서 C까지는 4가 들며 원래 직접 간선 3보다 멉니다.
최소 신장 트리(MST)는 모든 정점을 연결하는 트리 중 간선 비용 합이 최소인 것을 찾습니다. 한 출발점에서 각 정점까지 거리를 줄이는 최단 경로 트리와 목적이 다릅니다. 정점 V개의 트리는 V-1개 간선을 가지며 사이클이 없습니다. 비연결 그래프라면 하나의 트리가 없으므로 성분별 최소 신장 숲을 반환할지 오류로 볼지 정합니다.
선택 문제를 시작하기 전에 그래프가 무방향인지, 정점 전체를 연결할 수 있는지, 비용이 설치비인지 이동비인지 확인합니다. 설치비 합을 최소화하는 MST의 간선은 특정 두 정점 사이의 이동 거리까지 최소화하지 않으므로, “연결 비용”과 “사용자 경로 품질”을 하나의 숫자로 합치지 않는 것이 첫 번째 경계입니다.
Kruskal·Prim의 트리 확장 방식
예제 간선은 AB=1, BC=2, AC=3, CD=4, BD=5입니다. 무방향 간선이며 그림의 화살표 방향은 저장·표현을 위한 것일 뿐 통행 방향을 제한하지 않습니다.
그림을 글로 읽기
- A
- B
- C
- D
- A → B: 1
- B → C: 2
- A → C: 3
- C → D: 4
- B → D: 5
Kruskal은 전체 간선을 비용순으로 보며 서로 다른 성분을 연결합니다. Prim은 한 트리에서 시작해 그 트리와 바깥을 잇는 가장 싼 간선을 선택합니다.
| 단계 | Kruskal | A에서 시작한 Prim |
|---|---|---|
| 1 | AB=1로 A·B 병합 | A 밖으로 나가는 AB=1 선택 |
| 2 | BC=2로 C 병합 | {A,B}와 바깥을 잇는 BC=2 선택 |
| 3 | AC=3은 이미 연결되어 제외 | {A,B,C}에서 CD=4 선택 |
| 4 | CD=4로 D 병합 | 완료 |
이 예에서는 같은 순서가 나오지만 일반적으로 선택 순서는 다를 수 있습니다. 중요한 것은 총비용과 트리 조건입니다.
앞의 예를 상태로 추적하면 Kruskal은 {A},{B},{C},{D}에서 시작해 AB 후 {A,B}, BC 후 {A,B,C}, CD 후 하나의 성분이 됩니다. Prim은 현재 성분의 경계 후보만 관리합니다. 따라서 간선이 스트림처럼 정렬되어 들어오거나 전체 간선을 한 번에 다루기 쉬우면 Kruskal, 한 시작점에서 인접 후보를 점진적으로 확장하기 쉬우면 Prim을 우선 검토합니다.
컷을 가로지르는 최소 간선의 안전성
정점을 두 집합으로 나눈 경계를 컷이라고 합니다. 지금까지 선택한 간선들을 가로지르지 않는 컷에서 가장 싼 간선 e를 고르면 현재 선택과 e를 함께 포함하는 MST가 존재합니다.
현재 선택을 포함한 어떤 MST T가 e를 이미 포함하면 끝입니다. 포함하지 않으면 e를 추가할 때 사이클이 하나 생깁니다. 그 사이클에는 같은 컷을 가로지르는 다른 간선 f가 있습니다. e는 그 컷의 최소 간선이므로 weight(e)<=weight(f)입니다. f를 빼고 e를 넣으면 연결된 트리를 유지하면서 비용이 늘지 않습니다. 현재 선택 간선은 컷을 가로지르지 않으므로 f를 제거해도 기존 선택을 보존합니다.
이 교환 논증이 두 알고리즘의 근거입니다. 아무 컷의 최소 간선을 이미 강제한 선택과 무관하게 넣어도 된다는 뜻은 아닙니다. 컷이 기존 선택을 존중한다는 조건이 중요합니다.
Kruskal 간선 선택 코드
kruskal(vertices, edges):
require valid endpoints and finite weights
dsu = UnionFind(vertices)
chosen = []
total = 0
for edge in sort(edges, by=(weight, stableEdgeId)):
if dsu.union(edge.u, edge.v):
chosen.append(edge)
total = checked_add(total, edge.weight)
return {edges: chosen, cost: total, components: dsu.components}
자기 간선은 union이 false라 제외됩니다. 같은 두 정점을 잇는 여러 간선은 각각 후보로 다룰 수 있습니다. components>1이면 하나의 MST가 아니라 숲입니다. 음수 비용도 트리의 정의 안에서는 허용됩니다. Dijkstra의 비음수 조건을 MST에 그대로 옮기면 안 됩니다.
정렬 O(E log E)와 Union-Find 비용이 중심입니다. Prim의 인접 리스트·힙 구현은 보통 O(E log V) 형태로 설명하지만 지연 삭제로 중복 항목을 넣는 구현은 힙 크기와 다중 간선에 따라 상한을 더 명확히 써야 합니다. 조밀한 행렬에서는 매번 미선택 정점의 최소 연결 비용을 선형 탐색하는 O(V²) Prim이 힙 유지보다 단순하고 빠를 수 있습니다. 입력 표현·메모리 접근까지 측정해야 합니다.
실패 진단에서는 결과 간선 수가 V-1인지보다 먼저 components와 union 성공 횟수를 비교합니다. 입력에 잘못된 endpoint나 비유한 weight가 있으면 정렬 전에 거절하고, checked_add 실패는 MST 선택 오류가 아니라 비용 표현 범위 오류이므로 별도 오류로 노출해야 합니다.
간선 동점과 MST 유일성
삼각형의 세 간선이 모두 1이면 어떤 두 간선을 골라도 비용 2라 여러 MST가 있습니다. 반면 그래프 자체가 세 정점의 경로이고 두 간선 비용이 모두 1이라면 가능한 신장 트리가 그 하나뿐입니다. 모든 가중치가 서로 다르면 유일하지만, 동점이 있다는 사실은 비유일성의 충분조건이 아닙니다.
비용 뒤에 안정적인 간선 ID를 비교하면 결과 재현을 돕지만 최적성의 증명은 아닙니다. 테스트는 간선 집합 하나와만 비교하지 않고 연결성·사이클 부재·V-1개·총비용을 검사합니다.
간선 변경과 경로·컷 분석
새 간선 AD=2를 기존 트리 AB·BC·CD에 넣으면 A-B-C-D-A 사이클이 생깁니다. 그 사이클에서 가장 비싼 CD=4를 빼고 AD=2를 넣으면 연결성과 트리 조건은 유지되고 총비용은 7에서 5로 내려갑니다. 새 간선이 경로의 최대 간선보다 싸면 이 교환을 할 수 있고, 같으면 같은 비용의 다른 MST가 생기며, 더 비싸면 기존 트리를 유지하는 편이 낫습니다.
반대로 트리 간선 CD를 삭제하면 A-B-C와 D라는 두 성분이 생깁니다. 이제 두 성분을 가로지르는 남은 원본 간선을 살펴 가장 싼 것을 골라야 하며, 그런 간선이 없으면 그래프는 비연결입니다. 트리에 없던 간선 삭제는 현재 트리 자체를 바꾸지 않습니다. 기본 Union-Find만으로는 이 경로 최대 질의와 삭제 후 분리를 처리할 수 없으므로, 변화가 잦다면 동적 구조와 매번 재계산하는 비용을 비교해야 합니다.
새 간선의 양 끝이 기존 트리 안에 있으면 그 트리 경로의 최대 간선 하나만 비교하고, 기존 간선 삭제라면 삭제로 생긴 두 성분을 가로지르는 대체 간선을 다시 찾습니다. 이 두 경우를 같은 “변경 후 다시 union” 코드로 처리하면 삭제된 트리 간선을 복구하지 못하거나 경로 최대 조건을 놓칠 수 있습니다.
장애 내성과 MST 목적의 차이
트리의 간선은 모두 끊으면 분리되는 bridge입니다. 회선 하나를 잃어도 연결을 유지해야 한다면 MST만으로는 부족합니다. 여분 간선·독립 장애 영역·용량·최대 우회 거리를 제약으로 추가해야 합니다. 같은 MST를 두 번 계산한다고 독립 경로가 생기지는 않습니다.
작은 그래프에서는 V-1개 간선 조합을 전수 검사해 최적 비용을 비교할 수 있습니다. 음수·동점·고립 정점·평행 간선과 AD 추가 예를 검산하고, 장애 요구가 있으면 결과 간선을 하나씩 제거해 연결성을 다시 확인합니다. 설치 비용 최소화가 모든 운영 요구를 대신하지 않는다는 점까지 포함해야 올바른 답입니다.
작은 검증 실습에서는 MST를 만든 뒤 각 선택 간선을 차례로 제거해 연결성이 깨지는지 확인합니다. 모든 간선이 bridge라는 예측이 맞으면 MST의 구조는 검증되지만, 장애 한 번을 견디려는 요구에는 별도 여분 간선이 필요하다는 설계 결론도 함께 확인됩니다.