Kruskal 알고리즘
탐욕(Greedy) 알고리즘의 한 종류로 그래프의 있는 모든 정점을 최소 비용으로 연결할 때 사용한다.
- 그래프 : 정점(node 혹은 vertex)과 간선(edge)으로 이루어져있으며 각 간선에는 가중치(weight)가 부여된다.
결론적으로 Kruskal 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하기 위한 알고리즘이다.
- 신장 트리(Spanning Tree) : cycle을 발생시키지 않으면서 모든 노드를 포함하며 각 노드는 최소한 하나의 간선을 포함하는 트리를 말한다.
크루스칼(Kruskal) 알고리즘의 진행순서
- 주어진 그래프에 있는 모든 간선(Edge)을 가중치를 기준으로 오름차순 정렬을 한다.
- 모든 노드를 생성한다.
- 정렬된 간선 중 가중치가 낮은 것부터 선택해 간선과 양 끝 단인 두 정점을 연결한다. 이 때, 선택된 간선의 두 정점을 선택해 cycle을 가지게 된다면 해당 간선은 선택하지 않는다. 가중치가 같은 두 간선이 있을 경우 어떠한 간선을 선택해도 상관없다. 아래 예시는 가중치가 같으면 간선번호가 작은 것을 택하였다.
- 총 선택된 간선(edge)의 수가 (정점의 수- 1)이 될때 까지 진행한다. => 선택된 간선(edge)의 수가 정점의 수보다 같거나 많아진다면 반드시 cycle을 가지게 되기 때문이다.
Kruskal 알고리즘의 예시
-
그래프가 다음과 같이 주어진다.
-
주어진 간선(edge)를 가중치를 기준으로 오름차순 정렬을 한다.
-
모든 노드를 생성한다.
-
오름차순으로 정렬된 간선을 가중치가 낮은 것부터 선택한다.
아래에서는 크루스칼(Kruskal) 알고리즘을 c언어로 구현하였다. 출력으로는 MST(Minimum Spanning Tree)가 출력된다. 중요 부분에는 주석처리가 되어있으며, 2차원 배열인 A_matrix[5][5]에는 Spanning tree의 정보가 주어진다.
int A_matrix[5][5] = { {0,1,3,0,0}, {1,0,3,6,0} , {3,3,0,4,2}, {0,6,4,0,5},{0,0,2,5,0} };
위의 A_matrix는 다음과 같은 정보를 포함한다.
v1-v4가 0이라는 것은 두 정점은 연결되어 있지 않다는 것이며
v1-v2가 1이라는 것은 두 정점은 연결되어 있으며 해당 노드의 가중치는 1이라는 것을 의미합니다.
VERTEX_NUM, EDGE_NUM, A_matrix[][]는 상황에 맞게 바꾸시면 됩니다.
c언어로 kruskal 알고리즘 구현
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef struct
{
int start;
int end;
int weight;
}edge;
typedef struct
{
int parent;
int depth;
}universe;
#define VERTEX_NUM 5 // 정점의 갯수
#define EDGE_NUM 7 // 노드의 갯수
int A_matrix[5][5] = { {0,1,3,0,0}, {1,0,3,6,0} , {3,3,0,4,2}, {0,6,4,0,5},{0,0,2,5,0} }; // MST를 구하고 싶은 그래프
void kruskal(int n, int m, edge* E, edge* F);
void input(int vertex1, int vertex2, int w);
void initial(int n);
int find(int i);
void makeset(int i);
int equal(int p, int q);
void merge(int p, int q);
edge edge_info[EDGE_NUM]; // 모든 edge를 저장하기 위해
universe U[VERTEX_NUM + 1];
int indexs = 0; // edge들을 all_edge에 넣기위해
int f_index = 0;
int main()
{
edge result[EDGE_NUM];
for (int i = 0; i < VERTEX_NUM; i++) {
for (int j = i + 1; j < VERTEX_NUM; j++) {
if (A_matrix[i][j] != 0) {
input(i + 1, j + 1, A_matrix[i][j]);
}
}
}
// kruskal 알고리즘 작동
kruskal(VERTEX_NUM, EDGE_NUM, edge_info, result);
int kruscal_MST[VERTEX_NUM][VERTEX_NUM] = { 0 };
for (int i = 0; i < f_index; i++) {
kruscal_MST[result[i].start - 1][result[i].end - 1] = result[i].weight;
kruscal_MST[result[i].end - 1][result[i].start - 1] = result[i].weight;
}
printf(" 1 2 3 4 5 -> vertex number in the MST \n");
for (int i = 0; i < VERTEX_NUM; i++) {
printf("%d ", i + 1);
for (int j = 0; j < VERTEX_NUM; j++) {
printf("%d ", kruscal_MST[i][j]);
}
printf("\n");
}
printf("ㄴ vertex number in the MST \n");
}
void input(int vertex1, int vertex2, int w)
{
edge_info[indexs].start = vertex1;
edge_info[indexs].end = vertex2;
edge_info[indexs].weight = w;
indexs += 1;
}
void kruskal(int n, int m, edge* E, edge* F)
{
// 가중치 정렬
for (int i = 0; i < m - 1; i++)
{
for (int j = i + 1; j < m; j++)
{
if (E[i].weight > E[j].weight)
{
edge temp = E[i];
E[i] = E[j];
E[j] = temp;
}
}
}
// 가중치가 같다면 노드 번호 작은것이 선택되도록 정렬
for (int i = 0; i < VERTEX_NUM; i++) {
for (int j = 0; j < VERTEX_NUM - 1 - i; j++) {
if (E[i].weight == E[i + 1].weight) {
if (E[i].start > E[i + 1].start) {
edge temp = E[i];
E[i] = E[i + 1];
E[i + 1] = temp;
}
}
}
}
// U 만들기
for (int i = 1; i < VERTEX_NUM + 1; i++)
{
U[i].parent = 0;
U[i].depth = 0;
}
// F 만들기
for (int i = 0; i < m; i++)
{
F[i].start = 0;
F[i].end = 0;
F[i].weight = 0;
}
//initial
initial(VERTEX_NUM);
// while문 시작
int find_start = 0;
while (find_start < VERTEX_NUM) // 총 edge수가 VERTE_NUM보다 작을때까지 반복
{
int i, j, p, q;
edge e = E[find_start];
i = E[find_start].start;
j = E[find_start].end;
p = find(i);
q = find(j);
if (!equal(p, q))
{
merge(p, q);
F[f_index] = E[find_start];
f_index += 1;
}
find_start++;
int count = 0;
// 모든 subset이 하나로 merge 되었는지 확인하기
for (int i = 1; i < EDGE_NUM + 1; i++)
{
if (U[i].parent == i)
count++;
}
// 자기 자신을 가리키는 U가 있다면 종료
if (count == 1) {
break;
}
}
}
// 초기에는 자기는 자기 자신을 가리키게
void initial(int n)
{
for (int i = 1; i < n + 1; i++) {
makeset(i);
}
}
// 각 요소의 집합 만들기
void makeset(int i)
{
U[i].parent = i;
U[i].depth = 0;
}
int find(int i)
{
int j;
j = i;
while (U[j].parent != j) // 부모가 자기 자신을 가리킬 때 까지
{
j = U[j].parent;
}
return j;
}
void merge(int p, int q)
{
// 한 쪽으로만 기우는 것 방지
if (U[p].depth == U[q].depth)
{
U[p].depth = U[q].depth;
U[q].parent = p;
}
// p의 depth가 더 크면 q를 p에 붙인다.
else if (U[q].depth < U[p].depth) {
U[q].parent = p;
}
// q의 depth가 더 크면 p를 q에 붙인다.
else {
U[p].parent = q;
}
}
int equal(int p, int q)
{
if (p == q)
return 1;
else
return 0;
}오류가 존재하면 댓글로 알려주세요.
Front-End Developer