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

 이번 과제는 최소비용 신장트리를 얘기할 때 항상 크루스칼 알고리즘과 함께 얘기되고, 비교되는 프림 알고리즘이다. 크루스칼 알고리즘에 비해서는 이해하기 쉬운 편이다. 각 변수에 어떤 값이 들어가는지 몇번 찍어(적어)보다 보면 금방 이해가 된다.

 프림 알고리즘의 원리는 어떻게 보면 크루스칼 알고리즘 보다 더 수월하다. 보통 사람이 생각하는 방식으로 답을 찾기 때문이다.
  1. 그래프 W에서 시작 정점을 선택한다.
  2. 선택한 정점에 부속된 모든 이음선 중에서 가중치가 가장 작은 이음선을 연결하여 트리를 확장한다.
  3. 이전에 선택한 정점과 새로 선택한 정점에 부속된 모든 이음선 중에서 가중치가 가장 작은 이음선을 삽입하는데, 사이클을 형성하는 이음선은 삽입 할 수 없으므로 그 다음으로 가중치가 작은 이음선을 선택한다.
  4. 그래프 W에 n-1개의 이음선을 삽입할 때 까지 3.을 반복한다.
  5. 그래프 W에 이음선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.
 참고 자료에 있는 책을 참고하면 크게 어렵지 않게 짤수 있다. 시간 복잡도는 이음선의 갯수가 많을 수록 프림 알고리즘의 효율이 좋아진다. 하지만 개인적으로는 짜는데 고생한 만큼 크루스칼 알고리즘이 마음에 든다.
프림 알고리즘에서 쓰일 텍스트 파일(prim_array.txt)
5
 0  1  3 99 99
 1  0  3  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* W[], int n); // 파일에서 배열값을 읽는 함수
void prim(int n, int* W[], Edge F[]); // 프림 알고리즘
void print_value(int nearest[], int distance[], int n, int num);
FILE* file;

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

int n;
fscanf(file, "%d", &n);

int i;
int** W;
Edge* F = (Edge*)malloc(sizeof(Edge)*(n-1));

W = make_array(n); // W 배열 생성
read_array(W, n); // 파일에서 W 배열값 정보 읽기

// 프림 알고리즘을 돌려서 나온 최소비용 신장 트리를 F 이음선 집합에 저장
prim(n, W, F);

// 최소비용 신장트리 결과 출력
printf("\n## Prim Minimum Cost Spanning Tree ##\n");
for(i = 0; i < n-1; i++)
printf("v%d -> v%d : %d\n", F[i].vertex[0]+1, F[i].vertex[1]+1, F[i].cost);

free(W);
free(F); 
fclose(file);

return 0;
}

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 *W[], int n) // 파일에게 배열값을 읽어 배열 G에 저장
{
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
fscanf(file, "%d", &W[i][j]);
}

void prim(int n, int* W[], Edge F[]) // 프림 알고리즘
{
int i, vnear = 0;
int min, num = 0;
Edge e;
int* nearest = (int*)malloc(sizeof(int)*(n-2));
int* distance = (int*)malloc(sizeof(int)*(n-2));

for(i = 1; i < n; i++) {
nearest[i] = 0; // 모든 정점에 대하여, Y에 속한 가장
distance[i] = W[0][i]; // 가까운 정점(nearest[i])은 v1로 초기화하고
} // Y로 부터의 거리(distance[i])는 vi와 v1을
// 연결하는 이음선의 가중치로 초기화한다.

print_value(nearest, distance, n, num+1); // nearest, distance 변화 값 출력
while( num < n-1) { // n-1개의 정점을 Y에 추가한다.
min = 99;
for(i = 1; i < n; i++) // 각 정점에 대하여 distance[i]를 검사하여
if( distance[i] >= 0 && distance[i] < min) { // Y에 가장
min = distance[i]; // 가까이 있는 정점(vnear)을 찾는다.
vnear = i;
}
e.vertex[0] = nearest[vnear]; // 이음선 구조체에 시작점과
e.vertex[1] = vnear; // 끝점 정보를 넣고
e.cost = min; // F 이음선 집합에 삽입한다.
F[num] = e;

distance[vnear] = -1; // vnear가 인덱스인 정점을 Y에 추가한다
for(i = 1; i < n; i++) // distance가 -1인 정점은 더 이상 고려대상이 아니다.
if(W[i][vnear] < distance[i]) { // Y에 속하지 않은 각 정점에 대하여,
distance[i] = W[i][vnear]; // Y로 부터의 거리(distande[i])를 갱신한다.
nearest[i] = vnear;
}
print_value(nearest, distance, n, num+2); // nearest, distance 변화 값 출력
num++;
}
}

void print_value(int nearest[], int distance[], int n, int num)
{
int i;
printf("%dth nearest\t\t distance\n ", num);
for(i = 1; i < n; i++)
printf("%3d", i+1);
printf("\t");
for(i = 1; i < n; i++)
printf("%3d", i+1);
printf("\n ");
for(i = 1; i < n; i++)
printf("%3d", nearest[i]+1);
printf("\t");
for(i = 1; i < n; i++)
printf("%3d", distance[i]);
printf("\n");
}
결과는 다음과 같다. 중간에 nearest와 distance의 변하는 값이 출력되도록 소스를 약간 추가하였다(07/05/09).
 정말 요즘 정신없이 이것만 하는 것 같다. 그래서 다른 과목은 거의 보지도 못하고 있다. 에고고...
    참고자료
  • 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

by sakuragi | 2007/05/03 02:10 | :: R space :: 과제 | 트랙백 | 덧글(11)

트랙백 주소 : http://sakuragis.egloos.com/tb/3369554
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented at 2007/05/08 20:40
비공개 덧글입니다.
Commented by sakuragi at 2007/05/08 21:45
멋쟁이~, prim 함수 내부의 nearest와 distance 선언에 문제가 있었네요. 문제가 있던 부분을 수정해서 Visual C++에서 컴파일이 되는 것을 확인 했습니다. :D
gcc에서는 컴파일시 에러가 나지 않았는데, Visual C++ 6.0에서는 문제가 생기네요. 파일 확장자를 .c 가 아닌 .cpp 로 저장하셔서 컴파일 하시면 에러가 나지 않으실껍니다. C의 탈을 썼지만 C 문법에는 미묘하게 안 맞나 보군요. 제가 프로그래밍을 워낙 못하다 보니... 그럼, 도움이 되셨길... ( __)
Commented by 멋쟁이 at 2007/05/09 22:06
감사해요~^^*
많은 도움되었어요~
자주놀러올게요~~ㅋㅋㅋ
Commented by sakuragi at 2007/05/11 11:21
멋쟁이, 네.. 자주 놀러오세요~ :)
Commented by 배고파 at 2008/05/25 23:03
천재군요...
몇일을 헤매다 반쯤 미쳤었는데...
멋져요.. 짝짝짝..
Commented by sakuragi at 2008/06/06 19:34
저도 엄청 헤맸습니다.
천재는 아니지만 칭찬은 감사합니다. ( __)
Commented by fishorange at 2008/10/13 22:10
자료 감사합니다. 쏙쏙 이해 되네요!!
Commented by sakuragi at 2008/10/20 13:16
많이 부족한데 도움이 되셨다니 다행입니다. :)
Commented by akaz at 2010/05/16 23:10
음... 뭔가 똑같이 카피하고 똑같은 내용의 txt를 썼는데 메모리 alloc 관련 에러가 뜨는듯 하네요;
Commented by sakuragi at 2010/05/19 15:00
저는 아무 문제가 없었습니다. VC++ 6에서의 컴파일도 확인하였으니... 더이상 제가 드릴 수 있는 도움은 없는 것 같은데요~ ^^
Commented by June! at 2014/05/16 15:58
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;
}

여기에 문제가 있는것 같습니다. array를 4칸 할당하고 for문으로 5번의 malloc을 수행한것 같습니다.

:         :

:

비공개 덧글

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

:+: sakuragi's Steam :+: