2JINISHAPPY 2JINISHAPPY

#include #include #include #define INF 987654321 using namespace std; vector graph; int V, E; int prim() { vector cost(V + 1, INF); vector prev(V + 1, -1); vector visit(V + 1, false); priority_queue pq; pq.push(make_pair(0, 1)); cost[1] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); visit[u] = true; for (auto next : graph[u]) { int v = next.second; int weight = next.first; if (!vi..

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 ..