Prim's Algorithm

• Prim's Algorithm (by Robert C. Prim)
1. 그래프에서 임의의 vertex를 선택한다.
2. 선택한 vertex를 tree에 넣는다. 이것은 MST의 root가 된다.
3. 선택된 vertex와 연결된 edge중에서 가장 적은 weight를 선택한다.
4. 3에서 연결된 vertex를 tree에 넣고 root과 연결한다.
5. 두개의 vertex에 연결된 edge중에서 가장 작은 weight를 선택하고 선택된 vertex를 다시 MST에 연결한다.
6. 3,4,5를 계속 반복하면 가장 작은 weight 값을 사용한 MST가 완성된다.
• 주의할 점 : 위에서 두개의 edge가 한 vertex를 가리키는 경우가 있다. 두 edge중에서 적은 값을 놔두고 큰 edge는 없는 셈친다. (why ? 세개의 vertex간에서 cycle을 형성하기 때문이다. 이것은 tree의 정의에 어긋난다. 또한 최소한을 선택하는 이유는 minimum weight로 tree를 만들기 때문에 필요없다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Graph에서 아무 vertex 하나 고른다   D[시작 vertex] = 0   for(vertex가 시작 vertex가 아니라면){     D[u] = 무한대 }   각 vertex에 연결되는 edge의 weight를 정렬하기 위한 priority queue Q를 초기화한다   while(Q에 edge가 존재한다면){     Q에서 가장 작은 weight인 edge를 뽑고 기존의 vertex와 연결한다.     for(기존의 vertex에 인접한 vertex가 있다면){         if(원래 vertex와 거리 > 새로운 edge에 연결한 거리){             새로운 edge에 연결한 거리를 D[기존 vertex]에 업데이트함         }     } }