[그래프 알고리즘]프림 알고리즘(MST)

MST Minimum Spanning Tree

MST란 한 무향 그래프에서 특정 엣지들의 집합으로, 모든 노드들을 연결하면서, 가중치의 합이 제일 작은 엣지들의 집합이다.

MST는 트리이므로 엣지들의 개수는 노드의 개수에서 1을 뺀 수이다.

프림 알고리즘

프림 알고리즘은 한 노드에서 시작해, 주변 노드들을 MST에 포함시켜 나간다.

MST 에 포함될 다음 노드는, MST에 가장 작은 가중치로 연결된 노드이다.

모든 노드들이 MST에 포함될 때까지 반복한다.

구현

	#include <iostream>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	#define N_NODE 5
	#define INF 9999999
	struct Edge {
	int dst;
	int weight;
	Edge(int dst, int weight){
	this->dst = dst;
	this->weight = weight;
	}
	};
	vector<Edge> adjList[N_NODE];
	void addEdge(int u, int v, int w){
	adjList[u].emplace_back(v, w);
	adjList[v].emplace_back(u, w);
	}
	// MST에 포함되어 있는지 표시
	vector<bool> inMST(N_NODE, false);
	vector<pair<int, int>> prim(){
	// 다익스트라 알고리즘과 유사하다
	vector<pair<int, int>> mst;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	// 노드 0부터 시작
	pq.push(make_pair(0, 0));
	// minwWeight : 한 노드에 연결된 가장 작은 가중치를 기록한다.
	// parent : 노드에 연결된 가장 작은 가중치를 엣지의 반대편 노드
	vector<int> minWeight(N_NODE, INF), parent(N_NODE);
	minWeight[0] = 0;
	parent[0] = 0;
	while(!pq.empty()){
	pair<int, int> cur = pq.top();
	pq.pop();
	int weight =cur.first;
	int here = cur.second;
	// 중복으로 들어간 경우 제외
	if(minWeight[here] < weight) continue;
	// MST에 추가하기
	inMST[here] = true;
	if(parent[here] != here)
	mst.push_back(make_pair(parent[here], here));
	for(auto &there : adjList[here]){
	// 아직 MST에 있지 않으면서 더 작은 가중치의 엣지가 발견된 경우
	if(!inMST[there.dst] && minWeight[there.dst] > there.weight) {
	minWeight[there.dst] = there.weight;
	parent[there.dst] = here;
	pq.push(make_pair(minWeight[there.dst], there.dst));
	}
	}
	}
	return mst;
	}
	int main(){
	// 그래프 생성
	addEdge(0, 1, 1);
	addEdge(1, 2, 1);
	addEdge(2, 3, 8);
	addEdge(3, 4, 1);
	addEdge(1, 3, 9);
	addEdge(1, 4, 1);
	addEdge(0, 4, 7);
	vector<pair<int, int>> mst = prim();
	for(auto &edge : mst){
	cout << edge.first << ", " << edge.second << "\n";
	}
	return 0;
	}

view raw prim_algorithm.cpp hosted with ❤ by GitHub

다익스트라 알고리즘과 유사하다.

MST에 연결된 노드들 중 가장 가중치가 작은 엣지에 연결된 노드를 선택한다.

선택 과정을 효율적으로 하기 위해 우선순위 큐를 이용한다.

MST는 결국 엣지들의 집합이므로, 노드를 선택할 때 고려된 엣지의 반대편 노드도 저장해야한다.