Quick Comparison
| 알고리즘 | 핵심 자료구조 | 잘 맞는 상황 |
|---|---|---|
| Kruskal | 간선 정렬 + 유니온-파인드 | 간선 목록이 주어짐 |
| Prim | 우선순위 큐 + 인접 리스트 | 한 정점에서 확장하기 쉬움 |
| 공통 조건 | 무방향 가중치 그래프 | 모든 정점 연결 |
| 결과 | 간선 수 V - 1 | 연결 비용 최소 |
static (long Cost, int UsedEdges) Kruskal(
int vertexCount,
List<(int From, int To, long Cost)> edges)
{
if (vertexCount < 0) throw new ArgumentOutOfRangeException(nameof(vertexCount));
if (vertexCount == 0) return (0, 0);
var sets = new DisjointSet(vertexCount);
edges.Sort((a, b) => a.Cost.CompareTo(b.Cost));
long total = 0;
int used = 0;
foreach ((int from, int to, long cost) in edges)
{
if (!sets.Union(from, to)) continue;
total = checked(total + cost);
used++;
if (used == vertexCount - 1) break;
}
return (total, used);
}DisjointSet은 유니온-파인드 카드의 0-based 구현처럼 Find와 Union을 제공해야 합니다. 정점이 하나 이상일 때 UsedEdges == vertexCount - 1인지 확인해 연결된 MST와 최소 신장 숲을 구분합니다.
MST는 두 정점 사이 최단 경로가 아니라 모든 정점을 연결하는 전체 비용을 최소화합니다. 그래프가 끊어져 있으면 결과는 MST가 아닌 최소 신장 숲입니다.
구조
최소 신장 트리는 그래프의 모든 정점을 연결하면서 간선 비용 합이 최소가 되는 트리입니다. 모든 정점을 연결해야 하므로 결과 간선 수는 V - 1개이고, 사이클은 포함하지 않습니다.
Kruskal은 가장 싼 간선부터 보면서 사이클을 만들지 않는 간선만 채택합니다. 사이클 여부는 유니온-파인드의 Union 성공 여부로 판단합니다.
1. 간선을 비용 오름차순 정렬
2. 싼 간선부터 확인
3. 이미 같은 집합이면 버림
4. 다른 집합이면 채택하고 합침Prim은 하나의 연결된 집합을 키워 갑니다. 현재 트리에서 바깥 정점으로 나가는 가장 싼 간선을 계속 고르는 방식입니다.
static (long Cost, int UsedEdges) Prim(IReadOnlyList<(int To, long Cost)>[] graph, int start)
{
if ((uint)start >= (uint)graph.Length) throw new ArgumentOutOfRangeException(nameof(start));
var visited = new bool[graph.Length];
var queue = new PriorityQueue<(int Vertex, long Cost), long>();
queue.Enqueue((start, 0), 0);
long total = 0;
int usedEdges = 0;
while (queue.TryDequeue(out var candidate, out _))
{
if (visited[candidate.Vertex]) continue;
visited[candidate.Vertex] = true;
total = checked(total + candidate.Cost);
if (candidate.Vertex != start) usedEdges++;
foreach ((int next, long cost) in graph[candidate.Vertex])
{
if (!visited[next]) queue.Enqueue((next, cost), cost);
}
}
return (total, usedEdges);
}UsedEdges == graph.Length - 1이면 모든 정점이 연결된 MST이고, 더 작으면 start가 속한 연결 요소의 비용만 구한 것입니다. 음수 가중치도 MST에서는 사용할 수 있으며, 같은 비용의 간선이 있으면 MST가 여러 개일 수 있습니다.
선택 기준
| 조건 | 선택 |
|---|---|
| 간선 목록 입력이 직접 주어짐 | Kruskal |
| 인접 리스트 중심으로 탐색하기 쉬움 | Prim |
| 그래프가 이미 연결되어 있는지 불명확 | MST 이후 간선 수 확인 |
| 모든 정점을 최소 비용으로 연결 | MST |
| 특정 두 정점 사이 최단 경로 | Dijkstra 등 최단 경로 |
MST의 “최소”는 전체 연결 비용 기준입니다. 두 정점 사이 경로가 항상 최단이라는 뜻은 아닙니다. 네트워크 설치 비용, 섬 연결, 도시 연결 문제처럼 전체 연결 비용을 줄이는 문제에 맞습니다. 간선 비용과 최대 간선 수를 곱해 합계가 int를 넘을 수 있으면 long으로 누적합니다.
주의할 점
그래프가 연결되어 있지 않으면 MST가 아니라 최소 신장 숲이 됩니다. Kruskal에서는 채택한 간선 수가 V - 1인지 확인하고, Prim에서는 방문한 정점 수를 확인해야 합니다.
MST는 무방향 그래프 기준입니다. 방향 간선에서 모든 정점을 연결하는 최소 구조는 별도 문제이며, 일반적인 Kruskal이나 Prim을 그대로 적용하면 안 됩니다.
참고 링크
2 sources