최소신장트리 알고리즘

개념
최소신장트리 (Minimum Spanning Tree) 알고리즘 (프림 알고리즘, 크루스칼 알고리즘) 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프

I. 신장트리 (Spanning Tree)의 개요

   가.  신장 트리의 정의

- 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프

나.  최소신장트리의 정의

- 정점 간 가중치(cost)의 합이 최소인 신장 트리

 

Ⅱ. 최소신장트리 알고리즘

   가.  Prim의 알고리즘

* 시작점 기반 최소 가중치

* 정점마다 edge 검사

* 우선순위 큐 기반 구현

  1. 임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입
  2. 선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사
  3. 최소 가중치를 가지는 edge를 선택
  4. 해당 edge로 두 정점을 연결했을 때, cycle이 발생하면 버리고, 그렇지 않으면 신장트리에 삽입
  5. 선택된 edge는 edge리스트에서 제거
  6. edge리스트에 더 이상의 edge가 없을 때까지 2~5번 반복

void prim(int n, const number W[][], set_of_edges& F) {

 index i, vnear;

 number min;

 edge e;

 index nearest[2..n];

 number distance[2..n];

 

 F = empty_set;

 for(i=2;i <= n;i++) {   

   nearest[i] = 1;        

   distance[i] = W[1][i];

 }

 repeat(n-1 times) {

  min = ;

  for(i=2; i <= n; i++) {

   if 0 <= distance[i] < min) {

     min = distance[i];

     vnear = i;

 }}

 e = vnear와 nearest[vnear]를 잇는 이음선;

 e를 F에 추가;

 distance[vnear] = -1;

 for(i=2; i <= n; i++)

  if (W[i][vnear] < distance[i]) {

   distance[i] = W[i][vnear];

   nearest[i] = vnear;

}}}

 

 

가.  Kruskal의 알고리즘

* 가중치의 오름차순 정렬 수행

* 최소 가중치 edge 선택

* 분리집합 기반 구현

  1. 그래프 내의 모든 edge을 가중치의 오름차순으로 정렬
  2. 현재 edge들 중에서 가중치가 가장 적은 edge를 선택
  3. 해당 edge로 두 정점을 연결했을때, cycle이 발생하면 버리고, 그렇지않으면 신장트리에 삽입
  4. 선택된 edge는 edge리스트에서 제거
  5. edge리스트에 더 이상의 edge가 없을 때까지 2~3 반복

void kruskal( int n, int m, set_of_edges E, set_of_edges& F) {

 index i, j;

 set_pointer p, q;

 edge e;

 E에 속한 m개의 이음선을 가중치의 비내림차순으로 정렬;

 F = emptyset;

 initial(n);

 while (F에 속한 이음선의 개수가 n-1보다 작다) {

  e = 아직 점검하지 않은 최소의 가중치를 가진 이음선;

  i, j = e를 이루는 양쪽 정점의 인덱스;

  p = find(i);

  q = find(j);

  if (!equal(p,q)) {

    merge(p,q);

    e를 F에 추가;

}}}

 

 

댓글