2JINISHAPPY 2JINISHAPPY

MST를 생성하는 방법에는 Kruskal, Prim 두 가지 알고리즘이 존재한다. Kruskal 알고리즘을 빠른 시간 내에 동작하게 하려면 Union-Find 자료구조(라이브러리가 없기에 직접 구현해야함)를 사용해야 한다는 번거로움이 있지만, 여기에서 다룰 Prim's Algorithm은 priority queue를 가지고 구현할 수 있다. Prim's Algorithm을 관통하는 가장 중요한 property를 정의하고 가자. Cut Property: Edge e = (u,v)는 MST의 edge set T에 속해 있다 ↔ e는 vertex u를 포함한 어떤 vertex set S와 v를 포함한 V(G) - S를 이어주는 edge들 중 제일 cost가 작다 (오른쪽 그림, ←)MST가 위에서 설명한 e ..

이전에 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의 성질이..