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

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

 

최소 비용 신장 트리

 

Idea. 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까?

 

간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함

 

유의사항. 사이클이 형성되면 안된다.

--> 사이클이 발생하는지의 여부는 Union-Find알고리즘을 사용

순서.

1. 정렬된 순서에 맞게 그래프에 포함시킵니다.

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

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getParent(int parent[], int x)
{
	if (parent[x] == x) return x;

	return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
void unionParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);

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

}

int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a == b)
	{
		return 1;
	}

	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 parent[7];
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < v.size(); i++)
	{
		if (!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1))
		{
			sum += v[i].distance;
			unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
		}
	}

	printf("%d\n", sum);

}