Kruskal(크루스칼) 알고리즘

참고사이트:https://blog.naver.com/ndb796/221230994142

18. 크루스칼 알고리즘(Kruskal Algorithm)

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다.

 

* MST(최소 신장 트리)를 만들기위한 알고리즘 입니다.

MST란 Minimum Spanning Tree 로서 최소 신장 트리라고 합니다.

특징은

간선의 가중치 합이 최소여야 하고,

n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선을 사용해아 하며,

사이클이 포함되어서는 안됩니다.

 

구현 방법이 바로 Kruskal MST 알고리즘 입니다.