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

최소 신장 트리(Minimum spanning Tree)는 그래프 내에서

 

1.사이클을 생성하지 않으면서

 

2.그래프의 모든 노드를 포함하는 

 

3. 최소 가중치 합의 간선을 갖는 부분 그래프 를 의미한다. 

 

이러한 최소 신장 트리를 찾는 알고리즘이 바로 크루스칼(Kruskal) 알고리즘이다. 

 

크루스칼 알고리즘은 기본적으로 탐욕 알고리즘의 일종으로서 가장 짧은 간선(edge)를 찾고 

 

이를 트리에 추가함으로써 최소 신장 트리를 만들어낸다. 

 

크루스칼 알고리즘의 메커니즘

출처: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/

 

크루스칼 알고리즘의 주요 메커니즘은 다음과 같다. 

 

1. 그래프에서 가장 짧은 간선(Edge)를 찾는다. 

 

2. 해당 간선을 최소 신장 트리에 추가했을 때 사이클 생성 여부를 확인한다. 

 

3. 사이클 생성이 이루어지지 않을 경우 그 간선을 트리에 추가한다. 

 

위 과정을 반복한다. 

 

사이클 생성 여부를 판별하기 위해 유용하게 사용되는 자료구조인 '유니온-파인드(Union-Find)'에 

 

대해서 살펴보자. 

 

그래프에서 하나의 그룹으로 묶인 노드들의 집합을 컴포넌트(Component)라고 한다. 

 

유니온-파인드 구조에서는 이 컴포넌트를 식별하기 좋게 각 노드들을 하나의 그룹으로 묶고 

 

그 그룹을 대표하도록 하나의 대표 노드를 선정시킨다. 대표노드는 보통 가장 값이 작은 노드가 된다. 

 

succ 이라는 벡터에 각 노드들의 후속 노드를 담고 그 후속 노드를 따라가다보면 대표 노드가 나온다. 

 

이 벡터에서 대표 노드는 자기 자신을 값으로 가진다. 

 

예를 들어 succ[1]이 1이면 노드 1이 대표 값이며, succ[4] = 2, succ [2] = 1이면 

 

4 - 2 - 1 이 하나의 컴포넌트로 묶이는 것이다.

 

int find(vi succ, int x) {
	if (x == succ[x]) {
		return x;
	}
	while (x != succ[x]) {
		//대표값을 만날때까지
		x = succ[x];
	}
	return x;
	//대표값 반환
}

find 함수는 이 벡터를 추적하여서 각 노드의 대표값을 반환시킨다. 

 

int same(vi succ, int a, int b) {
	if (find(succ, a) == find(succ, b)) {
		//노드 a, b가 같은 대표값을 가리키면
		return 1;
	}
	else {
		return 0;
	}
}

또한 Same 함수는 find 함수를 이용하여 노드 a와 b가 서로 같은 컴포넌트에 속한지 판별한다. 

 

최소 신장 트리에 간선을 추가할 때 이미 두 노드가 같은 컴포넌트에 있으면 간선 추가 시 사이클이 만들어지므로 

 

서로 다른 컴포넌트에 있는 노드들만 연결해야한다. 

 

void unite(vi& succ, vi& size, int a, int b) {
	int aHead = find(succ, a);
	int bHead = find(succ, b);
	if (size[aHead] < size[bHead]) {
		swap(aHead, bHead);
	}
	succ[bHead] = aHead;
	size[aHead] += size[bHead];
}

서로 다른 컴포넌트에 있다면 각자의 대표 노드를 찾아서 사이즈가 더 작은 컴포넌트가 다른 컴포넌트의 밑으로 들어간다. 

 

size 벡터에는 각 컴포넌트의 크기를 나타낼 수 있도록 size[대표노드] = 컴포넌트 크기 의 형식으로 값을 저장한다. 

 

이는 A 컴포넌트(더 작은)의 대표 노드가 B 컴포넌트(더 큰)의 대표 노드를 후속 노드로 가리키는 것으로 표현할 수 있다. 

 

vector<tuple<int, int, int>> bubbleForKruskal(vector<vector<pair<int, int>>> adj) {
	int n = adj.size() - 1;
	//sentinel 노드 제외

	vector<tuple<int, int, int>> linkedNodes;

	for (int i = 1; i < adj.size()-1; i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			linkedNodes.push_back(tie(i, adj[i][j].first, adj[i][j].second));
		}
	}

	n = linkedNodes.size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (get<2>(linkedNodes[j]) > get<2>(linkedNodes[j+1])) {
				auto temp = linkedNodes[j];
				linkedNodes[j] = linkedNodes[j + 1];
				linkedNodes[j + 1] = temp;
			}
		}
	}
	return linkedNodes;
}

크루스칼 알고리즘은 가장 짧은 길이의 간선부터 고려하기 때문에 정렬해서 구현하는 것이 편하다. 

 

먼저 vector<vector<pair<int,int>>> 형태의 인접 리스트를 vector<tuple<int,int,int>>의 형태로 바꾸어서 

 

{{시작노드, 이웃노드, 간선가중치}, ...} 형식의 값을 담도록 바꾼 뒤에 bubblesort를 이용하여 간선 가중치의 오름차순으로 

 

노드들의 연결 정보를 만들어주었다. 

 

vector<tuple<int, int, int>> kruskal(vector<tuple<int, int, int>> edgeList) {
	vi succ;
	vi size;
	succ.push_back(0);
	size.push_back(0);
	//add sentinel value.

	int nodeNum = calcNodeNum(edgeList);
	for (int i = 1; i <= nodeNum; i++) {
		succ.push_back(i);
		//처음 모든 노드의 후속 노드는 자신
		size.push_back(1);
		//처음 모든 노드는 떨어져있음을 가정
	}

	vector<tuple<int, int, int>> minSpanTree;
	
	for (int i = 0; i < edgeList.size(); i++) {
		if (same(succ, get<0>(edgeList[i]), get<1>(edgeList[i]))) {
			continue;
		}
		else {
			minSpanTree.push_back(edgeList[i]);
			unite(succ, size, get<0>(edgeList[i]), get<1>(edgeList[i]));
		}
	}
	return minSpanTree;
}

크루스칼 알고리즘의 전체 코드이다. 

 

	vi succ;
	vi size;
	succ.push_back(0);
	size.push_back(0);
	//add sentinel value.

먼저 노드의 컴포넌트 추적을 위한 succ 벡터와 size 벡터를 선언하고 보초값을 삽입한다. 

 

	int nodeNum = calcNodeNum(edgeList);
	for (int i = 1; i <= nodeNum; i++) {
		succ.push_back(i);
		//처음 모든 노드의 후속 노드는 자신
		size.push_back(1);
		//처음 모든 노드는 떨어져있음을 가정
	}

그리고 노드 연결 정보를 입력 받아 노드들의 전체 갯수를 구한 뒤에 각 노드들이 서로 떨어져 있는 것으로 초기화한다. 

 

	vector<tuple<int, int, int>> minSpanTree;
	
	for (int i = 0; i < edgeList.size(); i++) {
		if (same(succ, get<0>(edgeList[i]), get<1>(edgeList[i]))) {
			continue;
		}
		else {
			minSpanTree.push_back(edgeList[i]);
			unite(succ, size, get<0>(edgeList[i]), get<1>(edgeList[i]));
		}
	}
	return minSpanTree;

그런 뒤에 가장 짧은 간선부터 차례로 살펴보아 두 노드가 같은 컴포넌트에 있지 않으면 이를 트리에 추가하고 

 

두 노드들을 같은 컴포넌트에 있는 것으로 정보를 갱신한다. 

 

전체 간선을 모두 순회하면 최소 신장 트리가 완성된다.