프림 알고리즘(Prim Algorithm)

개요

Prim Algorithm은 최소비용 신장트리 (Minimal Spanning Tree)를 만들어 내는 알고리즘이다.

동작

알고리즘은 다음 순서로 동작한다.
1 ) 임의의 정점을 선택하여 비어있는 tree T에 포함시킨다.
2 ) T에 존재하는 정점과 T에 존재하지 않는 정점의 간선 중 가중치가 최소인 간선을 찾아 그 간선과 T에 존재하지 않던 정점을 T에 포함시킨다.
3 ) 모든 정점이 T에 포함될 때까지 2 )를 반복한다.

구현

가중치가 최소인 간선을 찾는 과정을 최소 힙(Min Heap)을 이용한다.

문제 : 백준 1922번 - 네트워크 연결

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct compare {
  bool operator()(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
  }
};

int N, M, ans;
vector<pair<int, int>> Edges[1010];
int Visit[1010];
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq; //최소 힙을 priority queue로 구현

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int a, b, c;
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> a >> b >> c;
    Edges[a].push_back({b, c});
    Edges[b].push_back({a, c});
  }

  Visit[a] = 1;
  for (auto &i : Edges[a]) pq.push(i);

  while (!pq.empty()) {
    pair<int, int> temp = pq.top();
    pq.pop();
    if (Visit[temp.first]) continue;
    ans += temp.second;
    Visit[temp.first] = 1;
    for (auto &i : Edges[temp.first]) pq.push(i);
  }

  cout << ans << "\n";

  return 0;
}

정당성 증명

프림 알고리즘의 정확성은 수학적 귀납법을 통해 증명한다. 정점의 수 : n 명제 : 프림 알고리즘의 각 단계에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 MST가 항상 존재한다.

1. base : 프림 알고리즘은 첫 단계에서는 간선이 없다. 그러므로 간선들의 집합은 공집합이다. 따라서 MST가 무엇이든 간선들의 집합을 포함한다.
2. step : 프림 알고리즘의 1부터 n-2단계까지에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 MST가 존재한다고 가정하자.
   n-2 단계로 얻는 그래프는 Q이고 이 때 간선들의 집합 L을 포함하는 MST를 T라고 하면 Q에서 아직 연결되지 않은 마지막 꼭짓점 E를 한점으로 하는 변 e를 그리면 Q’을 얻는다. 그러므로 Q’과 T는 L을 공통으로 포함하고, E를 연결하는 변만 차이가 있다. 이 때 T는 MST이고, Q’도 가중치가 가장 낮은 e를 그려서 얻으므로 T와 Q’은 비용이 동일하다. 그러므로 n-1 단계에서 얻는 그래프 Q’의 간선 집합을 포함하는 MST Q’ 자신이 존재한다.

시간복잡도

O(ElogV) (E : 간선의 수, V : 정점의 수) 기본적으로 모든 노드에 대해 탐색을 진행하므로 O(V), 힙을 이용해 매 노드마다 최소 간선을 찾는 시간이 O(logV)이므로 탐색과정에는 O(VlogV)가 소요된다.
이때 각 노드의 간선을 찾는 시간은 O(E)이고, 간선을 힙에 넣는 과정이 O(logV)이므로 힙 구성에 O(ElogV)가 소요된다. 따라서 총 시간복잡도는 O(VlogV + ElogV)이지만 E가 일반적으로 V보다 크기 때문에 결과적으로 O(ElogV)라고 할 수 있다.