Kruskal's Algorithm

Kruskal's Algorithm은 가장 적은 비용으로 노드들을 연결하기 위한 알고리즘이다.
모든 노드를 최소한의 비용으로 연결시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬하고 비용이 적은 간선부터 차례대로 연결해주면 된다.

1. 정렬된 순서에 맞게 그래프에 포함시킨다
2. 포함시키기 전에는 사이클 테이블을 확인한다
3. 사이클을 형성하는 경우 간선을 포함하지 않는다.

사이클은 트리로 형성되어야 할 구조에서 서로 연결되어 트리가 아닌 그래프가 되는 것이고, 이것이 발생해서는 안된다.
서로 다른 두개의 노드와 그 사이의 거리를 가지는 클래스를 만들어주고, Union-Find 알고리즘을 사용하여 최소비용 신장트리를 만든다.

Kruskal's Algorithm Code

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

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;
	
	std::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[n];
	for(int i = 0 ; i < n ; i++)
		set[i] = i;
		
	int sum = 0;
	for(int i = 0 ; i < v.size() ; 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);
		}
	}
	
	std::cout<< sum;
}

이미지 링크
자료 링크