그래프 이론에서 최소 신장 트리(MST, Minimum Spanning Tree) 는
모든 정점을 연결하면서 간선의 가중치 합이 최소가 되도록 하는 트리이다.
이때 대표적으로 사용되는 두 가지 알고리즘이 바로
👉 프림(Prim) 과 크루스칼(Kruskal) 알고리즘이다.
🌱 1️⃣ 프림 알고리즘 (Prim’s Algorithm)
프림 알고리즘은 정점(vertex) 중심으로 확장하는 방식이다.
하나의 시작 정점에서 출발하여, 연결된 간선 중 가중치가 가장 작은 간선을
하나씩 추가해 나가면서 트리를 확장한다.
📊 아래 그림처럼, 하나의 정점(초록색)에서 시작해
인접한 간선들 중 가장 비용이 작은 간선을 선택하며 트리를 확장한다.
⚙️ 동작 과정
- 임의의 정점 하나를 선택 (시작점)
- 현재 트리와 연결된 간선 중 가중치가 최소인 간선 선택
- 해당 간선이 연결하는 새로운 정점을 트리에 추가
- 모든 정점이 포함될 때까지 2~3 과정을 반복
💡 특징
- 정점 중심 확장 방식
- 항상 하나의 연결 그래프를 유지
- 우선순위 큐(힙)를 사용하면
O(E log V)시간복잡도 - 조밀한 그래프(Dense Graph) 에서 효율적
⚖️ 2️⃣ 크루스칼 알고리즘 (Kruskal’s Algorithm)
크루스칼 알고리즘은 간선(edge) 중심의 접근이다.
그래프의 모든 간선을 가중치 오름차순으로 정렬한 뒤,
사이클이 생기지 않도록 하나씩 선택해 트리를 만든다.
📊 아래 그림은 크루스칼 알고리즘이
가장 짧은 간선부터 하나씩 선택하며 트리를 완성하는 과정을 보여준다.
(빨간색 간선은 현재 선택된 간선)
⚙️ 동작 과정
- 모든 간선을 가중치 기준으로 오름차순 정렬
- 정렬된 간선부터 하나씩 선택
- 선택된 간선이 사이클을 만들지 않으면 트리에 포함
- 모든 정점이 연결되면 종료
이때 사이클 여부는 Union-Find(Disjoint Set) 자료구조로 효율적으로 검사한다.
💡 특징
- 간선 중심 선택 방식
- 트리를 점차 연결하며 확장
O(E log E)시간복잡도 (간선 정렬 과정)- 희소 그래프(Sparse Graph) 에서 효율적
📊 3️⃣ 프림 vs 크루스칼 비교
| 구분 | 프림 (Prim) | 크루스칼 (Kruskal) |
|---|---|---|
| 접근 방식 | 정점 중심 | 간선 중심 |
| 구현 방식 | 인접 정점 중 최소 간선 선택 | 전체 간선 정렬 후 선택 |
| 사용 자료구조 | 우선순위 큐 (힙) | Union-Find |
| 시간 복잡도 | O(E log V) | O(E log E) |
| 효율적 그래프 | 조밀한 그래프(Dense) | 희소한 그래프(Sparse) |
| 사이클 검사 | 필요 없음 (자동 보장) | Union-Find로 검사 |
🧠 정리하자면
- 프림 알고리즘은 “정점에서 시작해 나아가는 방식”
- 크루스칼 알고리즘은 “간선부터 연결해 나가는 방식”
- 둘 다 결과적으로 최소 비용의 신장 트리(MST) 를 구하지만,
그래프의 밀도나 구현 방식에 따라 적합한 알고리즘이 다르다.
💬 한 줄 요약!!!
🔹 프림: "하나의 점에서 뻗어나가는 나무"
🔹 크루스칼: "가장 짧은 다리를 하나씩 놓아가는 연결망"
다음 시간에는 벨만 포드 알고리즘과 다익스트라 알고리즘을 비교할 예정이다~!
