그리디 알고리즘: 최소 신장 트리(MST, Minimum Spanning Tree)

참조

https://en.wikipedia.org/wiki/Minimum_spanning_tree
https://janghw.tistory.com/entry/알고리즘-Greedy-Algorithm-탐욕-알고리즘
https://ko.wikipedia.org/wiki/크러스컬_알고리즘
https://ko.wikipedia.org/wiki/프림_알고리즘

최소 신장 트리

어떤 그래프가 있을 때, 모든 정점을 최소 비용으로 연결하는 트리
크루스컬 알고리즘(Kruskal’s algorithm)과 프림 알고리즘(Prim's algorithm)이 있다.

크루스컬 알고리즘

크러스컬 알고리즘은 아래의 순서대로 작동한다.

1. 그래프에서 꼭짓점 또는 나무를 분리해 내지 않는 최대 가중치의 변을 제거한다.
2. 그래프에 n-1개의 변만 남을 때까지 1을 반복한다.
3. 그래프에 n-1개의 변이 남으면 최소 비용 생성나무이다.

프림 알고리즘

프림 알고리즘은 아래의 순서대로 작동한다:

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.
4. 알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.