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

프림(Prim) 알고리즘

1. 그래프에서 시작점을 정한다 - (어떤 노드이어도 상관없음)
2. 선택한 정점과 인접하는 정점들 중 최소 비용인 간선에 연결된 정점을 선택한다.
3. 모든 정점이 선택될 때까지 1,2과정을 반복한다.

※ 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리를 구성하는데 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 정렬 후 가장 최소 비용으로 간선을 선택하기 때문에 사이클이 발생하는지 판단하면서 진행해야 한다. 

	struct compare {
	bool operator()(pairInt &lhs, pairInt &rhs) {
	return lhs.second > rhs.second;
	}
	};
	void Prim() {
	priority_queue<pairInt, vector<pairInt>, compare> pque;
	for (int i = 0; i < adj[1].size(); i++) pque.push(adj[1][i]);
	visit[1] = true;
	int cnt = 0;
	while (cnt < v - 1) {
	pairInt curline = pque.top();
	pque.pop();
	int node = curline.first;
	int weight = curline.second;
	if (visit[node]) continue;
	visit[node] = true;
	cnt++;
	cout << node <<" "<< weight;
	for (int i = 0; i < adj[node].size(); i++) {
	int nextnode = adj[node][i].first;
	if (!visit[nextnode]) pque.push(adj[node][i]);
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub