[자료구조] 최소 비용 신장 트리

 

 

신장트리

n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

 

- 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용하여 생성된 신장 트리

- 너비 우선 신장 트리 : 너비 우선 탐색을 이용하여 생성된 신장 트리

 

최소 비용 신장 트리

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리

최소 비용 신장 트리를 만드는 알고리즘

 

- Kruskal 알고리즘

- Prime 알고리즘

 

Kruskal 알고리즘 Ⅰ

가중치가 높은 간선을 제거

1. 그래프에서 모든 간선을 가중치에 따라 내림차순으로 정리

2. 그래프에서 가중치가 가장 높은 간선을 제거

 - 이때 정점을 그래프에서 분리시키는 간선을 제거할 수 없으므로 그 다음으로 가중치가 높은 간선 제거

3. 그래프에 n-1개의 간선만 남을 때까지 2를 반복

4. 그래프에 n-1개의 간선이 남게 되면 최소 비용 신장 트리 완성

 

Kruskal 알고리즘 Ⅱ

가중치가 낮은 간선 삽입

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정리

2. 그래프에 가중치가 가장 작은 간선을 삽입

 - 이때 사이클을 형성하는 간선을 삽입할 수 없으므로 그 다음으로 가중치가 작은 간섭 삽입

3. 그래프에 n-1개의 간선을 삽입할 때까지 2 반복

4. 그래프의 간선이 n-1개가 되면 최소 비용 신장 트리 완성

 

Prime 알고리즘

간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법

1. 그래프에서 시작 정점을 선택

2. 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간서을 연결하여 트리를 확장

3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선 삽입

 - 이때 사이클을 형성하는 간선을 삽입할 수 없으므로 그 다음으로 가중치가 작은 간선 선택

4. 그래프에 n-1개의 간선을 삽입할 때까지 3 반복

5. 그래프의 간선이 n-1개가 되면 최소 비용 신장 트리 완성