크루스칼 알고리즘 (Kruskal)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결할 때 쓰이는 알고리즘이다.(ex : 도시를 도로로 연결하고자 할 때 가장 적은 비용으로 연결을 위해 사용)

 

▷노드 : 출발지와 도착지를 나타내는 지점.

▷간선 : 각 노드를 잇는 선으로 간선마다 비용이 있다.

 

위와 같이 비용 그래프가 이루어져 있다고 해보자.

크루스칼 알고리즘에서는 총 (노드의 갯수 - 1)개의 간선을 비용이 적은 순서대로 뽑는다.

단, 여기서 중요한 점은 사이클을 형성하지 않는 간선만 선택하는 것이다.(여기에서 앞서 배웠던 Union-Find 알고리즘이 사용된다.)

 

 

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

using namespace std;

int parent[8];
class Edge {
public:
	int node[2];
	int dis;

	Edge(int a, int b, int dis) {
		this->node[0] = a;
		this->node[1] = b;
		this->dis = dis;
	}

	// operator를 사용하여 dis가 작은 순서대로 sort가 되도록 함
	bool operator <(Edge & edge) {
		return this->dis < edge.dis;
	}
};

// 부모를 찾는 함수 (재귀 사용)
int get_parent(int parent[], int n) { 
	int result = 0;
	if (parent[n] == n) return n;
	return result = get_parent(parent, parent[n]);
}

// 두 노드의 부모를 합치는 함수
void union_parent(int parent[], int a, int b) {
	int p_a = get_parent(parent, a);
	int p_b = get_parent(parent, b);
	if (p_a < p_b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

// 두 노드의 부모가 같은지 확인하는 함수
int is_Union(int parent[], int a, int b) {
	int p_a = get_parent(parent, a);
	int p_b = get_parent(parent, b);
	if (p_a == p_b) {
		return 1;
	}
	else return 0;
}

int main() {
	vector<Edge> v;
	
	// 노드 사이의 간선을 생성한다.
	v.push_back(Edge(1, 7, 12));
	v.push_back(Edge(7, 4, 13));
	v.push_back(Edge(4, 2, 24));
	v.push_back(Edge(1, 5, 17));
	v.push_back(Edge(1, 4, 28));
	v.push_back(Edge(1, 2, 67));
	v.push_back(Edge(5, 2, 62));
	v.push_back(Edge(5, 3, 20));
	v.push_back(Edge(5, 6, 45));
	v.push_back(Edge(3, 6, 37));
	v.push_back(Edge(5, 7, 73));

	sort(v.begin(), v.end());

	int sum = 0;

	for (int i = 1; i <= 7; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < v.size(); i++) {
		if (!is_Union(parent, v[i].node[0], v[i].node[1])) { // 두 노드가 같은 부모를 가지고 있지 않을 경우에만 간선 추가
			union_parent(parent, v[i].node[0], v[i].node[1]);
			sum += v[i].dis;
		}
	}

	printf("최소비용 = %d", sum);
}

 

◇ 크루스칼 알고리즘의 시간복잡도는 사실상 Union-Find 알고리즘과 정렬 알고리즘의 시간복잡도의 합으로 나타낼 수 있기 때문에 사실상 정렬 알고리즘의 시간 복잡도와 같다고 할 수 있다.