MST(Minimum Spanning Tree) 문제 해결을 위한 크루스칼 알고리즘(Kruskal's Algorithm)
MST(MCST, Minimum Cost Spanning Tree, 최소비용신장트리)는 약어 그대로 그래프에 존재하는 여러 개의 Spanning Tree 중 최소 비용을 가지는 것을 찾는 문제이다. 주로 간선(Edge)의 방향성이 없는 undirected graph에서 모든 Vertex(Node) 들을 방문하는 최소의 비용을 구하는 문제가 해당된다.이 MST 문제를 해결하기 위한 알고리즘은 물론 여러 가지가 있을 수 있지만, 대표적으로 Kruskal's Algorithm(크루스칼 알고리즘)과 Prim Algorithm이 있다. Kruskal's Algorithm은 Merge Sort와 Union-Find를 사용하여 구현하는 알고리즘이고, Prim Algorithm은 Heap을 사용하여 구현하는 알고리즘이..
