[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)

 

크루스칼 알고리즘은 최소 비용 신장 트리(MST)를 만드는 데 사용되는 알고리즘입니다. 최소 비용 신장 트리란 가장 적은 최소한의 가중치(비용)로 모든 노드를 연결한 트리입니다. 즉, 여러 장소를 최소한의 비용으로 연결하고자 할 때 적용되는 알고리즘입니다. 

 

우선 정점(노드) vertex과 간선 edge의 개념에 대해 알고 가야합니다. 그래프 자료구조에서 자세히 다루었으니 참고하시기 바랍니다.

 

알고리즘 원리

크루스칼 알고리즘의 동작 원리는 다음과 같습니다.

 

1. 최소 비용을 기준으로 간선을 오름차순 정렬

2. 사이클 확인 후 집합 생성 (사이클이면 사이클되는 간선을 배제함)

최소 비용 신장 트리의 경우 사이클이 생성되어서는 안됩니다. 사이클 여부는 유니온 파인드 알고리즘을 적용하여 판단합니다.

위 0~8의 9개의 정점과 16개의 간선들로 이루어진 그래프에서 비용을 기준으로 오름차순 정렬하면 그래프 아래의 표와 같이 나타낼 수 있습니다. 이제 이 표의 순서대로 하나씩 집합을 만들어 가면 됩니다.

먼저 간선 비용이 가장 작은 정점 0과 1을 집합으로 연결합니다.

그 다음으로 정점 3과 5를 연결합니다

그 다음으로 정점 1과 4를 연결합니다

그 다음으로 정점 7과 8을 연결합니다

그 다음으로 정점 5와 7을 연결합니다

그 다음으로 정점 6과 8을 연결합니다

그 다음으로 정점 0과 2를 연결합니다

정점 3과 6의 간선, 정점 3과 7의 간선, 정점 1과 2의 간선은 모두 사이클이 되는 간선이므로 배제합니다.

그 다음으로 정점 2와 3의 간선을 연결합니다. 이로써 연결된 간선 수가 정점 수 - 1인 7이 되었으므로 모든 정점이 연결된 최소 비용 신장 트리가 형성됩니다. 확인되지 않은 간선들을 확인할 수 있으나 시간 복잡도가 증가하므로 모두 배제합니다.

 

알고리즘 구현

크루스칼 알고리즘을 구현하는 데 있어서 기본적으로 Union-Find 알고리즘이 사용됩니다. 최소 비용의 간선 사이에서 Find를 적용하여 사이클 되지 않은 두 정점이 존재하면 Union을 적용합니다.

// Algorithm Analysis
// 크루스칼 알고리즘 (Kruskal Algorithm)

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

using namespace std;

// 속한 집합 찾기
int getSet(int set[], int x) {
	if (set[x] == x) return x;
	return set[x] = getSet(set, set[x]);
}

// 두 집합 합치기
void unionSet(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a < b)
		set[b] = a;
	else
		set[a] = b;
}

// 동일한 집합 내에 속해있는지 확인
int find(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a == b) return 1;
	return 0;
}

// 간선 정보 클래스
class Edge {
public:
	int vtx[2]; // 연결된 2개의 정점
	int distance; // 거리(비용)
	Edge(int a, int b, int distance) {
		this->vtx[0] = a;
		this->vtx[1] = b;
		this->distance = distance;
	}
	bool operator <(Edge& edge) {
		return this->distance < edge.distance; // 적은 거리 우선 정렬
	}
};
int main() {
	int v = 9; // 정점 수 (0~8)

	vector<Edge> data; // 간선 데이터 배열
	data.push_back(Edge(0, 1, 8)); // 정점0과 정점1의 간선 비용8
	data.push_back(Edge(0, 2, 12));
	data.push_back(Edge(1, 2, 13));
	data.push_back(Edge(1, 3, 25));
	data.push_back(Edge(1, 4, 9));
	data.push_back(Edge(2, 3, 14));
	data.push_back(Edge(2, 6, 21));
	data.push_back(Edge(3, 4, 20));
	data.push_back(Edge(3, 5, 8));
	data.push_back(Edge(3, 6, 12));
	data.push_back(Edge(3, 7, 12));
	data.push_back(Edge(3, 8, 16));
	data.push_back(Edge(4, 5, 19));
	data.push_back(Edge(5, 7, 11));
	data.push_back(Edge(6, 8, 11));
	data.push_back(Edge(7, 8, 9));

	// 간선 비용을 기준으로 정렬
	sort(data.begin(), data.end());

	int set[9];
	for (int i = 0; i < v; i++) {
		set[i] = i;
	}
	int sum = 0; // 최소 비용 합

	for (int i = 0; i < data.size(); i++) {
		// 사이클이 발생하지 않으면 그래프에 포함
		if (!find(set, data[i].vtx[0], data[i].vtx[1])) {
			sum += data[i].distance;
			unionSet(set, data[i].vtx[0], data[i].vtx[1]);
		}
	}
	cout << sum;
}

 

시간 복잡도 : O(E logE)

V : 정점 수 | E : 간선 수

 

모든 정점을 독립적 집합으로 생성하는 시간 복잡도 O(V)

오름차순으로 정렬하는 시간 복잡도 O(E logE)

Union하는 시간 복잡도 O(1)

따라서 Kruskal Algorithm의 전체 시간 복잡도는 O(E logE)입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.