Prim 최소 신장 트리 출력 - Prim choeso sinjang teuli chullyeog

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

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

목차 Show

프림 알고리즘(Prim's algorithm)
동작 예제
Prim’s Algorithm pseudocode
소스코드

개요

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

그래프에서 임의의 하나의 정점을 선택한다.
선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.
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:

#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:

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