알고리즘 : 최소 스패닝 트리(Minimum Spanning Tree) - 크루스칼 알고리즘 구현하기
최소 스패닝 트리는 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말합니다.
최소 스패닝 트리를 만들기 위한 조건은 아래와 같습니다.
- 본래의 그래피의 모든 노드를 포함해야 합니다.
- 간선의 가중치의 합이 최소여야 합니다.
- 모든 노드가 서로 연결되어 있어야 합니다.
- Cycle이 존재하지 말아야 합니다.
최소 스패닝 트리를 구하기 위한 대표적인 알고리즘이 2가지가 있습니다.
첫번째는 크루스칼 알고리즘(Kruskal Algorithm)이며, 두번째는 프림 알고리즘(Prim Algorithm)입니다.
이번 시간에는 크루스칼 알고리즘에 대해 알아보겠습니다.
크루스칼 동작 원리
1) 모든 간선들의 가중치를 오름차순으로 정렬합니다
2) 가중치가 가장 작은 간선부터 선택합니다.
3) 선택한 간선이 사이클을 만들지 않는다면, 두 개의 노드를 연결합니다.
4) 모든 노드를 연결할 때까지 1) ~ 3)의 과정을 반복합니다.
크루스칼 동작 과정
아래와 같은 그래프가 있다고 가정합니다.
노드는 1부터 7까지 있고, 모든 노드가 연결되지 않은 독립된 상태입니다.
노드 1과 노드 2의 간선의 가중치는 3입니다.
다른 모든 연결된 간선도 가중치를 가지고 있습니다.
이 그래프를 크루스칼 알고리즘을 이용하여, 최소 스패닝 트리를 찾아보도록 하겠습니다.
먼저 Parent 배열을 만들고, 각 주소에 각 노드로 초기화합니다. Parent 배열은 각 연결된 부분의 가장 상단의 부모가 공통인지를 검사하여, 각 노드가 연결되어 있는지, 독립하여 존재하는지 검사하기 위해 사용됩니다. (즉, 두 노드를 연결할 때, Cycle이 발생하지 않도록 검사하기 위해 필요합니다.)
모든 간선은 가중치의 값을 오름차순으로 정렬하도록 합니다.
간선의 가중치가 가장 낮은 {2} 와 {3}을 연결시킵니다.
To의 Parent는 From의 최 상위의 부모로 지정합니다.
그러면 [2]에는 From인 3이 부모가 됩니다.
이러한 과정을 반복합니다.
노드 1과 노드 2를 연결하면 사이클이 발생하여 연결되지 못합니다. 또한 노드 5와 노드 6, 노드 5와 노드 4도 동일하게 사이클을 발생시키기 때문에 연결되지 못합니다.
크루스칼 알고리즘을 동작시키면, 아래와 같이 최소 스패닝 트리가 구해지고,
최소 비용의 값은 14가 됩니다.
크루스칼 구현
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <queue>
#include <stack>
#include <list>
using namespace std;
// 간선의 정보를 나타낼 구조체를 정의합니다.
struct Edge {
int from, to, weight;
Edge(int f, int t, int w) {
from = f;
to = t;
weight = w;
}
};
vector<Edge> v; // 모든 간선의 정보를 담음
int N; // 노드의 수
int M; // 간선의 수
int result = 0; // 최소 스패닝 트리의 모든 가중치의 합
int parent[100001]; // Parent 배열
// 입력정보
void inputData() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int f, t, w;
cin >> f >> t >> w;
v.push_back(Edge(f, t, w));
}
}
void printV() {
for (int i = 0; i < M; i++) {
cout << v[i].from << " " << v[i].to << " => " << v[i].weight << '\n';
}
}
// 가중치 오름차순으로 정렬하기 위한 compare 함수
bool comp(const Edge& e1, const Edge& e2) {
return e1.weight < e2.weight;
}
// 최상위의 부모노드를 구합니다.
int getParent(int x) {
if (x == parent[x]) return x;
else
return parent[x] = getParent(parent[x]);
}
// 두 노드를 연결합니다.
void Union(int x, int y)
{
x = getParent(x);
y = getParent(y);
if (x == y) return ; // 두 노드의 최상위 부모가 동일한지 검사합니다.
parent[y] = x;
}
// 사이클을 이루는지 확인합니다.
bool isCycle(int x, int y) {
x = getParent(x);
y = getParent(y);
if (x == y)
return true;
return false;
}
void solve() {
sort(v.begin(), v.end(), comp); // 가중치 오름차순으로 간선을 정렬합니다.
for (int i = 1; i <= N; i++) parent[i] = i; // 우선 parent 배열에 각 노드로 초기합니다.
// 두 노드를 연결하였을 때, 사이클을 이루지 않는다면, 두 노드를 연결시킵니다.
for (int i = 0; i < v.size(); i++) {
if (isCycle(v[i].from, v[i].to) == false) {
// cout << " Union : " << v[i].from << " " << v[i].to << " w : " << v[i].weight << '\n';
Union(v[i].from, v[i].to);
result += v[i].weight; // 가중치의 모든 합을 구합니다.
}
}
}
void printData() {
cout << result;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
inputData();
solve();
printData();
return 0;
}