프림스 알고리즘

MST(Minimum Spanning Tree) 를 찾는 방법은 프림스 알고리즘(Prim's Algoryth)을 이용한다. Prim's Algorythm은 방향은 없지만 가중치는 있는 tree에서 모든 정점을 포함하는 Spanning Tree를 찾는다. 이는 모든 정점을 포함하는 Edge들은 가장 작은 total weight를 갖는 부분집합을 찾는 과정이다.

1. 수도코드

 ReachSet = {0};                    // You can use any node...
   UnReachSet = {1, 2, ..., N-1};
   SpanningTree = {};

   while ( UnReachSet ≠ empty )
   {
      Find edge e = (x, y) such that:
         1. x ∈ ReachSet
	 2. y ∈ UnReachSet
	 3. e has smallest cost

      SpanningTree = SpanningTree ∪ {e};

      ReachSet   = ReachSet ∪ {y};
      UnReachSet = UnReachSet - {y};
   }

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html