크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘이란?

그래프 내에서 모든 정점들을 가장 적은 비용으로 연결하는 알고리즘이다.
즉, 최소 신장 트리를 구하는 알고리즘이다.
그렇다면 최소 신장 트리는 무엇일까?

최소 신장 트리(MST)란?

최소 신장 트리를 알기 전에 신장 트리에 대해서 알아야한다.

신장 트리

1. 그래프에서 모든 정점을 포함한다.
2. 정점 간 서로가 연결이 되어 있으며 싸이클이 존재하지 않는다.

그림으로 알아보자.

이런 그래프가 있지만 (1,2,4,5), (1,2,3,5), (2,3,4,5) 이렇게 싸이클이 형성된 상태이다.

이 그래프로 신장 트리를 만들어 보자.

위 그림과 같이 모든 정점은 연결 되어 있지만 싸이클이 하나도 존재하지 않는 것을 볼 수 있다.

이 중에서 최소 신장 트리란 가장 적은 비용으로 모든 정점을 싸이클 없이 연결하면 된다.

위 그림은 가중치의 합 10으로 모든 정점은 연결 되었고, 싸이클이 존재하지 않는 최소 신장 트리이다.

크루스칼 알고리즘 설명

왼쪽 그림과 같이 싸이클이 형성된 그래프가 있다.
이 그래프의 모든 정점은 포함하고, 싸이클이 없게, 최소 비용으로 트리를 형성하면 오른쪽 그림과 같다.

그렇다면 오른쪽 그림과 같이 어떻게 만들 수 있을까?

1. 입력 받은 데이터를 가중치의 오름차순 값으로 정렬을 시킨다.
2. 정렬 후 최솟값부터 연결되지 않은 정점들을 연결 처리하며 가중치 값을 더해준다.(처음은 모두가 연결되지 않은 상태)

일단 위 그림과 같이 데이터를 받아보자.

첫 번째 값이 시작점, 두 번째 값이 도착점, 세 번째 값이 가중치이다.
왼쪽과 같이 입력을 받으면 세 번째 가중치 값의 오름차순으로 정렬을 한다.

정렬이 완료되었다면 이제 최소 신장 트리를 만들어야한다.

처음 상태는 어느 정점도 연결되지 않은 상태이고, 우리는 가중치가 작은 값부터 정렬을 해두었으므로 연결 여부를 판단한다.

크루스칼 알고리즘 그림을 통해 알아보기

위의 데이터 값은 9개의 정점과 12개의 간선이다.
정점은 1~9까지이다.

처음에 정점은 모두 연결되어 있지 않다.

데이터 값 (2 9 8), (2 3 10)은 "2번 정점과 9번 정점을 8의 가중치로 연결해주세요", "2번 정점과 3번 정점을 10의 가중치로 연결해주세요"라는 뜻이다.

연결을 하면 다음과 같다.

마찬가지로 (1 2 12), (8 9 15) 를 연결해보자.

이 상태에서 다음 데이터 값 (2 8 17)을 받아보자.
하지만 2와 8은 9라는 정점을 통해 이어져 있는 상태이다. 따라서 2와 8은 연결될 수 없다.

이와 같은 방식으로 연결되지 않은 모든 정점을 연결 시켜주면 다음 그림과 같다.

소스코드

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

using namespace std;

int unf[101];
vector<pair<pair<int, int>, int>> v;

bool compare(pair<pair<int, int>, int> &p1, pair<pair<int, int>, int> &p2) {
	return p1.second < p2.second;
}

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

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a != b)
		unf[a] = b;
}

int main() {

	int N, M, A, B, C, res = 0;

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		unf[i] = i;

	for (int i = 0; i < M; i++) {
		cin >> A >> B >> C;
		v.push_back(make_pair(make_pair(A, B), C));
	}

	sort(v.begin(), v.end(), compare); // 가중치 값 오름차순 정렬

	for (int i = 0; i < M; i++) {
		int a = Find(v[i].first.first); // 정점이 속한 그룹을 a에 저장
		int b = Find(v[i].first.second); // 정점이 속한 그룹을 b에 저장

		if (a != b) { //만약 속한 그룹이 다르다면(연결되어 있지 않다면)
			Union(a, b); // 두 정점을 연결해라
			res += v[i].second; //가중치 값을 더해라
		}
	}
	cout << res;

	return 0;
}