1. 최소 비용 신장 트리, 최소 신장 트리 구조
(Minimum Cost Spanning Tree, Minimum Spanning Tree, MST)
ㅇ 가중 무방향 그래프에서, ☞ 그래프 종류 (가중치 그래프, 무방향 그래프)참조
ㅇ 구성가능한 다수의 신장 트리 중에,
ㅇ 가중치 합이 최소인 것
2. 최소비용 신장트리 생성 알고리즘 (Minimum Spanning Tree, MST)
ㅇ 신장 트리의 생성
- 주어진 그래프에서, 정점들은 모두 포함하면서, 사이클(루프 순환)을 없애는 것
ㅇ 최소 신장 트리의 생성
- 주어진 그래프에서, 모든 임의 경로의 가중치 합이 최소가 되도록, 신장 트리를 만드는 것
ㅇ 최소 신장 트리의 알고리즘 전략 : 탐욕 알고리즘에 속함
- 각 단계 마다 그 순간에 가장 좋은 것(최소 가중치 간선)을 선택하게 됨
※ [참고] ☞ 탐욕 알고리즘, 그래프 알고리즘, 스패닝 트리 프로토콜 참조
3. MST 알고리즘의 대표적인 例)
ㅇ 프림 알고리즘 (Prim Algorithm)
- 하나의 정점을 시작으로 트리를 점차 확장시켜가며 신장 트리를 만들어감
. 임의 정점부터 시작하며,
. 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가하고,
. 루프를 만들지 않으면서,
. 점차 선택된 정점들에 부속된 연결선들 중 최소 가중치 연결선을 추가하면서,
. 최소 신장트리가 완성됨
- 최단 경로를 찾는, 다익스트라 알고리즘과 유사하게 동작
ㅇ 크루스칼 알고리즘 (Kruskal Algorithm)
- 루프를 만들지 않으면서도, 최소 가중치를 갖는 연결선을 하나씩 추가하며, 신장트리 작성
. 가중치로 간선을 정렬한 후, 사이클이 형성되지 않도록 하며,
. 간선을 하나씩 선택 또는 삭제하며 신장트리를 만들어감
- 순환을 피하며 단순히 그 시점에 최소 가중치를 갖는 연결선을 선택하며,
. 연결선 단위로 신장 트리를 구축하는 탐욕 알고리즘 접근법
- 최초에는 연결선이 전혀 없는 n개 개별 정점, n개 개별 트리로부터 시작
. n-1개 연결선을 더하고 나면 모든 트리가 합쳐져서 하나의 신장 트리가 됨