Greedy 알고리즘 - Prim 알고리즘

Greedy 알고리즘  문제 중 하나인 최소 신장 트리 구하는 문제의 두 번째 풀이

 

-Prim algorithm

랜덤으로 노드를 하나 고르고 고른 노드와 연결되는 edge 중 weight가 적은 것을 고르고, 이어진 노드에서 이 과정을 이어가기를 반복한다

 

-주의

점을 하나 선택할때마다 근처 점들의 weight를 가져오는 것은 비효율적이다.

그래서 배열D에 각 노드에서 다른 한 노드까지 걸리는 wieght의 최소값을 저장해놓는다.

D의 값들 중 최솟값을 T로 업데이트한다.

T를 갱신할때마다 D를 업데이트한다.

이 과정이 추가됨에 따라 Greedy Search+Dynamic program 방법이 섞인 알고리즘이 된다.

 

-Prim MST의 Pseudo Code

입력 : 가중치 그래프 G=(V,E), |V|=n,|E|=m

출력 : 최소 신장 트리 T

배열 D는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 원소이다.

그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p]=0으로 놓는다.
for(시작점 p가 아닌 각 점 v에 대하여){//D 초기화
  if(선분 (p,v)가 그래프에 있으면)
    D[v]=선분 (p,v)의 가중치
  else
    D[v]=9999}//D초기화 끝, 이를 토대로 T 작성 시작
 T={p}//초기에 트리 T는 점 p만을 가진다.
 while(T에 있는 점의 수<n){//점 개수가 다 채워질때까지 T업데이트
  T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 v와 연결된 선분 (U,v)를 T에 추가한다. 단 U는 T에 속한 점이고, 점 v도 T에 추가된다. 점과 적절한 선분 추가!
    for(T에 속하지 않은 각 점 w에 대해서){//점이 하나 새로 추가되었으므로 다른 결과가 나올 수 잇다.
      if(선분 v,w)의 가중치<D[w])//기존 등록된 가중치보다 작은 가중치이면 
        D[w]=선분(v,w)의 가중치} }//D에 업데이트
return T

프림 알고리즘은 T밖에 있는 점을 1개씩 추가하고, 동일한 vertex는 다신 선택되지 않으므로 Tree 형태임이 증명된다. 

 

 

 

-Prim MST의 time Complexity

D의 초기화 과정은 일정하다.O(1)

T에 노드가 다 채워질때까지 최소값인 점 찾아 넣기를 반복->n번*(n-1)번 O(n^2)

기존 등록된 가중치보다 작은지 비교 n-2번 O(n)

 

최종T= O(n^2)+O(1)+O(n)=O(n^2)

 

성능이 별로지만 쉽고 많이 쓰이는 알고리즘이다.

 

-소스 코드(C)

방문한 노드와 그렇지 않은 노드를 구분하여 최소 거리를 비교해야한다.

노드를 먼저 찾아낸 후 dist 배열을 갱신해준다. dist[v]=weight[u][v]

업데이트 되는 부분이 어디인지 잘 봐두자

#include <stdio.h>
#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 6  // 노드 개수
#define INF 1000 // INFINITE

int weight[MAX_VERTICES][MAX_VERTICES] = {// 트리의 거리와 모양을 배열로 표현, INF는 바로갈 수 있는 경로가 없음을 뜻한다.
  {0,3,INF,2,4,INF},
  {29,0,1,4,INF,2},
  {INF,1,0,INF,INF,INF},
  {2,4,INF,0,5,7},
  {4,INF,INF,5,0,9},
  {4,INF,INF,5,9,0},
};

int selected[MAX_VERTICES]; // 노드의 선택 여부를 담는다.
int dist[MAX_VERTICES]; // 최소 거리를 저장한다. 추가되는 노드가 있을때마다 업데이트된다.

int get_min_vertex(int n)// 최소 dist 값을 갖는 노드를 반환한다.
{
    int v, i; // 노드의 정보를 저장할 변수 v

    for (i = 0; i < n; i++)//선택되지 않은 노드를 골라서 차례대로 비교하기 위한 과정
    {
        if (selected[i] == FALSE) {
            v = i;  // 아직 선택되지 않은 노드의 번호를 v에 저장한다. 0~n-1
            break;
        }
    }

    for (i = 0; i < n; i++)
    {
        //(선택되지 않은)모든 노드들에 대하여 최소 거리를 가지는지 확인한다. 
        if (selected[i] == FALSE && (dist[i] < dist[v]))//첫 번째 노드가 추가된 후라면 dist가 업데이트되어있음. 첫번째 노드 선택 후에서야 다음 노드로 갈 수 있는 선택지가 늘어남
            v = i;  //최소 거리를 가진 노드가 있으면 저장한다.
    }

    return(v);//최소 거리 노드 반환
}

void prim(int s, int n)
{
    int i, u, v;

    for (u = 0; u < n; u++)  // dist와 selected 초기화. 처음엔 모든 값이 inf이고, false이다.
    {
        dist[u] = INF;
        selected[u] = FALSE;
    }

    dist[s] = 0;  //노드 자신과의 거리는 0

    for (i = 0; i < n; i++)
    {
        
        u = get_min_vertex(n);
        selected[u] = TRUE; // 최소 거리를 갖는 노드 u를 찾았으므로 선택되었다 표시한다.

        // 만약 경로가 없다면 종료한다.
        if (dist[u] == INF) return;

        printf("%c ", u+97); // 선택한 노드를 출력한다.

        for (v = 0; v < n; v++)  // 새롭게 추가된 노드에 따라 dist를 업데이트해준다.
        {
            // 선택된 노드 u와 연결된 노드간의 거리를 비교한다.
            if (weight[u][v] != INF)//노드 u와의 거리가 무한대가 아님->연결되어있음
            {
                // 아직 선택되지 않았고, v에서 u까지의 거리가 기존 최소 거리보다 가까우면
                if (selected[v] == FALSE && weight[u][v] < dist[v])
                    dist[v] = weight[u][v]; // dist[v]의 값을 갱신해준다.

            }
        }
        printf(" dist:");
        for (int i = 0; i < MAX_VERTICES; i++)//업데이트될 때마다 dist를 출력한다.
        {
            printf(" %d",dist[i]);
        }
        printf("\n");
    }
}

void main()
{
    prim(2, MAX_VERTICES);  //임의의 점 C에서 출발하여 얻을 수 있는 MST

전체 흐름 [1]~[7]