[파이썬 자료구조} Prim-Jarnik

Prim-Jarnik

1단계. 임의의 정점을 선택하고 트리에 넣음 (0을 선택했다고 가정) 그리고 인접 edge를 제외하고 모두 없다고 생각

2단계. 양쪽의 edge의 가중치를 확인한 후 정점1을 트리에 포함시킴 

3단계. 정점1에서 인접한 edge중에서 가장 작은 가중치의 edge를 고름. 그리고 정점6을 트리에 포함시킴

4단계. 원래 1->4의 가중치가 5였는데 1->6의 edge가 생겼으므로 1->4의 edge를 없애고 4->6을 연결함(가중치 1)

5단계. 정점 6에서 인접한 edge중에서 가장 작은 가중치를 택함

정점을 추가할 때마다 cycle여부를 확인하지 않아도됨. 왜냐하면 트리내부의 정점을 택하는것이 아니라 외부의 정점을 택하기 때문임.

수행 성능

[파이썬 자료구조] Partition or Disjoint Set

[파이썬 자료구조] Kruskal 알고리즘