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

Spanning Tree

그래프 내의 모든 정점을 포함하는 트리를 의미한다. 

 

Spanning Tree의 특징

• Tree의 특수한 형태로 모든 정점이 연결되어 있어야 한다.
• 하나의 그래프에 여러개의 스패닝 트리가 존재할 수 있다.
• 사이클이 존재하면 안된다.
• N개의 정점을 정확히 N-1개의 간선으로 연결해야한다.

---

Minimum Spanning Tree (MST)

사용된 간선들의 가중치 합이 최소인 Spanning Tree를 의미한다.

MST의 특징

• 간선의 가중치의 합이 최소여야한다.
• Spanning Tree의 특징을 가져야한다.

MST의 구현 방법

대표적인 MST알고리즘은 크루스칼과 프림 알고리즘이 있다. 이번시간엔, 크루스칼에 대해서만 설명할 것이다.

---

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

모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에, 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차례대로 그래프에 연결하는 것이 이 알고리즘의 핵심이다.

 

동작 방법

1. 간선들의 가중치를 기준으로 오름차순 정렬한다.
2. 정렬된 간선리스트의 앞에서부터 사이클을 형성하지 않는 간선을 선택한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다. 

(끝날 때까지 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;
}
//두 노드가 같은 그래프에 존재하면 1, 아니면 0
int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, 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() {
	int n, m; //정점 간선
	cin >> n >> m;

	int a, b, distance;
	vector<Edge> v;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> distance;
		v.push_back(Edge(a, b, distance));
	}

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

	int parent[10000];
	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);
		}
	}
	cout << sum;
}