2JINISHAPPY 2JINISHAPPY

이전에 MST(Minimum Spanning Tree)에 대해 다룬 적이 있다. Weighted Connected Graph에서는 edge의 cost 합이 최소가 되게 하는 Subgraph(Tree)를 구성할 수 있고, 이를 MST라고 한다. 이러한 MST를 생성하는 대표적인 알고리즘으로는 Kruskal(크루스칼), Prim(프림)알고리즘이 있다. Kruskal's Algorithm(Greedy) : 그래프 G의 MST를 이루는 edge set을 T라고 가정한다. 각 step마다 T에 추가해도 cycle이 생기지 않는 edge들 중 cost가 가장 작은 edge를 T에 추가한다. 이 과정을 MST가 완성될 때 까지 반복한다. 이와 같이 T에 새로운 edge e를 추가해도 spanning tree의 성질이..