[알고리즘] 탐욕적 알고리즘 Part 2 - 최소신장트리 Phase 2 - Prim의 알고리즘 작성

* Prim의 알고리즘 작성
 - 용어 : 처음에 선택된 정점 V0와 합쳐진 정점들은 "적색"정점들이라고 부른다.
            그 외 다른 정점들은 "청색" 정점들이라고 부른다. 
 - 알고리즘 : 각 단계에서 한 적색정점과 한 청색 정점을 연결하는 가장 가벼운 연결선을 선택한다.
                  그리고 청색 정점을 적색으로 바꾸고, 그 연결선을 트리에 추가한다.
 - 그래프의 표현 : 그래프는 비용행렬 W에 의해 나타내진다.
 - 슈도 코드
  R: 적색 정점들의 집합
  B: 청색 정점들의 집합
  V: 주어진 그래프 내의 모든 정점들의 집합
  T: 트리내에 포함되는 연결선들의 집합
  ⓐ 임의의 노드 V0를 선택한다.
  ⓑ T = 공집합
  ⓒ R = {V0}  B = V - {V0}
  ⓓ for ( i = 1 ; i <= n-1 ; i++ )
   ⓓ-1. W[r][b]를 최소화 하기 위한 r ∈ R과 b ∈ B를 선택한다.
   ⓓ-2. T = T ∪ { (r,b) }
   ⓓ-3. B = B - {b}
   ⓓ-4. R = R ∪ {b}
 - 분석
  W에 대한 참조 횟수로 그 효율을 알수 있다.
  

  > 위에서 중복된 계산 과정이 많이 존재한다는 것을 알수 있다. 거의 같은 집합상에서 최소 연결선이 매
     반복시 계산 된다.
  > 이를 최소화하기 위해 2가지 관점으로 관찰을 한다.
   ⓐ 적색 정점의 관점 : 한 정점이 적색이 될 때 {b,c,d,e}중 하나만 최소값 고려 대상에서 빠진다.
   ⓑ 청색 정점의 관점 : 한 정점 q가 적색이 될 때 W[a,q]가 a에 대한 최소값 고려 대상에 포함된다.
   ※ 청색 관점에서 신장트리를 추가하는 것이 더 쉽게 추가가 가능함을 나타낸다.
       

 - 구현
  > 변수
   ⓐ near[b] : 청색 정점 b에서 가장 가까운 적색 정점
   ⓑ isblue[v] : 저점 v가 청색이면 true
  > 코드
   // 초기화 부분
   isblue[1] = false;   // 임의의 노드로 첫번째 노드를 선택한다.
   for ( i = 2 ; i <= n ; i++ ){
     isblue[i] = true;
     near[i] = 1;
   } 
   for ( i = 1; i <= n-1 ; i++ ){
     minval = ∞;
     for ( b = 1 ; b <= n ;  b++ ){

       if ( isblue[b] ) 
         if ( w[b,near[b]] < minval ){   // 최소거리 가중치 찾기
           minval = w[b,near[b]];
           newred = b;
         }
     } 
     isblue[newred] = false;
     "out put edge (newred,near[newred])"
      // near[b]를 갱신한다.
      for ( b = 1; b<= n ; b++ ){

        if ( isblue[b] )
          if ( w[b,newred]<w[b,near[b]])
            near[b] = newred;
      }
    }