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

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

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. (최소비용신장트리를 만들기 위한 대표적인 알고리즘)

여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자할 때 실제로 적용합니다.

​

모든 간선정보를 오름차순으로 정렬한 뒤에 (간선 거리(비용)이 짧은(적은) 순서대로 정렬) 비용이 적은 간선부터 차근차근 그래프에 포함시키면 됩니다.

 

1. 정렬된 순서에 맞게 그래프에 포함

2. 포함시키기 전에는 사이클 테이블 확인

3. 사이클을 형성하는 경우 간선을 포함시키지 않는다

​

사이클이 발생하는 지의 여부는 Union-Find 알고리즘을 적용하면 됩니다.

 

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

using namespace std;

//부모 노드를 가져옴
int getParent(int set[], int x) {
	if (set[x] == x) return x;
	return set[x] = getParent(set, set[x]);
}

//부모 노드 병합
void unionParent(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);

	if (a < b) set[b] = a;
	else set[a] = b;
}

//같은 부모를 가지는지 확인
int find(int set[], int a, int b) {
	a = getParent(set, a);
	b = getParent(set, b);
	if (a == b) return 1;
	else return 0;
}


//간선 클래스 선언
class Edge {
public:
	int node[2];
	int distance;

	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}
	
	bool operator <(Edge& edge) {
		return this->distance < edge.distance;
	}
};
int main(void) {
	int n = 7;
	int m = 11;

	vector<Edge> v;
	v.push_back(Edge(1, 7, 12));
	v.push_back(Edge(1, 4, 28));
	v.push_back(Edge(1, 2, 67));
	v.push_back(Edge(1, 5, 17));
	v.push_back(Edge(2, 4, 24));
	v.push_back(Edge(2, 5, 62));
	v.push_back(Edge(3, 5, 20));
	v.push_back(Edge(3, 6, 37));
	v.push_back(Edge(4, 7, 13));
	v.push_back(Edge(5, 6, 45));
	v.push_back(Edge(5, 7, 73));

	//간선의 비용으로 오름차순 정렬
	sort(v.begin(), v.end());


	

	//각 정점이 포함된 그래프가 어디인지 저장
	int set[7];
	for (int i = 0; i < n; i++) {
		set[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		//동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택
		if (!find(set, v[i].node[0] - 1, v[i].node[1] - 1)) {
			sum += v[i].distance;
			unionParent(set, v[i].node[0] - 1,v[i].node[1] - 1);
		}
	}

	cout << sum << '\n';
}