[C++] 크루스칼 알고리즘(Kruskal Algorithm, 최소 스패닝 트리-MST) 개념

크루스칼 알고리즘이란?

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.

이는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다.

대표적으로 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘입니다.(크루스칼 알고리즘을 구현할 때 기본적으로 유니온 파인드 개념을 사용합니다.)

 

 

예시코드

class edge {
public:
	int node[2];
	int distance;

	edge(int a, int b, int c) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = c;
	}

	bool operator <(edge& edge) {
		return this->distance < edge.distance;
	}
};

int parent[10001];

int find(int index) {
	if (parent[index] == index) return index;
	return parent[index] = find(parent[index]);
}

void uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

//사이클 유무 확인
bool isCycle(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return true;
	else
		return false;
}

 main 부분 구현

	for (int i = 0; i < v.size(); i++) {
		if (isCycle(v[i].node[0], v[i].node[1]) == false) {
			answer += v[i].distance;
			uni(v[i].node[0], v[i].node[1]);
		}
	}