빠른 비교
| 알고리즘 | 핵심 자료구조 | 잘 맞는 상황 |
|---|---|---|
| Kruskal | 간선 정렬 + 유니온-파인드 | 간선 목록이 주어짐 |
| Prim | 우선순위 큐 + 인접 리스트 | 한 정점에서 확장하기 쉬움 |
| 공통 조건 | 무방향 가중치 그래프 | 모든 정점 연결 |
| 결과 | 간선 수 V - 1 | 연결 비용 최소 |
csharp
edges.Sort((a, b) => a.cost.CompareTo(b.cost));
long total = 0;
int used = 0;
foreach ((int a, int b, int cost) in edges)
{
if (!Union(a, b)) continue;
total += cost;
used++;
if (used == n - 1) break;
}구조
최소 신장 트리는 그래프의 모든 정점을 연결하면서 간선 비용 합이 최소가 되는 트리입니다. 모든 정점을 연결해야 하므로 결과 간선 수는 V - 1개이고, 사이클은 포함하지 않습니다.
Kruskal은 가장 싼 간선부터 보면서 사이클을 만들지 않는 간선만 채택합니다. 사이클 여부는 유니온-파인드의 Union 성공 여부로 판단합니다.
text
1. 간선을 비용 오름차순 정렬
2. 싼 간선부터 확인
3. 이미 같은 집합이면 버림
4. 다른 집합이면 채택하고 합침Prim은 하나의 연결된 집합을 키워 갑니다. 현재 트리에서 바깥 정점으로 나가는 가장 싼 간선을 계속 고르는 방식입니다.
선택 기준
| 조건 | 선택 |
|---|---|
| 간선 목록 입력이 직접 주어짐 | Kruskal |
| 인접 리스트 중심으로 탐색하기 쉬움 | Prim |
| 그래프가 이미 연결되어 있는지 불명확 | MST 이후 간선 수 확인 |
| 모든 정점을 최소 비용으로 연결 | MST |
| 특정 두 정점 사이 최단 경로 | Dijkstra 등 최단 경로 |
MST의 “최소”는 전체 연결 비용 기준입니다. 두 정점 사이 경로가 항상 최단이라는 뜻은 아닙니다. 네트워크 설치 비용, 섬 연결, 도시 연결 문제처럼 전체 연결 비용을 줄이는 문제에 맞습니다.
주의할 점
그래프가 연결되어 있지 않으면 MST가 아니라 최소 신장 숲이 됩니다. Kruskal에서는 채택한 간선 수가 V - 1인지 확인하고, Prim에서는 방문한 정점 수를 확인해야 합니다.
MST는 무방향 그래프 기준입니다. 방향 간선에서 모든 정점을 연결하는 최소 구조는 별도 문제이며, 일반적인 Kruskal이나 Prim을 그대로 적용하면 안 됩니다.
참고 링크
2 sources