크루스칼 알고리즘은 간선을 가중치순으로 살피며 사이클을 만들지 않는 간선을 선택하는 최소 신장 트리 알고리즘이다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
원리
서로 다른 연결 요소를 잇는 간선만 채택한다. 서로소 집합 자료구조로 두 정점이 이미 연결되었는지 검사할 수 있다.
예시
가중치 1, 2, 5인 삼각형에서는 1과 2를 선택하면 모든 정점이 연결되므로 5인 간선은 제외한다.
주의할 점
간선 정렬 비용이 대체로 O(E log E)을 차지한다. 입력이 연결되지 않은 경우 선택 간선 수가 V−1에 도달하지 않는다.