[알고리즘] MST - 프림(Prim) 알고리즘

Prim 알고리즘이란

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

Prim 알고리즘의 동작

1. 시작단계에서는 시작 정점만이 MST집합에 포함된다.
2. 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
   • 즉 가장 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때 까지 반복한다.

Prim 알고리즘의 구체적인 동작 과정

Prim 알고리즘을 이용하여 MST를 만드는 과정

• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법

Prim 알고리즘의 시간 복잡도

• 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복
  - Prim의 알고리즘의 시간 복잡도는 O(n^2) 이 된다.
• Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 이므로
  - 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고
  - 그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.

Prim 알고리즘의 구현

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
#define NODE 7
#define EDGE 9



class Edge {
public:
	int node[2]; //양 끝 정점
	int distance;
	Edge(int x, int y, int distance) {
		this->node[0] = x;
		this->node[1] = y;
		this->distance = distance;
	}
	bool operator <(Edge &edge) {
		return this->distance < edge.distance;
	}

	bool operator >(Edge &edge) {
		return this->distance > edge.distance;
	}
};

vector<Edge> v;
int visit[10001];
priority_queue<Edge, vector<Edge>, greater<>> pq;
int sum;

void prim(int start) {
	visit[start] = 1;

	for (int i = 0; i < v.size(); i++) {
		if (v[i].node[0] == start) {
			if (!visit[v[i].node[1]]) {
				pq.push(v[i]); //정점 start와 연결된 간선을 큐에 담는다
			}
		}
	}

	while (!pq.empty()) {
		Edge w = pq.top();
		pq.pop();
		if (!visit[w.node[1]]) {
			sum += w.distance;
			prim(w.node[1]);
			return;
		}
	}
}


int main(int argc, char *argv[]) {

	v.push_back(Edge(0, 1, 28));
	v.push_back(Edge(0, 5, 10));
	v.push_back(Edge(1, 0, 28)); //
	v.push_back(Edge(1, 2, 16));
	v.push_back(Edge(1, 6, 14));
	v.push_back(Edge(2, 1, 16)); //
	v.push_back(Edge(2, 3, 12));
	v.push_back(Edge(3, 2, 12)); //
	v.push_back(Edge(3, 4, 22));
	v.push_back(Edge(3, 6, 18));
	v.push_back(Edge(4, 3, 22)); //
	v.push_back(Edge(4, 5, 25));
	v.push_back(Edge(4, 6, 24));
	v.push_back(Edge(5, 0, 10));//
	v.push_back(Edge(5, 4, 25));//
	v.push_back(Edge(6, 1, 14)); //
	v.push_back(Edge(6, 3, 18));
	v.push_back(Edge(6, 4, 24));

	prim(0);
	cout << sum << endl;
	
	return 0;
}