[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)? 크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 알고리즘으로, 탐욕적인(greedy) 방법을 통해 구현할 수 있다. greedy? 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. 구현 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의..

원문링크 : [Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)