Related to: Algorithm
최소 신장 트리
어떤 그래프가 있을 때, 모든 정점을 최소 비용으로 연결하는 트리크루스컬 알고리즘(Kruskal’s algorithm)과 프림 알고리즘(Prim’s algorithm)이 있다.
크루스컬 알고리즘
크러스컬 알고리즘은 아래의 순서대로 작동한다.
- 그래프에서 꼭짓점 또는 나무를 분리해 내지 않는 최대 가중치의 변을 제거한다.
- 그래프에 n-1개의 변만 남을 때까지 1을 반복한다.
- 그래프에 n-1개의 변이 남으면 최소 비용 생성나무이다.
프림 알고리즘
프림 알고리즘은 아래의 순서대로 작동한다:
- 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
- 그래프의 모든 변이 들어 있는 집합을 만든다.
- 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.
- 알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.
참조
https://en.wikipedia.org/wiki/Minimum_spanning_tree
https://janghw.tistory.com/entry/알고리즘-Greedy-Algorithm-탐욕-알고리즘