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

정의

최소 신장 트리 (Minimum Spanning Tree, MST) 는 연결 그래프 G = (V, E) 에서 모든 정점을 연결 하면서 간선 가중치 합이 최소 인 부분 그래프. 정확히 V - 1 개의 간선으로 이루어진 트리.

두 대표 알고리즘: Kruskal (간선 정렬 + Union-Find), Prim (정점 기준 greedy). 둘 다 O((E + V) log V) 또는 O(E log E).

문제 상황과 동기

N 개 도시를 연결하는 최소 비용 도로망, 네트워크 케이블 최소 길이 등.

• naive: 모든 spanning tree 탐색. 지수 개 존재 (Cayley’s formula: N 개 정점 완전 그래프는 N^(N-2) 개 spanning tree).
• Kruskal: 간선을 오름차순 정렬, 사이클 안 생기면 추가. O(E log E).
• Prim: 정점 하나에서 시작, 매번 최소 가중치 간선으로 확장. O((E + V) log V) with min-heap.

핵심 통찰: cut property (자른 두 집합 연결하는 최소 간선은 MST 에 포함) 와 cycle property (사이클 내 최대 간선은 MST 에 불필요).

시각화

핵심 아이디어

Cut Property

그래프를 S 와 V \ S 로 나누는 cut 에서, 두 집합 연결하는 간선 중 최소 가중치 간선 은 어떤 MST 에든 포함.

증명: MST T 가 그 간선 e 를 안 쓰면, T 의 S—(V\S) 경로의 어떤 간선 e’ 를 e 로 교체해도 더 작거나 같은 가중치. e 가 최소이므로 w(e) ≤ w(e’), 따라서 T 는 최소가 아니거나 e 를 포함 가능.

Cycle Property

사이클에서 최대 가중치 간선 은 MST 에 포함 안 됨.

증명: 사이클 내 최대 간선 e 를 빼도 여전히 연결됨. e 를 빼고 다른 간선으로 연결하면 가중치 합 감소 또는 동일.

Kruskal 알고리즘

1. 모든 간선을 가중치 오름차순 정렬.
2. 간선 하나씩 보면서, 사이클을 만들지 않으면 추가.
3. V - 1 개 간선 추가되면 종료.

사이클 여부는 Union-Find 로 O(α(V)) (amortized 상수).

Kruskal(G):
    T = ∅
    sort edges by weight
    for each edge (u, v, w) in sorted order:
        if find(u) != find(v):
            union(u, v)
            T = T ∪ {(u, v)}
    return T

Prim 알고리즘

1. 임의 정점 s 선택, S = {s}.
2. S 와 V \ S 를 잇는 최소 가중치 간선 (u, v) 선택 (u ∈ S, v ∉ S).
3. v 를 S 에 추가, (u, v) 를 MST 에 추가.
4. |S| = V 까지 반복.

min-heap 으로 O((E + V) log V).

Prim(G, s):
    dist[v] = ∞ for all v
    dist[s] = 0
    pq = {(0, s)}
    T = ∅
    while pq not empty:
        (d, u) = pq.pop()
        if u already visited: continue
        mark u as visited
        if parent[u] exists: T = T ∪ {(parent[u], u)}
        for each (u, v, w):
            if dist[v] > w and v not visited:
                dist[v] = w
                parent[v] = u
                pq.push((w, v))
    return T

구현

Kruskal (Union-Find)

// Kruskal, Union-Find
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w; };
int parent[100001];
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int x, int y) {
  x = find(x); y = find(y);
  if (x == y) return false;
  parent[x] = y; return true;
}
int main() {
  int V, E; cin >> V >> E;
  vector<Edge> edges(E);
  for (auto& [u, v, w] : edges) cin >> u >> v >> w;
  sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w < b.w; });
  for (int i = 1; i <= V; i++) parent[i] = i;
  long long total = 0; int cnt = 0;
  for (auto [u, v, w] : edges) {
      if (unite(u, v)) {
          total += w;
          if (++cnt == V - 1) break;
      }
  }
  cout << total << "\n";
}

# Kruskal, Union-Find
import sys
input = sys.stdin.readline
​
def find(x):
  if parent[x] != x:
      parent[x] = find(parent[x])
  return parent[x]
​
def unite(x, y):
  x, y = find(x), find(y)
  if x == y: return False
  parent[x] = y
  return True
​
V, E = map(int, input().split())
edges = []
for _ in range(E):
  u, v, w = map(int, input().split())
  edges.append((w, u, v))
edges.sort()
parent = list(range(V + 1))
total = 0
cnt = 0
for w, u, v in edges:
  if unite(u, v):
      total += w
      cnt += 1
      if cnt == V - 1: break
print(total)

// Kruskal, Union-Find
import java.util.*;
import java.io.*;
class Edge implements Comparable<Edge> {
  int u, v, w;
  Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
  public int compareTo(Edge o) { return this.w - o.w; }
}
public class Main {
  static int[] parent;
  static int find(int x) {
      if (parent[x] != x) parent[x] = find(parent[x]);
      return parent[x];
  }
  static boolean unite(int x, int y) {
      x = find(x); y = find(y);
      if (x == y) return false;
      parent[x] = y; return true;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int V = Integer.parseInt(st.nextToken());
      int E = Integer.parseInt(st.nextToken());
      Edge[] edges = new Edge[E];
      for (int i = 0; i < E; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());
          edges[i] = new Edge(u, v, w);
      }
      Arrays.sort(edges);
      parent = new int[V + 1];
      for (int i = 1; i <= V; i++) parent[i] = i;
      long total = 0; int cnt = 0;
      for (Edge e : edges) {
          if (unite(e.u, e.v)) {
              total += e.w;
              if (++cnt == V - 1) break;
          }
      }
      System.out.println(total);
  }
}

4 5
1 2 2
1 3 3
2 3 1
2 4 5
3 4 4

7

Prim (priority_queue)

// Prim, min-heap
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
  int V, E; cin >> V >> E;
  vector<vector<pii>> adj(V + 1);
  for (int i = 0; i < E; i++) {
      int u, v, w; cin >> u >> v >> w;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
  }
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  vector<bool> vis(V + 1, false);
  pq.push({0, 1});
  long long total = 0;
  while (!pq.empty()) {
      auto [w, u] = pq.top(); pq.pop();
      if (vis[u]) continue;
      vis[u] = true;
      total += w;
      for (auto [v, ww] : adj[u]) {
          if (!vis[v]) pq.push({ww, v});
      }
  }
  cout << total << "\n";
}

# Prim, heapq
import heapq
import sys
input = sys.stdin.readline
​
V, E = map(int, input().split())
adj = [[] for _ in range(V + 1)]
for _ in range(E):
  u, v, w = map(int, input().split())
  adj[u].append((v, w))
  adj[v].append((u, w))
​
pq = [(0, 1)]
vis = [False] * (V + 1)
total = 0
while pq:
  w, u = heapq.heappop(pq)
  if vis[u]: continue
  vis[u] = True
  total += w
  for v, ww in adj[u]:
      if not vis[v]:
          heapq.heappush(pq, (ww, v))
print(total)

4 5
1 2 2
1 3 3
2 3 1
2 4 5
3 4 4

7

복잡도

E = O(V^2) 이면 Kruskal O(V^2 log V), Prim O(V^2 log V) 비슷. E = O(V) 이면 Kruskal 이 빠름.

변형 / 활용

최대 신장 트리 (Maximum Spanning Tree)

간선 가중치 음수로 뒤집거나, 정렬 역순.

두 번째 MST

MST T 의 각 간선 e 를 빼고 다시 MST 구하기. O(V (E log E)).

MST 유일성

가중치가 모두 다르면 MST 유일. 같은 가중치가 있으면 여러 MST 가능. 정렬 안정성 (stable sort) 으로 사전순 최소 MST.

Borůvka 알고리즘

병렬화 가능. 각 컴포넌트가 동시에 최소 간선 선택. O(E log V), 실무는 거의 안 씀.

함정

1. 방향 그래프

MST 는 무방향 그래프 전용. 방향 그래프는 최소 신장 아보레센스 (Minimum Spanning Arborescence), Edmonds’ algorithm O(VE).

2. 연결되지 않은 그래프

컴포넌트가 여러 개면 MST 존재 안 함. 최소 신장 숲 (Minimum Spanning Forest) 으로 일반화.

3. Kruskal 에서 정렬 누락

sort(edges) 빼먹으면 greedy 보장 안 됨.

4. Prim 에서 중복 push

vis[u] 체크 안 하면 같은 노드 여러 번 pop, 시간 초과.

5. 가중치 오버플로우

int 합이 넘으면 long long.

BOJ 연습 문제

참고

• Union-Find
• 크루스칼 알고리즘
• 프림 알고리즘
• 신장 트리