[알고리즘] 최소신장트리 구하기 - 크루스칼 알고리즘 C++

앞에서 최소신장트리를 구하는 두가지 알고리즘을 살펴봤다.

두개 중 먼저 크루스칼 알고리즘을 구현해보려 한다.

 

크루스칼 알고리즘

크루스칼 알고리즘은 간선의 cost 를 오름차순으로 정렬하고 제일 cost가 싼 간선 순서대로 연결시키는 알고리즘이다.

이때 사이클이 만들어지면 안되므로, 간선 추가 시 사이클이 발생하는지를 판단하는 알고리즘이 따로 필요한데,

 

이는 Union Find 를 이용하면 된다

 

 

Union Find

총 1 부터 10까지 10개의 노드가 존재한다.

노드는 서로 연결되어 있는데, 

 

1-2-3-4

5-6-7-8

9-10 

 

 총 3 그룹으로 나눌 수 있다.

 

여기서 우리는 Parent[] 라는 배열을 사용하는데, 윗칸은 노드의 번호 , 아래칸은 해당 노드의 부모 노드를 의미한다.

 

연결정보를 갱신하는데, 이때 작은 값을 기준으로 갱신한다.

 

위 그림에서 1 과 2가 서로 연결되어있으므로 

노드'2' 의 부모 노드를 1로 바꾸는 식이다.

 

1-2-3-4 는 모두 한 그룹에 속해있지만 현재는 3과 4의 부모노드 값은 1이 아닌 걸 볼 수 있다.

 

3은 2와 연결되어있다 → 2는 1과 연결되어있다 → 따라서 3과 1은 연결되어있다. 

그러므로 노드'3' 의 부모노드도 1로 바꿔줘야하는데, 이는 재귀를 통해 해결할 수 있다.

 

크루스칼 알고리즘 구현

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

using namespace std;

int parent[7];

class Edge {
public:
	int node[2];
	int cost;
	Edge(int a, int b, int cost) {
		this->node[0] = a;
		this->node[1] = b;
		this->cost = cost;
	}

	//간선을 오름차순으로 정렬할때 기준을 cost로 정함.
	bool operator<(Edge &edge) {
		return this->cost < edge.cost;
	}

};

//재귀로 구현한 부모노드 가져오는 함수
int getParent(int node) {
	if (parent[node] == node) return node;
	else return getParent(parent[node]);
}

// 노드끼리 연결시키는 함수. 이때 부모노드는 작은 노드로 쓴다.
void unionParent(int node1, int node2) {
	node1 = getParent(node1);
	node2 = getParent(node2);
	if (node1 < node2) parent[node2] = node1;
	else parent[node1] = node2;
}

// 사이클인지 판단하는 함수
bool isCycle(int node1, int node2) {
	node1 = getParent(node1);
	node2 = getParent(node2);
	if (node1 == node2) return true;
	else return false;
}

int main() {
	//두 노드를 연결할 간선을 정해줍니다. 
	vector<Edge> v;
	v.push_back(Edge(1, 7, 12));
	v.push_back(Edge(1, 4, 23));
	v.push_back(Edge(1, 2, 26));
	v.push_back(Edge(2, 3, 36));
	v.push_back(Edge(2, 4, 21));
	v.push_back(Edge(2, 5, 45));
	v.push_back(Edge(3, 5, 29));
	v.push_back(Edge(3, 6, 37));
	v.push_back(Edge(3, 7, 55));
	v.push_back(Edge(4, 7, 20));
	v.push_back(Edge(5, 6, 30));

	//간선을 오름차순으로 정렬합니다. 
	sort(v.begin(), v.end());

	//각 노드는 자기자신이 부모로 초기화해줍니다. 
	for (int i = 1; i <= 7; ++i) {
		parent[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < v.size(); i++) {
		//싸이클이 존재하지 않으면 비용을 더합니다. 
		if (isCycle(v[i].node[0], v[i].node[1])==false) {
			sum += v[i].cost;
			unionParent(v[i].node[0], v[i].node[1]);
		}
	}

	cout << sum << endl;

	return 0;
}