크루스칼 (Kruskal)

크루스칼 알고리즘은 프림 알고리즘과 함께 최소 스패닝 트리를 찾는 알고리즘이다.

 

스패닝 트리는 모든 정점에 대해 사이클이 없는 그래프이다. 즉 트리 형태이지만 부모- 자식의 형태로 이어질 필요는 없다.

 

크루스칼 알고리즘은 간선을 정렬한 후 사이클이 존재하지 않게 순서대로 간선을 붙이는 방식으로 구현된다.

 

사이클이 존재하지 않기 위해서는 두 정점이 같은 컴포넌트로 속해져 있지 않으면 되고, 같은 컴포넌트에

에 속하지 않는 것을 확인하기 위해 상호배타적 조합 ( 유니온 파인드라고 많이 부른다)을 사용한다.

 

#include <vector>
#include <algorithm>
using namespace std;

struct DisjointSet {
	vector<int> parent, rank;

	DisjointSet(int n) {
		parent = vector<int>(n);
		rank = vector<int>(n, 1);
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	int find(int u) {
		if (u == parent[u]) {
			return u;
		}

		return parent[u] = find(parent[u]);
	}

	void merge(int u, int v) {
		u = find(u);
		v = find(v);

		if (u == v) {
			return;
		}

		if (rank[u] > rank[v]) {
			swap(u, v);
		}

		parent[u] = v;
		if (rank[u] == rank[v]) {
			rank[v]++;
		}
	}

	void swap(int &a, int &b) {
		int temp = a;
		a = b;
		b = temp;
	}
};

const int MAX_V = 100;
int V;

vector<pair<int, int>> adj[MAX_V];

int kruskal(vector<pair<int, int>>& selected) {
	int ret = 0;
	selected.clear();

	vector<pair<int, pair<int, int>>> edge;
	for (int u = 0; u < V; u++) {
		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first;
			int cost = adj[u][i].second;
			edge.push_back(make_pair(cost, make_pair(u, v)));
		}
	}

	sort(edge.begin(), edge.end());

	DisjointSet sets(V);

	for (int i = 0; i < edge.size(); i++) {
		int cost = edge[i].first;
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (sets.find(u) == sets.find(v)) {
			continue;
		}

		sets.merge(u, v);
		selected.push_back(make_pair(u, v));
		ret += cost;
	}

	return ret;
}