최소비용 신장 트리... Kruskal Minimum Cost Spanning Tree

 최근 알고리즘 관련 포스팅을 하면서 부터 방문자는 부쩍 늘었는데, 어찌된 것인지 덧글은 더더욱 줄어든 느낌이다. 소스를 보고, 과제로 제출하거나, 참고하는 것도 좋지만 덧글도 좀 남겨주길...

 플로이드나 연쇄행렬 알고리즘의 경우 동적 계획법이였다. 이번의 크루스칼 최소비용 신장 트리의 경우는 탐욕적인 방법으로 분류되는 알고리즘이다. 동적 계획법이 과거의 결과를 현재에 재사용하는데 중점을 둔 기법이였다면, 탐욕적인 방법은 과거나 미래는 생각하지 않고, 현재 가장 최적이라고 생각되는 결과만을 취한다. 그래서 어떤 경우에도 현재의 최적이라고 생각되는 결과를 취하지만, 최종적으로 결과를 종합 했을 때, 그 결과가 꼭 최적인 된다고는 볼 수 없다. 크루스칼 최소비용 신장 트리 알고리즘의 경우 언제나 최종적인 결과도 최적이 된다(고 책에 나온다).

 크루스칼 알고리즘의 원리는 어렵지 않다. 간단하게 얘기하면 다음의 네가지 과정이 전부다.
  1. 그래프 G의 모든 이음선을 가중치에 따라 오름차순으로 정렬한다.
  2. 그래프 G에 가중치가 가장 작은 이음선을 삽입하는데 이때 사이클을 형성하는 이음선은 삽입할 수 없으므로 그 다음으로 가중치가 작은이음선을 삽입한다.
  3. 그래프 G에 n-1개의 이음선을 삽입할 때까지 2.를 반복한다.
  4. 그래프 G의 이음선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.
 이 과정 중에 사이클을 형성하는 이음선을 삽입할 수 없다는 조건에서, 아래의 소스에서는 서로소의 개념이 들어간다. 참고자료의 pseudo code를 바탕으로 짰으니, 그 책을 보면서 보면 좀 더 쉽게 이해할 수 있을 것 이다. 여기서의 입력 역시 참고자료에 나오는 책에 있는 예이다.
크루스칼 알고리즘에서 쓰일 텍스트 파일(kruskal_array.txt)
5 7
 0  1  3 99 99
 1  0 99  6 99
 3  3  0  4  2
99  6  4  0  5
99 99  2  5  0

최소비용 신장 트리를 구하는 크루스칼 알고리즘

#include <stdio.h>
#include <malloc.h>

typedef struct Edge // 이음선을 나타내는 구조체
{
int vertex[2]; // 시작점과 끝점
int cost; // 가중치
}Edge;

int** make_array(int n); // 배열 만들기
void read_array(int* G[], int n); // 파일에서 배열값 읽기
void convert_array_to_edge(int* G[], Edge E[], int n); // 배열을 이음선으로 변환
void print_edgy(Edge E[], int n); // E 이음선 집합 출력

void kruskal(int n, int m, Edge E[], Edge F[]); // 크루스칼 알고리즘
void sort(Edge E[], int m); // 거품 정렬
void merge(int p, int q, int U[]); // 집합(서로소)을 합치는 함수
int find(int i, int U[]); // 해당 정점이 어떤 집합에 속하는지 찾는 함수
FILE* file;

int main()
{
file = fopen("kruskal_array.txt", "r");
if(file == NULL) {
perror("File open error");
return 0;
}

int n, m;
// n개의 정점과 m개의 이음선을 가진...
fscanf(file, "%d %d", &n, &m);

int** G;

Edge* E = (Edge *) malloc(sizeof(Edge)*(m-1)); // 이음선
Edge* F = (Edge *) malloc(sizeof(Edge)*(n-2)); // 최소비용 신장트리

G = make_array(n); // 배열 만들기
read_array(G, n); // 파일에서 배열 정보 읽기
convert_array_to_edge(G, E, n); // 배열 정보를 이음선 정보로 변환

printf("\n## Kruskal Minimum Cost Spanning Tree ##\n");
// 크루스칼 알고리즘을 돌린 최소 비용 신장 트리를 F 이음선 집합에 삽입
kruskal(n, m, E, F);

// 최소 비용 신장 트리 결과 출력
printf("\nMinimum Cost Spanning Tree F is\n");
print_edgy(F, n-1);

fclose(file);

return 0;
}

void print_edgy(Edge E[], int n) // E 이음선 집합 출력
{
int i;
for(i = 0; i < n; i++)
if(E[i].cost != 0)
printf("v%d -> v%d, cost= %d\n", E[i].vertex[0]+1, E[i].vertex[1]+1, E[i].cost);
}

int** make_array(int n) // N x N 배열 만들기
{
int i;
int** array;
n--;
array = (int**)malloc(sizeof(int*)*n);
for(i = 0; i <= n; i++)
array[i] = (int*)malloc(sizeof(int)*n);

return array;
}

void read_array(int *G[], int n) // 파일에서 배열 값을 읽어 배열 G에 저장
{
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
fscanf(file, "%d", &G[i][j]);
}

// 배열 정보를 이음선 정보로 변환
void convert_array_to_edge(int *G[], Edge E[], int n)
{
int i, j, num = 0;
for(i = 0; i < n; i++) // 배열의 정보를 이음선 구조체에 삽입
for(j = i; j < n; j++) {
if( G[i][j] != 0 && G[i][j] != 99 ) {
E[num].vertex[0] = i;
E[num].vertex[1] = j;
E[num].cost = G[i][j];
num++;
}
}
}

void kruskal(int n, int m, Edge E[], Edge F[]) // 크루스칼 알고리즘
{
int i, j, k;
int p, q; // 서로소 체크를 위한 집합을 가리키는 변수
int num = 0;
int* U = (int*)malloc(sizeof(int)*(n-1)); // 서로소 집합 선언
Edge e;

printf("\nBefore Sort, set of Edges E\n");
print_edgy(E, m);
sort(E, m); // E에 속한 m개의 이음선을 가중치가 작은 것부터 차례로 정렬
printf("\nAfter Sort, set of Edges E\n");
print_edgy(E, m);

for (i = 0; i < n; i++) // 서로소 집합 초기값 대입
U[i] = i;

k = 0;
while(num < n-1) { // 이음선의 수가 n-1보다 작을 동안...
e = E[k]; // 아직 고려하지 않은 이음선 중 가중치가 최소인 이음선
i = E[k].vertex[0]; // i, j = e에 연결된 정점
j = E[k].vertex[1];
p = find(i, U); // p = i가 속하는 서로소 집합을 가리킴
q = find(j, U);
if(p != q ) { // p와 q 가 서로소이면..
merge(p, q, U); // p, q가 속한 집합을 합침
F[num] = e; // e를 F에 추가
num++;
}
k++;
}
}

int find(int i, int U[]) // i가 집합 U의 어느 집합에 속하나?
{
int j;
j = i;
while(U[j] != j)
j = U[j];
return j;
}

void merge(int p, int q, int U[]) // p, q를 집합 U에 합칩
{
if (p < q) // p는 합병된 집합을 가리키는 포인터
U[q] = p; // q는 더 이상 집합을 가리키는 포인터가 아님
else
U[p] = q;
}

void sort(Edge E[], int m) // E 엣지 집합의 가중치를 정렬하기 위한 함수
{
int i, Sorted = 0;
Edge tmp;
while( !Sorted ) { // 정렬이 완료되지 않았으면..
Sorted = 1;
for(i = 1; i < m; i++) {
if( E[i-1].cost > E[i].cost ) {
tmp = E[i-1];
E[i-1] = E[i];
E[i] = tmp;
Sorted = 0;
}
}
}
}

결과는 다음과 같다.
 교재에 나온 pseudo code 대로 짠다고 애 먹었다. 배열을 이음선(Edge)으로 변환하는 부분이나, 서로소를 쓰는 개념은 이해가 안되서 꽤나 오랜시간 끙끙거렸던 부분이다.
    참고자료
  • 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

by sakuragi | 2007/05/02 01:21 | :: R space :: 과제 | 트랙백(1) | 덧글(31)

트랙백 주소 : http://sakuragis.egloos.com/tb/3365963
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from My Life ..... at 2007/06/21 17:42

제목 : 최소비용 신장트리 Kruskal Minimum C..
http://sakuragis.egloos.com/tb/3365963 ...more

Commented by 슈와 at 2007/05/02 01:29
사정상 본문은 읽지 않았습니다. 다음 과제인거 같거든요 -_ㅠ
Commented by 환상경 at 2007/05/02 21:54
요즘은 계속 알고리즘에 관한 포스팅이군요 ㅋ
저도 나중에 시도해봐야겠네요 그대 sakuragi님의 포스팅을 참고좀 하겠습니다. ^^
Commented by sakuragi at 2007/05/03 01:32
슈와, 고생하시는군요. 힘내시길~ ^^;
환상경, 네, 요즘 하는게 이거 밖에 없는 것 같네요. T_T
Commented by ㅇㅇ at 2007/05/30 16:41
음....알고리즘이 좀 잘못됬네요..일단 v1->v42가 나오면 안되는거고..크루스컬 알고리즘에서도 문제가 있군요. 다른 그래프로 해도 결과값이 잘못 나오구요. 사실 이 코딩 안에 있는 저 그래프로 하여도..마지막에 f[4]에..서클이 형성되는 값이 입력이 됩니다..단지 출력할때 반복문에서 마지막껄 출력하지 않도록 n-1로 하였네요.. 다른 그래프로 손으로 직접 그려가면서 해본 결과..출력할때 n-1을 해도 서클을 형성하게 되네요
Commented by ㅇㅇ at 2007/05/30 17:35
아, 제가 잘못생각했네요. 죄송합니다.크루스칼 맞네요
Commented by sakuragi at 2007/05/30 19:27
ㅇㅇ, 출력 부분에 문제가 있었군요. 일단 그 부분은 수정해서 다시 올렸습니다. 지적 감사드립니다. :)
혹시나 뭔가 이상하다고 생각되는 점이 있으시면, 저는 참고 자료에 있는 책을 참고로 프로그램을 짰으므로, 참고 자료에 있는 책의 해당부분을 보시면 될 듯 합니다. :D
Commented by 이엘 at 2007/06/01 18:20
으아앗! 크루스칼 구현 소스네요 ''
올리시느라 고생한거같아요 ''
마침 과제로 찾던중이라 참고할겸 가져가겠습니다 ^^
Commented by sakuragi at 2007/06/03 00:44
이엘, 넵, 유용하게 잘 사용하시길.. :)
Commented by 랭이 at 2007/11/07 00:46
숙제 관련해서 참고했습니다. 잘 보고갑니다 ^^
Commented by sakuragi at 2007/11/07 02:25
랭이, 네, 도움이 되셨으면 좋겠군요. :)
Commented by hwangsangh at 2007/11/26 01:15
감사합니다... 참고 잘 했씁니다..^^;;
Commented by sakuragi at 2007/11/28 01:20
hwangsangh, 네. 많은 도움이 되셨길... :D
Commented at 2007/12/02 01:31
비공개 덧글입니다.
Commented by sakuragi at 2007/12/03 23:47
네, 유용하게 쓰시길..
Commented by ㅠㅠ at 2008/05/09 14:30
안녕하세요 정말 잘 짜신 것 같은데 입력 텍스트 파일에서 맨 윗줄의 5 7은 무슨 값인지요?
Commented by sakuragi at 2008/05/10 02:27
ㅠㅠ, 물어보신 것은 소스 안에 주석으로 적혀져 있습니다.
main() 함수 안에 있는 아래 부분을 위한 값 입니다.
---------------------------------------------
// n개의 정점과 m개의 이음선을 가진...
fscanf(file, "%d %d", &n, &m);
---------------------------------------------
좀 더 자세한 설명은 사이텍 미디어에서 나온 '알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역', 이 책에서 해당 부분을 찾아보시면 될 겁니다. 되도록 이 책에서 명시하고 있는 그대로 짜려고 노력했으니까요.
Commented by kamsa at 2008/11/06 13:02
사실 소스를 봐도 잘 모를 정도로 해매고 있지만 정말 빛과같은 도움 되었습니다,
잘받아 갈께요
Commented by sakuragi at 2008/11/09 00:52
많은 도움이 되셨다니 다행이네요 :)
Commented by to비 at 2008/12/02 15:52
감사합니다 과제로 찾던 소스인데 많은 도움이 되었어용
Commented by sakuragi at 2008/12/04 01:41
도움이 되셨다니 다행이네요~ ^^
Commented by to비 at 2008/12/03 20:30
이음선을 6이상 하면 컴파일중 최소비용트리는 나오지 않는데 왜 그런걸까요???
Commented by sakuragi at 2008/12/04 01:42
어떠한 경우에 값이 나오지 않는지 입력값이나 그래프를 예시로 보여주세요. ^^
Commented by urung at 2008/12/04 00:49
서로소 알고리즘 부분에 문제가 있지 않나 싶네요

1 - 2
| |
3 - 4 이런식으로 연결된 그래프가 있다면
5

1 2 3 4 5
1-2를 연결하고 1 1 3 4 5
3-4를 연결하고 1 1 3 3 5
1-3을 연결하고 1 1 1 3 5
2-4을 연결할려고 할때 1 1 1 1 5 가 되어 사이클이 형성됩니다.

따라서 merge()를 할때 번호가 변경당하는 쪽은 같은 번호가 잇다면 다같이 변경해 주어야
될것 같네요(위의 경우에 1-3을 연결할때 3번째인자의값만 1로 바꾸는게 아니라 4번째 인자의 값도 같이 바꾸어야 합니다. 1 1 1 1 5)
Commented by admin at 2011/11/21 18:53
과제에 많은 도움이 됬습니다 감사합니다~
Commented by 이거그냥 at 2012/11/22 11:20
과제에 많은 도움이 되었습니다. 알고리즘을 많이 어려워해서..ㅠㅠ 아무튼 감사합니다!
Commented by 도와주세요 at 2015/06/18 17:09
57
0 1 3 99 99
1 0 99 6 99
3 3 0 4 2
99 6 4 0 5
99 99 2 5 0
텍스트파일을 이렇게 만들고
실행했더니 invalid aloocation size 오류가 뜨네요. .ㅠ 뭐가 문젤까요?
Commented by sakuragi at 2015/06/23 11:00
첫 라인은 57이 아니라 5 7 입니다.
중간에 space가 들어가야 합니다.
Commented by KSW at 2015/11/03 12:02
MST 검색해서 오게 되었는데, 결과창 폰트가 예뻐서 여쭤보고 싶은데 어떤 폰트인가요???
Commented by sakuragi at 2015/11/04 17:38
은반달 글꼴이었던 걸로 기억합니다.
Commented by 정성현 at 2015/12/02 22:41
오름차순을 내림차순으로 바꾸는건 어떻게하나요?!
Commented by JJO at 2017/05/28 21:43
저는 동적할당으로 N입력받아서 NxN 이차원 배열 만들어서 거기에 올려주신 kruskal썼더니 heap에 손상이 왔다고 뜨더라구요.... 어디에서 문제가 나는건지 알 수 있을까요???ㅠ

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: