백준 1197번 : 최소 스패닝 트리 - Kruskal & Prim Algorithm

크루스칼 알고리즘과 프림 알고리즘 비교

 

크루스칼 알고리즘은 간선을 기준으로 Spanning Tree를 연결하고

프림 알고리즘은 정점을 기준으로 Spannig Tree를 연결한다.

 

따라서 간선이 많을 경우 프림 알고리즘을

간선이 적을 경우 크루스칼 알고리즘을 이용하는 게 유리하다.

 

 

 

---

크루스칼 알고리즘

크루스칼 알고리즘의 시간복잡도는 간선을 Sort하는데

최대 O(ElogE)가 필요하다

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y, val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 10001; i++) {
		unf[i] = i;
	}

	priority_queue<Edge> Q;

	int V, E;
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		Q.push({ a,b,c });
	}

	int ans = 0;
	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << ans << '\n';

	return 0;
}

 

 

프림 알고리즘

프림 알고리즘의 시간 복잡도는 O(E log V)

#include <bits/stdc++.h>
using namespace std;

bool ch[10001];
struct Edge {
	int e;
	int val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

vector<pair<int, int> > graph[10001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	priority_queue<Edge> Q;

	int i, n, m, a, b, c, res = 0;
	
	cin >> n >> m;

	for (i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({ a,c });
	}

	Q.push({ 1,0 });
	while (!Q.empty()) {
		Edge tmp = Q.top();
		Q.pop();
		int v = tmp.e;
		int cost = tmp.val;

		if (ch[v] == 0) {
			res += cost;
			ch[v] = 1;
			for (i = 0; i < graph[v].size(); i++) {
				Q.push({ graph[v][i].first, graph[v][i].second });
			}
		}
	}

	cout << res << '\n';
}