10장 트리(신장 트리, 최소 비용 신장 트리)

신장 트리

n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어져 사이클이 없는 단순 연결 그래프를 신장 트리라고 한다. 깊이 우선 탐색을 이용하여 생성된 깊이 우선 신장 트리와 너비 우선 탐색을 이용하여 생성된 너비 우선 신장 트리가 있다.

최소 비용 신장 트리

무방향 가중치 그래프에서 가중치의 합이 쵯소인 신장 트리를 최소 비용 신장 트리라고 한다. 최소 비용 신장 트리를 만들기 위해 Kruskal이 만든 알고리즘과 Prime이 만든 알고리즘을 사용한다.

Kruskal

Kruskal 알고리즘은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 Kruskal 알고리즘1 과 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 Kruskal 알고리즘2 가 있다.

1. Kruskal 알고리즘1

(1) 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정리한다. (2) 그래프 G에서 가중치가 높은 간선을 제거한다.     이때 정점을 그래프에서 분리시크는 간선은 제거할 수 없다.     이런 경우에는 그 다음으로 가중치가 높은 간선을 제거한다. (3) 그래프 G에 n-1개의 간선만 남을 때까지 (2)를 반복한다. (4) 그래프 n-1개의 간선이 남게 되면 최소 비용 신장 트리가 완성된다.

1. 그래프 정점이 7개 이므로 최소 비용 신장 트리는 6개의 간선을 갖는다. 내림차순(초기상태)

2. 가중치가 가장 큰 간선 (A, C)를 제거한다.

3. 남은 간선 중에서 가중치가 가장 큰 간선 (F, C)를 제거한다. (규칙에따라 반복한다.)

4. 남은 간선 중에서 가중치가 가장 큰 간선 (D, E)를 제거해야되지만 그러면 그래프가 단절되므로 다음 (C, F)로 이동한다. 그런데 (C, F)도 제거하면 그래프가 단절되므로 다음 (A, D)를 제거한다. 남은 간선 6개(7-1) 이므로 종료한다.

2. Kruskal 알고리즘2

(1) 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다. (2) 그래프 G에서 가중치가 가장 작은 간선을 삽입한다.     이때 사이클을 형성하는 간선은 삽입할 수 없다.     이런 경우에는 그 다음으로 가중치가 작은 간선을 삽입한다. (3) 그래프 G에 n-1개의 간선을 삽입할 때까지 (2)를 반복한다. (4) 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.

1. 그래프 G10의 간선을 가중치에 따라 오름차순으로 정렬한다.

2. 가중치가 가장 작은 간선 (E, G)를 삽입한다.

3. 나머지 간선 중에서 가중치가 가장 작은 간선 (A, B)를 삽입한다. (룰에따라 반복한다.)

4. 나머지 간선 중에서 가중치가 가장 작은 간선 (A, D)를 삽입하면 A-B-D-A의 사이클이 생성되므로 생성할 수 없다. 그 다음으로 가중치가 가장 작은 간선 (C, F)를 삽입한다.

5. 나머지 간선 중에서 가중치가 가장 작은 간선 (D, E)를 삽입한다. 간선 수가 6개(7-1) 이므로 종료한다.

Prime

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

(1) 그래프 G에서 시작 정점을 선택한다. (2) 선택ㅎ한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 연결하여 트리를 확장한다. (3) 이전에 선택한 정점과 새로 확장한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 삽입한다.     이때 사이클을 형성하는 간선은 삽입할 수 없다.     이런 경우에는 그 다음으로 가중치가 가장 작은 간선을 선택하여 삽입한다. (4) 그래프 G에 n-1개의 간선을 삽입할 때까지 (3)을 반복한다. (5) 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.

1. 그래프 G의 정점 중에서 정점 A를 정점으로 선택한다.

2. 정점 A에 부속된 간선 중에서 가중치가 가장 작은 간선 (A, B)를 삽입하여 트리를 확장한다.

3. 현재 확장된 트리의 정점 A, B에 부속된 간선 중에서 가중치가 가장 작은 간선 (B, D)를 삽입하여 트리를 확장한다.

4. 현재 확장된 트리의 정점 A, B, D에 부속된 간선 중에서 가중치가 가장 작은 간선 (A, D)를 삽입하면 A-B-D-A의 사이클이 생성되므로 할수 없다. 그 다음 가장 작은 간선 (D, E)를 삽입한다.(룰에 따라 반복한다.)

5. 현재 확장된 트리의 정점 A, B, D, E, F, G에 부속된 간선 중에서 가중치가 가장 작은 간선 (C, F)를 삽입하여 트리를 확장한다. 간선 수 6(7-1)이므로 종료한다.