visited[i]
8.4 그래프의 트리화
8.4.1 신장 트리
8.4.2 최소 비용 신장 트리
8.4.1 신장 트리 (1)
• 신장 트리(spanning tree)
• 그래프 G에서 E(G)에 있는 간선과 V(G)에 있는 모든 정점들 로 구성된 트리
• DFS, BFS에 사용된 간선 집합 T는 그래프 G의 신장 트리를 의미
• 주어진 그래프 G에 대한 신장 트리는 유일하지 않음
(a) 연결 그래프 G (b) 신장 트리 그래프 G에 대한 3개의 신장 트리
8.4.1 신장 트리 (2)
• 신장 트리의 종류
• 깊이 우선 신장 트리(depth first spanning tree) : DFS 사 용
• 너비 우선 신장 트리(breadth first spanning tree) : BFS 사용
0
1 3
2
4 5
6
(a) 연결 그래프 G
0
1 3
2
4 5
6
(b) DFS(0) 신장 트리
0
1 3
2
4 5
6
(c) BFS(0) 신장 트리 연결 그래프 G와 신장 트리
8.4.2 최소 비용 신장 트리 (1)
• 최소비용신장트리(MST: minimu spanning tree): 네트워크에 있 는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 신 장트리
• MST의 응용
• 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소 가 되도록 하는 문제
• 전기 회로 - 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
• 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구 성하는 문제
• 배관 - 파이프를 모두 연결하면서 파이프의 총 길이가 최소 가 되도록 연결하는 문제
8.4.2 최소 비용 신장 트리 (2)
• 2가지의 대표적인 알고리즘
• Kruskal의 알고리즘
• Prim의 알고리즘
• 탐욕적인 방법(greedy method)
• 알고리즘 설계에서 있어서 중요한 기법 중의 하나
• 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것 을 해답으로 선택함으로써 최종적인 해답에 도달
• 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증 해야 한다.
• Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명
8.4.2 최소 비용 신장 트리 (3)
• Prim의 MST 알고리즘
• Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법
• 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함
• 앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 최 저 간선으로 연결된 정점을 선택하여 트리를 확장
• 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속된다.
간선 (a, b)와 간선 (f, e)의 가중치를
비교해보면 (f, e)가 27로서 (a, b)의 29보다
높다. 따라서 (f, e) 간선이 선택되고 정점 e가
신장 트리 집합에 포함된다.
8.4.2 최소 비용 신장 트리 (4)
• Prim의 MST 알고리즘
8.4.2 최소 비용 신장 트리 (5)
• Kruskal의 MST 알고리즘
• 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이 클을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
• 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
• 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가한다.
• 만약 사이클을 형성하면 그 간선은 제외된다.
8.4.2 최소 비용 신장 트리 (6)
• Kruskal의 MST 알고리즘