자료구조 3 - 3) 그래프 MST : 크루스칼, 프림

 

 

 

 

 

 

1. 신장 트리(spanning tree)

: 그래프 내의 모든 정점을 포함하는 트리이다. 사이클이 없어야 한다 !!

- n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가진다.

 

 

 

 

 

 

 

2. 최소비용 신장 트리(Minimum Spanning Tree)

: 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 신장 트리이다.

 

 

 

 

3. 크루스칼의 MST

 

 

1) 동작 과정

- 간선을 비용에 따라 정렬한다.

- 선택되지 않은 간선 중, 가장 비용이 적은 간선을 선택한다.

- 간선 두 정점의 대표 정점을 반환하고, 대표 정점이 기존 대표 정점과 일치하지 않으면 기존 집합과 새로운 집합을 합친다.

 

크루스칼 알고리즘 동작과정

 

 

 

 

- 탐욕적인 방법(greedy algorythm)

: 각 단계에서 최선의 방법을 선택하는 과정을 반복한다.

: 검증 필요

: Kruskal 알고리즘은 최적임이 증명되었다.

 

 

- union-find 알고리즘

: 원소가 어떤 집합에 속하는지 알아낸다.

Kruskal의 MST 알고리즘에서 사이클 검사에 이용한다.

 

 

 

2) 핵심 코드

// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType *g, GraphType *t)
{
     // 구현
    int edge_accepted = 0;
    HeapType h;
    int uset, vset;
    element e;              // 힙 요소
    
    init(&h);
    insert_all_edges(&h, g);
    set_init(g->n);
    
    while(edge_accepted < (g->n-1)){
        e = delete_min_heap(&h);
        uset = set_find(e.u);		
        vset = set_find(e.v);
        if(uset != vset){
            printf("(%d, %d) %d \n", e.u, e.v, e.key);
            edge_accepted++;
            t->adj_mat[e.u][e.v] = e.key;
            set_union(uset, vset);
        }
    }
}

 

 

 

3) 전체 코드

#include <stdio.h>
#include "minheap.h"
#include "unionfind.h"

#define MAX_VERTICES 100
#define INF 9999

typedef struct GraphType {
    int n;                    // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
     // 구현
    g->n = 0;
    for(int i=0; i<MAX_VERTICES; i++){
        for(int j=0; j<MAX_VERTICES; j++){
            g->adj_mat[i][j] = INF;
        }
    }
}

void insert_edge(GraphType *g, int start, int end, int key)
{
    if( start >= g->n || end >= g->n ){
        fprintf(stderr,"그래프 : 정점 번호 오류");
        return;
    }
     
     // ƒ⁄µÂ ª¿‘
    g->adj_mat[start][end] = key;
    g->adj_mat[end][start] = key;
}

/*  */
void read_graph(GraphType *g, char *filename)
{
     // 구현
    int number, u, v, key;
   
    FILE *fp;
    fp = fopen(filename, "rt");
   
    if (fp == NULL)
    {
        printf("file %s open error!\n", filename);
        return;
    }
   
    fscanf(fp, "%d\n", &number);
    g->n = number;
    
    // 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
    while(fscanf(fp, "%d %d %d\n", &u, &v, &key) != EOF){
        insert_edge(g, u, v, key);
    }

    fclose(fp);
}


/*  */
void write_graph(GraphType *g, char *filename)
{
     // 구현
    int i, j;
    FILE *fp;
    
    if (filename == NULL) fp = stdout;
    else {
         fp = fopen(filename, "wt");
        if (fp == NULL)
        {
            printf("file %s open error!\n", filename);
             return;
        }
    }
   
   fprintf(fp, "%d\n", g->n);

   // 구현: fprintf(fp, "%d\n", ...)을 사용한다
   for(i=0; i<(g->n); i++){
       for(j=0; j<(g->n); j++){
           if(g->adj_mat[i][j] != INF)
               fprintf(fp, "%d %d %d\n", i, j, g->adj_mat[i][j]);
       }
   }
   
    if (filename != NULL) fclose(fp);
}

// 인접 행렬이나 인접 리스트에서 간선들을 읽어서 최소 히프에 삽입
// 현재는 예제 그래프의 간선들을 삽입한다.
void insert_all_edges(HeapType *h, GraphType *g)
{
     // 구현
    for(int i=0; i<g->n; i++){
        for(int j=0; j<g->n; j++){
            if(i < j && g->adj_mat[i][j] != INF){
                element e;
                e.u = i;
                e.v = j;
                e.key = g->adj_mat[i][j];
                insert_min_heap(h, e);
            }
        }
    }
}

// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType *g, GraphType *t)
{
    // 구현
    int edge_accepted = 0;
    HeapType h;
    int uset, vset;
    element e;              // 힙 요소
    
    init(&h);
    insert_all_edges(&h, g);
    set_init(g->n);
    
    while(edge_accepted < (g->n-1)){
        e = delete_min_heap(&h);
        uset = set_find(e.u);       // 대표 정점 반환
        vset = set_find(e.v);
        if(uset != vset){           // 대표 정점이 다르면
            printf("(%d, %d) %d \n", e.u, e.v, e.key);
            edge_accepted++;
            t->adj_mat[e.u][e.v] = e.key;
            set_union(uset, vset);      // 합친다.
        }
    }
}

int main()
{
    GraphType g, t;        // 입력 그래프, 결과 트리
    
    graph_init(&g);
//    read_graph(&g, "input.txt");
    read_graph(&g, "input2.txt");

    graph_init(&t);
    t.n = g.n;
    
    printf("선택된 간선<순서대로> : \n");
    kruskal(&g, &t);
    
    printf("\n파일로 출력:\n");
    write_graph(&t, "output.txt");
    write_graph(&t, NULL);    // to stdout
    
    return 0;
}

 

 

 

 

4) kruskal의 MST 알고리즘 복잡도

: 크루스칼의 알고리즘은 대부분 간선을 정렬하는 시간에 좌우된다.

- 사이클 테스트 등의 작업은 비교적 매우 신속하게 수행된다.

 

: 네트워크의 간선 e개를 퀵정렬과 같은 효율적인 알고리즘으로 정렬하면 

크루즈칼 알고리즘의 시간 복잡도는 O(e * log(e)), 최악의 경우 O(e^2)

힙정렬은 최악의 경우에도 O(e * log(e))

 

 

 

4. 프림의 MST

: 시작 정점부터 출발하여 신장 트리 집합을 단계적으로 확장해 나간다.

: 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점을 선택하여 신장 트리 집합에 추가한다.

 

 

 

- dist[u] : <신장트리집합>에서 u까지의 최소거리

- selected[u] : 신장트리집합에 u를 넣으면 selected[u] = 1;

- connectVertex[u] = 신장트리집합에 넣을 때 u와 연결된 점

 

 

 

 

1) 핵심 코드

//
void prim(GraphType* g, int s)
{
    int i, u, v;

    for (u = 0; u<g->n; u++){
        distance[u] = INF;
        connectVertex[u] = s;       // 중요! 시작점 설정, connectVertex = 신장트리집합에 넣을 때 u와 연결된 점
    }
    
    distance[s] = 0;
    
    for (i = 0; i<g->n; i++) {
        u = get_min_vertex(g->n);       // 신장트리집합으로부터 비용이 가장 작은 노드
        selected[u] = TRUE;
        
        if (distance[u] == INF) return;
        
        printf("<%d %d> %d\n", connectVertex[u], u, distance[u]);
        printf("selected[] = \t");
        for(int j=0; j<g->n; j++){
            printf("%7d", selected[j]);
        }
        printf("\n");
        
        for (v = 0; v<g->n; v++)
            if (g->weight[u][v] != INF)
                if (!selected[v] && g->weight[u][v]< distance[v]){
                    distance[v] = g->weight[u][v];
                    connectVertex[v] = u;
                }
        
        printf("dist[] = \t\t");
        for(int j=0; j<g->n; j++){
            printf("%7d", distance[j]);
        }
        printf("\n\n");
        
    }
}

 

 

 

 

2) 전체 코드

 

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L

typedef struct GraphType {
    int n;    // 정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int selected[MAX_VERTICES];
int distance[MAX_VERTICES];
int connectVertex[MAX_VERTICES];

// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n)
{
    int v = -1, i;
    for (i = 0; i <n; i++){
        if (!selected[i]) {
            v = i;
            break;
        }
    }
    
    if(v == -1)
        return -1;
    
    for (i = 0; i < n; i++)
        if (!selected[i] && (distance[i] < distance[v]))
            v = i;
    return (v);
}

//
void prim(GraphType* g, int s)
{
    int i, u, v;

    for (u = 0; u<g->n; u++){
        distance[u] = INF;
        connectVertex[u] = s;       // 중요! 시작점 설정, connectVertex = 신장트리집합에 넣을 때 u와 연결된 점
    }
    
    distance[s] = 0;
    
    for (i = 0; i<g->n; i++) {
        u = get_min_vertex(g->n);       // 신장트리집합으로부터 비용이 가장 작은 노드
        selected[u] = TRUE;
        
        if (distance[u] == INF) return;
        
        printf("<%d %d> %d\n", connectVertex[u], u, distance[u]);
        printf("selected[] = \t");
        for(int j=0; j<g->n; j++){
            printf("%7d", selected[j]);
        }
        printf("\n");
        
        for (v = 0; v<g->n; v++)
            if (g->weight[u][v] != INF)
                if (!selected[v] && g->weight[u][v]< distance[v]){
                    distance[v] = g->weight[u][v];
                    connectVertex[v] = u;
                }
        
        printf("dist[] = \t\t");
        for(int j=0; j<g->n; j++){
            printf("%7d", distance[j]);
        }
        printf("\n\n");
        
    }
}

int main(void)
{
    GraphType g = { 6,
    {{ 0, 10, INF, 20, 70, INF },
    { 10,  0, 50, 30, 60, INF },
    { INF, 50, 0, INF, 40, 90 },
    { 20, 30, INF, 0, INF, 80 },
    { 70, 60, 40, INF, 0, INF },
    { INF, INF, 90, 80, INF, 0} }
    };
    
    prim(&g, 0);
    
    return 0;
}

 

 

 

 

 

 

 

3) 크루스칼과 프림의 알고리즘 복잡도

 - 간선이 아주 적은 그래프(sparse)

: 크루스칼의 알고리즘이 유리 - O(e * log(e)) -> 계속 정렬을 해야 하니까

- 간선이 아주 많은 그래프(dense)

: 프림 알고리즘이 유리 - O(n^2)