크러스컬 알고리즘의 구현 및 실험

문제)

다음의 가중치가 주어진 도로망을 이용하여  실습에 주어진 코드로

최소 신장(생성) 트리를 출력하여라.

먼저  주어진 코드에  맞는 그래프 데이터 파일 "cities.dat" 파일을 만들고 

이것을 이용하여 실제 신장트리를 출력할 때  도시명이 출력되도록 하여라.   

C언어로 코드를 구현해보면 이렇게 작성할 수 있다.

#include <stdio.h>
#include<string.h>
#include <stdlib.h>
#define INF 10000
void set_init(int n);
int  set_find(int v);
char *clitiename[10]= {"서울","원주","강를","천안","논산","대전","광주","부산","대구","포항"};
void set_union(int s1, int s2);
typedef struct {
    int u, v;                   // (u,v)
    int w;                      // weight
} EDGE;

//G=(V,E)

EDGE *read_graph(char *GFile, int *m, int *n);
void KruskalMST(EDGE * elist, EDGE * T, int nedges, int nvertex);
int edge_cmp(const void *, const void *);
int check_cycle(EDGE E);

int main(int argc, char *argv[])
{
    int nedge, num_vertex, i;
    EDGE *Graph, *Tree;
    Graph = read_graph(argv[1], &nedge, &num_vertex);
    Tree = (EDGE *) malloc(sizeof(EDGE) * (num_vertex - 1));
    KruskalMST(Graph, Tree, nedge, num_vertex);

    for (i = 0; i < num_vertex - 1; i++)
        printf("%3s  %3s  %4d\n", clitiename[Tree[i].u],clitiename[ Tree[i].v], Tree[i].w);
}

EDGE *read_graph(char *GFile, int *m, int *n)
{
    FILE *fp;
    int i = 0;
    EDGE *elist;
    if ((fp = fopen(GFile, "r")) != NULL) {
        fscanf(fp, "%d%d", m, n); // total edge and vertex
        elist = (EDGE *) malloc(sizeof(EDGE) * (*m));
        while (i < *m) {
            fscanf(fp, "%d%d%d", &elist[i].u, &elist[i].v, &elist[i].w);
            i++;
        }
    } else {
        perror("error : can't read file");
    }
    return elist;
}

void KruskalMST(EDGE * Graph, EDGE * Tree, int nE, int nV)
{
    EDGE E;
    int ntree = 0, i = 0, setU, setV;
    qsort(Graph, nE, sizeof(EDGE), edge_cmp);
    set_init(nV);
    i=0;
    while (ntree < (nV - 1)) {
        E = Graph[i++];
        if ( check_cycle(E) )  {
            *Tree++ = E;
            ntree++;
            printf("(%s  %s):%d\n", clitiename[E.u], clitiename[E.v],E.w );
        }
    }
}

int check_cycle(EDGE E)
{
    int s1,s2;
        if((s1=set_find(E.u)) != (s2=set_find(E.v))){
        set_union(s1,s2);
        return 1;
    }else return 0;
}

int edge_cmp(const void *a, const void *b)   //for qsort
{
    EDGE *aa, *bb;
    aa = (EDGE *) a;
    bb = (EDGE *) b;
    return  ((aa->w) > (bb->w));
}

임의로 순서을 정해서 char *clitiename[10]= {"서울","원주","강릉","천안","논산","대전","광주","부산","대구","포항"};를 전역변수로 선언하여 숫자를 한글로 바꿔서 출력하게 하였습니다

dat파일을 보자면,

cites.dat

14  10  // 노드 수, 꼭지점 수
0   1   5
0   3   12
1   2   21
1   8   7
2   9   25
3   4   4
3   5   10
4   5   3
4   6   13
5   8   10
6   7   15
7   8   9
7   9   5
8   9   19

이렇게 만들었습니다. 서울을 0으로 시작하여 포항을 9로 정해놓았습니다.

 

출력결과물을 보면

이런식으로 잘 출력됩니다.