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

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

---

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

다음 노드들을 모두 한번씩 들르는 최소 경로를 알아보자!

---

비용이 짧은 순서대로 그래프에 포함시키자!!

일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에 모든 비용의 정보를 오름차순으로 정렬한 뒤에 비용이 작은 것부터 차근 차근 그래프에 포함시키면 된다. 단 사이클을 형성하는 경우는 포함에서 제외한다.

소스코드 구현 (C++)

#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;
}

bool FindParent(int parent[], int a, int b)
{
	a = GetParent(parent, a);
	b = GetParent(parent, b);

	return a == b ? true : false;
}
//간선 클래스
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()
{
	//노드
	int n = 7;
	//간선
	int m = 9;
	//간선 데이터를 가진 테이블
	vector<Edge> v;
	v.push_back(Edge(1, 6, 28));
	v.push_back(Edge(1, 2, 13));
	v.push_back(Edge(1, 4, 10));
	v.push_back(Edge(2, 3, 12));
	v.push_back(Edge(3, 4, 40));
	v.push_back(Edge(4, 7, 6));
	v.push_back(Edge(6, 7, 1));
	v.push_back(Edge(5, 6, 30));
	v.push_back(Edge(5, 7, 25));

	//오름차순 정렬
	sort(v.begin(), v.end());
	
	//각 정점이 포함된 그래프가 어디인지 저장
	int p[7];
	for (int i = 0; i < 7; i++) p[i] = i;

	int sum = 0;
	for (int i = 0; i < v.size(); i++)
	{
		//사이클 체크
		if (!FindParent(p, v[i].node[0] - 1, v[i].node[1] - 1))
		{
			sum += v[i].distance;
			UnionParent(p, v[i].node[0] - 1, v[i].node[1] - 1);
		}
	}
	cout << "연결 : ";
	for (int i = 0; i < 7; i++)
	{
		if (i != 6) cout << i << "-";
		else cout << i;
	}
	cout << endl;
	cout << "최소 비용은? : " << sum << endl;

	return 0;
}

출력 결과

---

노드들이 가지고 있는 각각의 간선 정보를 테이블로 만들고 이 정보를 토대로 최소비용 순서로 정렬을 한 후, 기존에 만들었던 합집합 찾기 알고리즘을 적용하여 사이클을 알아보고 사이클이 되지 않는 것들의 값으로 비용을 합하여 결과를 도출하였다. 시간복잡도는 O(Nlog₂N)이다.