2016년 2월 28일 일요일

프림(Prim) MST(Minimum Spanning Tree 최소 신장 트리)


프림 알고리즘(Prim's algorithm)

가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용을 찾는 알고리즘이다. (greedy algorithm 임)

개요

프림 알고리즘은 아래의 순서대로 작동한다:

  1. 그래프에서 임의의 하나의 정점을 선택한다.
  2. 선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.
  3. 1.2 과정을 반복 하여 모든 정점이 선택될까지 한다.


알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.


동작 예제


어떤 점에서 시작하던 관계는 없습니다.
좌측 그래프에서는 임의의 시작점 D를 선택합니다.



D지점에 연결된 모든 정점에 대해 거리가 최소가 되는 정점을 선택합니다.

D

여기에서는 A지점이 됩니다. D-A지점은 서로 연결을 시키게 됩니다.DA

A,D 정점 각각 모든 정점들에 대해 최소 비용을 계산합니다. DAF

D-F:6 비용이 최소가 됩니다. F정점을 추가합니다.DAF

지금까지 연결된 정점(A,D,F) 모두에 대하여 연결된 남은 정점들을 모두 검색해서 비용이 최소가 되는 정점을 구합니다.DAF

A-B가 7로서 최소값으로 추가되었습니다.DAFB


지금까지 연결된 B가 연결되면서 D-B상의 연결 검토는 필요가 없습니다.(회색) 왜냐하면 tree를 확장해나가는 조건이 연결이 안된 정점에 대해서 진행하기 때문입니다.
여기에서 최소값 검토 지점은 분홍색을 대상으로 진행합니다.		DAFB


B-E가 7로서 최소값으로 E정점이 추가되었습니다.DAFBE


E정점이 추가됨으로서 D-E,F-E는 검토대상에서 사라졌으며 E-C,G-E 가 검토 대상에 추가되었습니다.
최소값은 E-C:5가 되면서 C지점이 추가가 될 것입니다.		DAFBE


A-B가 7로서 최소값으로 추가되었습니다.DAFBEC


E-G 는 최소값 9로 추가 되었습니다.DAFBECG

Prim’s Algorithm pseudocode

Priority Queue Implementation

Q ← PQinit()
for each vertex v in graph G
    key(v) ← ∞
    pred(v) ← nil
    PQinsert(v, Q)

key(s) ← 0
while (!PQisempty(Q))
    v = PQdelmin(Q)
    for each edge v-w s.t. w is in Q
        if key(w) > c(v,w)
            PQdeckey(w, c(v,w), Q)
            pred(w) ← v

설명
v : vertex 정점
key : 가중치 또는 비용
PQ : 우선순위 Queue
edge : 간선,정점과 다른 정점 사이의 선

소스코드



C, pasted just now: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <stdio.h>

#define MAX_NODES 7

#define MAX_INT 99999
#define NOTDEF  -1
#define OUTOFQ  -1

// [in][out]
int graph[MAX_NODES][MAX_NODES]={
//  A, B, C, D, E, F, G out
  { 0, 7, 0, 5, 0, 0, 0},// A in
  { 7, 0, 8, 9, 7, 0, 0},// B in
  { 0, 8, 0, 0, 5, 0, 0},// C in
  { 5, 9, 0, 0,15, 6, 0},// D in
  { 0, 7, 5,15, 0, 8, 9},// E in
  { 0, 0, 0, 6, 8, 0,11},// F in
  { 0, 0, 0, 0, 9,11, 0},// G in
};

int key[MAX_NODES];  // The cost
int pred[MAX_NODES]; // The Infomation of parents
int Q[MAX_NODES];
int Qcount;

void PQinit()
{
    Qcount = 0;
}

int PQinsert(int a)
{
    Q[a] = 0;
    Qcount++;
}

int PQdelmin()
{
    int i;
    int min = MAX_INT;
    int saveindex = OUTOFQ;
    for(i=0;i<MAX_NODES;i++){
        if(Q[i]==OUTOFQ) continue;
        if(key[i] < min ){
            saveindex = i;
            min = key[i];
        }
    }
    if( saveindex == OUTOFQ ) return OUTOFQ;
    Q[saveindex]=OUTOFQ;
    Qcount--;
    return saveindex;
}

int PQisempty()
{
    if(Qcount==0) return 1;
    return 0;
}

int PQdeckey(int w, int newkey)
{
    key[w]=newkey;
}

void Prim(int start)
{
    int i,v,w;
    PQinit();
    for(i=0;i<MAX_NODES;i++){
        key[i]=MAX_INT;
        pred[i]=NOTDEF;
        PQinsert(i);
    }

    key[start]=0;
    for(;!PQisempty();){
        v = PQdelmin();
        printf("%d %c\n",v,v+'A');
        for(w=0;w<MAX_NODES;w++){
            if((graph[v][w]!=0) && (key[w]>graph[v][w])){
                PQdeckey(w, graph[v][w]);
                pred[w]=v;
            }
        }
    }
}

main()
{
    Prim(3);// D is 3
    return 0;
}


Output:
1
2
3
4
5
6
7

3 D
0 A
5 F
1 B
4 E
2 C
6 G



우선 순위 Q를 구현하지는 않았고 배열에 들어있는 값을 순차 비교를 하는 방식으로 구현하였습니다.

참고
https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
http://www.cs.princeton.edu/courses/archive/spr02/cs226/lectures/mst-4up.pdf
작성자: 시간:
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)