탐욕 알고리즘
최소신장트리(MST, Minimum Spanning Tree)를 구성하는데 사용하는 알고리즘, 정점 간 연결 비용이 최소이다.
- 프림 알고리즘 - 정점 간 비용이 적게 드는 순으로 연결하여 최소 신장트리를 완성한다.
프림 알고리즘 응용 소스코드 - BOJ 1197- 크루스칼 알고리즘 - 정점 간 비용이 적게 드는 순으로 같은 부모를 같도록 설정한 뒤 연결한다. 부모가 같다면 사이클이 발생하므로 연결하지 않고 부모가 다른 경우만 연결한다.
크루스칼 알고리즘 응용 소스코드 - BOJ 1197
incipience