크루스칼 알고리즘(Kruskal Algorithm) (feat. Union-Find)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하여 최소비용신장트리를 만들 때 사용하는 알고리즘이다.

가장 가중치가 작은 간선부터 골라가는 그리디한 방법이며 작동과정 중 사이클이 생기지 않도록 유니온파인드를 사용해 해결한다.

사용할 그래프

가중치가 가장 작은 간선을 선택한다.

마찬가지로 가중치가 가장 작은 간선을 선택한다.

그 다음으로 작은 간선을 선택한다.

간선 AB를 선택하고 사이클이 발생하는 BD는 제외한다.

다음으로 작은 간선을 고르고 사이클이 발생하면 제외한다.

반복하면 최소 비용 신장 부분 그래프가 완성된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int getParent(int set[], int x) {
	if(set[x] == x) return x;
	return set[x] = getParent(set, set[x]);
}

void unionParent(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);
	if(a < b) set[b] = a;
	else set[a] = b;
}

int find(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);
	if(a == b) return 1;
	else return 0;
}

class Edge {
public:
	int node[2];
	int distance;
	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}
	bool operator <(Edge &edge) {
		return this->distance < edge.distance;
	}
};

int main() {
	int n = 7;
	int m = 11;

	vector<Edge> v;

	v.push_back(Edge(1, 2, 7));
	v.push_back(Edge(1, 4, 5));
	v.push_back(Edge(2, 3, 8));
	v.push_back(Edge(2, 4, 9));
	v.push_back(Edge(2, 5, 7));
	v.push_back(Edge(3, 5, 5));
	v.push_back(Edge(4, 5, 15));
	v.push_back(Edge(4, 6, 6));
	v.push_back(Edge(5, 6, 8));
	v.push_back(Edge(5, 7, 9));
	v.push_back(Edge(6, 7, 11));

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

	int set[n];
	for(int i = 0; i < n; i++)
		set[i] = i;

	int sum = 0;
	for(int i = 0; i < v.size(); i++) {
		if(!find(set, v[i].node[0] - 1, v[i].node[1] - 1)) {
			sum += v[i].distance;
			unionParent(set, v[i].node[0] - 1, v[i].node[1] - 1);
		}
	}
	cout << sum;
}

위 코드에서 정점 A, B, C, D, E, F, E는 각 1, 2, 3, 4, 5, 6으로 표현했다.
최소 비용 신장 트리에서 간선들의 가중치 합을 출력하는 코드다.