최소 신장 트리는 연결된 무방향 가중 그래프의 모든 정점을 연결하면서 간선 가중치 합을 최소로 하는 트리이다.
원리
V개 정점을 연결하는 신장 트리는 V−1개 간선을 가진다. 크루스칼과 프림 알고리즘이 대표적인 구성 방법이다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
예시
여러 건물을 연결하는 케이블 총길이를 줄이는 모형에 쓸 수 있다. 한 건물에서 각 건물까지의 이동 거리를 모두 최소화하는 문제와는 다르다.
주의할 점
그래프가 연결되지 않았다면 전체 신장 트리는 없고 각 연결 요소의 최소 신장 숲을 구할 수 있다.