Spanning Tree, MST: 최소 신장 트리

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

정의

Spanning Tree 는 그래프의 모든 정점을 포함하는 부분 트리. MST (Minimum Spanning Tree) 는 간선 가중치 합이 최소인 spanning tree.

Kruskal

간선을 가중치 오름차순 정렬, Union-Find 로 사이클 만들지 않는 간선을 그리디하게 추가.

sort(edges.begin(), edges.end());
DSU dsu(n);
long long total = 0;
for (auto [w, u, v] : edges) {
    if (dsu.merge(u, v)) total += w;
}

O(E log E).

Prim

한 정점에서 시작, 최소 가중치 간선을 priority queue 로 반복 확장.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
vector<bool> vis(n);
pq.push({0, 0});
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, ew] : adj[u]) if (!vis[v]) pq.push({ew, v});
}

O(E log V).

Borůvka

병렬화 좋음. 각 컴포넌트에서 최소 outgoing edge 를 동시 선택, 반복.

참고

• Union-Find (Kruskal)
• Priority Queue (Prim)
• Shortest Path (다름 유의)