[알고리즘] 프림 알고리즘, Prim's Algorithm | 설계 및 분석

  프림 알고리즘의 locally optimal의 기준은 이미 방문한 정점들의 집합 Y에서부터 방문한 적이 없는 한 정점까지의 거리이다. 즉, 방문한 적이 없는 정점들 중 출발점과의 거리가 가장 가까운 정점부터 선택한다는 것이다. 이 과정을 간단한 수도코드와 그림으로 나타내면 다음과 같다.

 

수도코드(high level)

 

  F := ∅;  //edge의 집합
  Y := {v1}; //vertex의 집합, 출발점을 포함한 상태로 시작
  
  while(the instance is not solved) {
    select a vertes in V-Y that is nearest to Y; //selection procedure, feasibility check
    
    add the vertex to Y;
    add the edge to F;
    
    if(Y==V) //solution check
      the instance is solved;
}
  

 

문제 해결 과정

 

문제 해결 과정 예시

  위 그림을 보면 알 수 있듯이 그래프는 크게 방문한 정점들의 묶음 Y(    ), 방문하지 않은 정점들의 묶음 V-Y(    ) 이렇게 두 묶음으로 나뉜다. 방문하지 않은 정점들 중 방문한 정점들의 묶음과 가장 가까운 정점을 선택하여 이를 방문한 정점들의 묶음에 포함한다. 쉽게 말하면 분홍 묶음과 파랑 묶음을 연결하는 선 중 가장 값이 작은 선을 선택하는 것이다.

  이 과정을 이해했다면 아래의 더 자세한 수도코드를 이해할 수 있을 것이다.

 

수도코드(low level)

  prim 알고리즘에서는 nearest 배열과 distance 배열을 추가적으로 사용한다.

• nearest[i] : Y에 속한 정점들 중에서 v_i와 가장 가까운 정점의 인덱스
• distance[i] : v_i와 nearest[i]를 잇는 이음선의 가중치. 즉, 그 가까운 정점과의 거리

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]; //가장 가까운 정점(nearest)과 그 정점과의 거리(distance)
  
  F = ∅;
  for(i=2; i<=n; i++) { //초기화
    nearest[i] = 1;
    distance[i] = W[1][i];
  }
  
  repeat(n-1 times) { //cycle이 없는 트리의 edge는 n-1개이므로
    min = "infinite";
    for(i=2; i<=n; i++) //가장 가까운 정점을 찾는다
      if(0 <= distance[i] <= min) { //basic operation
        min = distance[i];
        vnear = i;
      }
    e = edge connecting vertices indexed by vnear and nearest[vnear];
    add e to F;
    distance[vnear] = -1;
    for(i=2; i<=n; i++) //새로운 정점이 Y에 추가되었으므로 V-Y에 있는 정점들과 Y의 거리를 각각 갱신해준다.
    if(W[i][vnear] < distance[i]) //basic operation
    {
      distance[i] = W[i][vnear];
      nearest[i] = vnear;
    }
  }
}

 

 

알고리즘 분석

basic operation : distance 값을 비교하는 부분(두 개의 for문 내부의 명령문)

prim 알고리즘은 그래프의 내용에 상관없이 연산횟수가 동일한 every-case이다.

각 for문은 n-1번 반복되므로 2x(n-1)이고 이는 n-1번 반복하는 reapeat에 싸여있으므로 2x(n-1)x(n-1)

∴ T(n) = 2(n-1)(n-1) ∈ Θ(n²)

 

최적 여부 검증

  greedy approach는 다른 접근 방식과는 달리 최적 여부를 증명해야한다. 최적이라는 보장이 없기 때문이다.

현재 prim algorithm은 최적의 해답을 주는 것으로 증명된 상태이다.