MST - Prim Algorithm

minimum spanning tree(MST)는 undirected graph - G(V, E) - 에서 모든  점을 연결하는 그래프 중에서 weight의 합이 최소인 서브 그래프를 말한다.

MST를 구하는 대표적 알고리즘은 Kruskal 과 Prim 알고리즘이 있다.

먼저 Prim algorithm은 graph를 2개의 set 으로 나누고 두 셋을 연결하는 에지는 최소여야 MST를 만들 수 있다는 아이디어로 부터 만들어진 것이다.

설명은 여기가 너무나 잘 되어 있고..
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

나의 구현은 여기
https://github.com/nberserk/codejam/blob/master/java/src/codejam/lib/PrimMST.java


Kruskal 다음에 하기로..