최소 신장 트리(크루스칼·프림) 계산기
간선 목록을 넣으면 크루스칼과 프림이 각각 어떤 순서로 간선을 고르는지 단계별로 보여 주고 총 비용을 냅니다. 두 답이 왜 순서는 달라도 합은 같은지, MST가 유일한지까지 판정합니다.
한 줄에 「정점 정점 가중치」. 방향은 없는 것으로 보고 80개까지 다룹니다.
최소 신장 트리 총 비용
37
정점 9개를 잇는 간선 8개의 합입니다. 크루스칼과 프림의 답이 같습니다.
① 크루스칼 — 싼 간선부터, 사이클이 안 생기면 넣는다
| 간선 | 가중치 | 판정 | 누적 비용 | 남은 덩어리 |
|---|---|---|---|---|
| g–h | 1 | 넣는다 | 1 | 8 |
| f–g | 2 | 넣는다 | 3 | 7 |
| c–i | 2 | 넣는다 | 5 | 6 |
| a–b | 4 | 넣는다 | 9 | 5 |
| c–f | 4 | 넣는다 | 13 | 4 |
| i–g | 6 | 사이클 — 버린다 | 13 | 4 |
| c–d | 7 | 넣는다 | 20 | 3 |
| i–h | 7 | 사이클 — 버린다 | 20 | 3 |
| b–c | 8 | 넣는다 | 28 | 2 |
| h–a | 8 | 사이클 — 버린다 | 28 | 2 |
| d–e | 9 | 넣는다 | 37 | 1 |
| e–f | 10 | 사이클 — 버린다 | 37 | 1 |
| b–h | 11 | 사이클 — 버린다 | 37 | 1 |
| d–f | 14 | 사이클 — 버린다 | 37 | 1 |
사이클 판정은 유니온-파인드로 합니다. 두 끝점의 «뿌리»가 같으면 이미 이어져 있다는 뜻이라 그 간선은 사이클을 만듭니다. 간선을 하나 받을 때마다 덩어리가 하나씩 줄고, 1이 되는 순간 나무가 완성됩니다.
② 프림 — 한 점에서 시작해 밖으로 나가는 가장 싼 간선을 붙인다
| 차례 | 고른 간선 | 가중치 | 들어온 정점 | 누적 비용 |
|---|---|---|---|---|
| 0 | 시작 | — | a | 0 |
| 1 | a–b | 4 | b | 4 |
| 2 | b–c | 8 | c | 12 |
| 3 | c–i | 2 | i | 14 |
| 4 | c–f | 4 | f | 18 |
| 5 | f–g | 2 | g | 20 |
| 6 | g–h | 1 | h | 21 |
| 7 | c–d | 7 | d | 28 |
| 8 | d–e | 9 | e | 37 |
프림이 고르는 순서는 가중치 오름차순이 아닙니다 — 「지금 나무에서 나가는 것」 중에서만 고르기 때문입니다. 그래도 합은 크루스칼과 같습니다. 시작 정점을 바꿔 보면 순서가 달라지지만 총 비용은 그대로입니다.
계산 방법
- 1간선을 한 줄에 하나씩 「정점 정점 가중치」 형식으로 넣습니다. 방향은 없는 것으로 봅니다.
- 2크루스칼 표에서 간선을 싼 것부터 훑으며 사이클이 되는 간선을 버리는 과정을 확인합니다.
- 3프림의 시작 정점을 바꿔 가며 선택 «순서»는 달라져도 총 비용은 그대로임을 확인합니다.
- 4MST가 유일한지 판정 결과를 보고, 여럿이면 어떤 간선끼리 맞바꿀 수 있는지 확인합니다.
자주 묻는 질문
총 비용이 같다면 둘 다 맞습니다. 두 알고리즘은 간선을 고르는 순서가 다를 뿐이고, 가중치 합은 언제나 같습니다. 크루스칼은 간선을 싼 것부터 훑으며 사이클이 안 생기면 넣고, 프림은 한 정점에서 출발해 나무 밖으로 나가는 가장 싼 간선을 붙여 나갑니다. 고른 간선 «집합»까지 같을 수도 다를 수도 있는데, 다르다면 그 그래프에 최소 신장 트리가 여러 개 있다는 뜻입니다.
가중치가 모두 다르면 하나뿐이고, 같은 값이 섞이면 여럿일 수 있습니다. 정확한 판정은 나무에 없는 간선마다 그 양끝을 잇는 나무 위 경로에서 가장 무거운 간선을 보는 것입니다. 그 값이 새 간선의 가중치와 같으면 둘을 맞바꾼 다른 최소 신장 트리가 있습니다. 가중치가 겹쳐도 서로 다른 컷에 있으면 맞바꿀 수 없어 여전히 유일합니다.
신장 트리가 아니라 신장 숲이 됩니다. 모든 정점을 하나로 묶는 것이 애초에 불가능하므로, 크루스칼은 덩어리마다 최소 신장 트리를 만들고 간선을 「정점 수 − 덩어리 수」개 고릅니다. 프림은 시작 정점이 속한 덩어리만 덮고 나머지 정점에는 닿지 못합니다.
그보다 적으면 끊기고 많으면 사이클이 생기기 때문입니다. 정점 n개를 사이클 없이 모두 잇는 그래프는 언제나 간선이 n−1개이며, 이것이 트리의 정의이기도 합니다. 이 계산기는 고른 간선 수를 함께 보여 주므로 n−1인지 바로 확인할 수 있습니다.
이 계산기는 입력에 먼저 적힌 간선을 먼저 봅니다. 규약을 밝히지 않으면 같은 자료에서도 선택 순서가 재현되지 않기 때문입니다. 총 비용은 어느 쪽을 먼저 고르든 같으므로, 교재의 순서와 달라도 합이 같으면 틀린 것이 아닙니다.
됩니다. 최소 신장 트리는 음수 가중치가 있어도 그대로 성립합니다. 최단경로의 다익스트라가 음수에서 무너지는 것과 다른데, 크루스칼과 프림은 「경로의 합」이 아니라 「컷을 가로지르는 가장 싼 간선」만 보기 때문입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 CLRS「Introduction to Algorithms」Figure 23.4의 그래프(정점 9개·간선 14개, 총 비용 37)를 정답지로 삼았습니다. 무작위 연결 그래프 300벌에서 모든 시작 정점의 프림 결과가 크루스칼과 같은 합을 내는지도 대조했습니다.
- 방향은 없는 것으로 봅니다. 「a b 4」와 「b a 4」는 같은 간선이며, 방향 그래프의 최소 신장 트리(최소 신장 수목, arborescence)는 추마-류/에드먼즈 알고리즘이 필요한 다른 문제입니다.
- 자기 자신을 잇는 간선은 언제나 사이클이라 빼고 계산합니다. 같은 두 정점을 잇는 간선이 여럿이면 그대로 두고 싼 것이 먼저 뽑히게 둡니다.
- MST가 유일한지 판정할 때 「가중치가 겹치면 유일하지 않다」로 답하는 자료가 많은데 그것은 틀립니다. 겹쳐도 서로 다른 컷에 있으면 맞바꿀 수 없습니다. 예제 버튼 가운데 이 경우를 확인할 수 있는 자료를 넣어 두었습니다.
- 간선 80개·정점 40개까지 다룹니다. 과정을 표로 보이는 것이 목적이라 그보다 크면 읽히지 않습니다. 프림은 우선순위 큐 없이 매번 훑는 O(VE) 구현이라 큰 그래프에는 맞지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.