최소 신장 트리 : 노드를 모두 연결하는 트리에서 가장 짧게 연결할 수 있는 트리
(가장 적은 비용으로 모든 노드를 연결)
크루스칼 알고리즘은 그래프가 주어졌을 때 최소 신장 트리를 찾는 알고리즘이다.
위 그래프에서 최소 신장 트리는 선으로 굵게 칠해진 부분들이다.
우선 크루스칼 알고리즘을 구현 하기전에 Union-Find 알고리즘을 알아야 한다.
<Union-Find 알고리즘(합집합 찾기)>
또 다른 이름으로는 서로소 집합(disjoint-set)알고리즘 이라고도 부른다.
이 알고리즘은 두 개의 노드가 주어졌을 때 서로 같은 집합인지 아닌지 판별해준다.
<Union_Find 알고리즘 코드>
#include<iostream>
using namespace std;
int d[11];
int n = 10;
int find_parent(int a) //집합의 부모(루트)를 찾아줌
{
if (d[a] == a)return a; //루트면 반환
return d[a] = find_parent(d[a]);
}
void make_union(int a, int b) // 집합끼리의 루트를 합쳐줌
{
a = find_parent(a);
b = find_parent(b);
if (a > b)d[a] = b; //루트 끼리 연결
else d[b] = a;
}
bool is__union(int a, int b)
{
return find_parent(a) == find_parent(b); //루트가 같으면 true
}
int main()
{
for (int i = 1; i <= n; i++)
{
d[i] = i; //연결 안되있는 노드는 자신의 부모는 자신임
}
//1,2,3을 같은 집합으로 만듬
make_union(1,2);
make_union(2,3);
//4,5를 같은 집합으로 만듬
make_union(4, 5);
cout << " 둘이 같은 집합인가? " << is__union(3, 4);
make_union(3, 4); //3,4도 연결
cout << "\n 둘이 같은 집합인가? " << is__union(3, 4);
return 0;
}
<크루스칼 알고리즘>
크루스칼 알고리즘은 위의 굵은 선, 즉 최소신장 트리를 찾는 알고리즘이다.
크루스칼의 알고리즘은 간단하다 그냥 제일 짧은 선들부터 고르는 것이다. 단, edge를 고를 때 edge의 두 개의 노드가 다른 집합일 경우에만 선택할 수 있다. (이미 연결되어 있는 집합을 다시 연결할 필요가 없다)
<크루스칼 알고리즘 코드>
그래프는 위의 그래프로 구현하였다.(a,b,c,d,e,f, 순서대로 1,2,3,4,5,6 로 생각)
C++
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class edge
{
public:
int n1, n2, distance;
edge(int n1, int n2, int distance)
{
this->n1 = n1;
this->n2 = n2;
this->distance = distance;
}
bool operator<(edge &others) //정렬을 위해 정의
{
return this->distance < others.distance;
}
};
int d[11];
int n = 10;
int find_parent(int a) //집합의 부모(루트)를 찾아줌
{
if (d[a] == a)return a; //루트면 반환
return d[a] = find_parent(d[a]);
}
void make_union(int a, int b) // 집합끼리의 루트를 합쳐줌
{
a = find_parent(a);
b = find_parent(b);
if (a > b)d[a] = b; //루트 끼리 연결
else d[b] = a;
}
bool is__union(int a, int b)
{
return find_parent(a) == find_parent(b); //루트가 같으면 true
}
void kruskal(vector<edge> &v)
{
for (int i = 1; i <= n; i++)
{
d[i] = i; //연결 안되있는 노드는 자신의 부모는 자신임
}
sort(v.begin(), v.end()); //edge(선)을 오름차순으로 정렬
int sum = 0;
for (int i = 0; i < v.size(); i++) //제일 짧은 선부터 연결시킴
{
int n1 = v[i].n1;
int n2 = v[i].n2;
int distance = v[i].distance;
if (!is__union(n1, n2)) //두개의 노드가 다른 집합이면 연결
{
make_union(n1, n2);
sum += distance; //연결되는 선들 합 구하기
printf("edge : %d - %d (%c - %c) \n", n1, n2,'a'+n1-1,'a'+n2-1);
}
}
printf("최소신장 트리의 총 거리: %d\n", sum);
}
int main()
{
vector<edge> v;
v.push_back(edge(1, 2, 6));
v.push_back(edge(1, 3, 3));
v.push_back(edge(2, 3, 2));
v.push_back(edge(2, 4, 5));
v.push_back(edge(3, 4, 3));
v.push_back(edge(3, 5, 4));
v.push_back(edge(4, 5, 2));
v.push_back(edge(4, 6, 3));
v.push_back(edge(5, 6, 5));
//그래프의 모든 선을 vector에 넣어줌
kruskal(v); //크루스칼 알고리즘
return 0;
}
코틀린
import java.io.*
val bw = BufferedWriter(OutputStreamWriter(System.out))
class Edge(var n1: Int, var n2: Int, var distance: Int)
val v = mutableListOf<Edge>().apply {
add(Edge(1, 2, 6))
add(Edge(1, 3, 3))
add(Edge(2, 3, 2))
add(Edge(2, 4, 5))
add(Edge(3, 4, 3))
add(Edge(3, 5, 4))
add(Edge(4, 5, 2))
add(Edge(4, 6, 3))
add(Edge(5, 6, 5))
}
val parent = IntArray(10)
val n = 9
fun findRoot(node: Int): Int {
if (parent[node] == node) return node
parent[node] = findRoot(parent[node])
return parent[node]
}
fun isUnion(a: Int, b: Int) = findRoot(a) == findRoot(b)
fun makeUnion(a: Int, b: Int) {
val n1 = findRoot(a)
val n2 = findRoot(b)
if (n1 > n2) parent[n1] = n2
else parent[n2] = n1
}
fun kruskal() {
for (i in 0..n) {
parent[i] = i
}
v.sortWith { a, b -> a.distance.compareTo(b.distance) }
var sum = 0
for (i in 0..v.size - 1) {
val n1 = v[i].n1
val n2 = v[i].n2
val distance = v[i].distance
if (!isUnion(n1, n2)) {
makeUnion(n1, n2)
sum += distance
bw.write("edge : $n1 - $n2 (${'a' + n1 - 1} ${'a' + n2 - 1}) \n")
}
}
bw.write("최소신장 트리의 총 거리: $sum")
}
fun main() {
kruskal()
bw.flush()
}
궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.
반응형