[자료구조] 최소 비용 신장 트리(Minimum-cost Spanning Tree)

신장 트리(Spanning Tree)

G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리이다.

최소 비용 신장 트리(Minimum-cost Spanning Tree)

최소 비용 신장 트리란 최저의 비용을 갖는 신장 트리이다.

 

연결 무방향 그래프에서 최소 비용 신장 트리를 구하기 위해서는 세 가지 상이한 알고리즘을 사용할 수 있다.

모두 갈망법(greedy method)이라고 하는 설계 전략을 사용하고 있다.

 

<세 가지 알고리즘>

1. Kruskal 알고리즘
2. Prim 알고리즘
3. Solin 알고리즘

<제한 조건>

1. 그래프 내에 있는 간선들만을 사용해야 한다.
2. 정확하게 n-1개의 간선만을 사용해야 한다.
3. 사이클을 생성하는 간선을 사용해서는 안 된다.

탐욕 알고리즘(Greedy Algorithm)

매 순간 최적의 해를 단계별로 도출한다.

각 단계에서는 판단 기준에 따라 최상의 결정을 선택한다. 단, 한 번 내려진 결정은 번복 불가능하다.

최종적인 최적해에 도달한다.

 

<탐욕 알고리즘이 잘 작동하는 조건>

 

1. 탐욕스런 선택 조건 (Greedy choice property)

• 앞의 선택이 이후의 선택에 영향을 주지 않음

 

2. 최적 부분 구조 조건 (Optimal substructure)

• 문제에 대한 최적해가 부분 문제에 대해서도 최적해

 

Kruskal 알고리즘

방법 1) 가중치가 가장 낮은 간선을 하나씩 T에 추가

방법 2) 가중치가 가장 높은 간선을 하나씩 T에서 제거

 

위의 과정을 반복하다가 최소 비용 신장 트리가 구축되면 종료한다.

G가 연결되어 있고, n>0개의 정점을 가지므로 정확하게 n-1개의 간선이 T에 포함된다.

Pseudo code

T = ∅
while ((T가 n-1개 미만의 간선을 포함) && (E가 공백이 아님)) {
	E에서 최소 비용 간선 (v,w) 선택;
	E에서 (v,w)를 삭제;
	if (v,w)가 T에서 사이클을 만들지 않으면 T에 (v,w)를 추가;
	else discard (v,w);
	}
if (T가 n-1개 미만의 간선을 포함) cout << "신장 트리 없음" << endl;

 

Prime 알고리즘

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

• 그래프에서 시작 정점을 선택한다.
• 선택한 정점에서 부속된 간선들 중에서 가중치가 가장 작은 간선을 연결하여 트리를 확장한다.
• 이전에 선택한 정점과 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 삽입한다.
• 그래프에 n-1개의 간선이 포함될 때까지 추가 단계를 반복한다.