반응형
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여부를 확인하지 않아도됨. 왜냐하면 트리내부의 정점을 택하는것이 아니라 외부의 정점을 택하기 때문임.
수행 성능
반응형
'자료구조' 카테고리의 다른 글
[파이썬 자료구조] 다익스트라 알고리즘(Dijkstra algorithm) (0) | 2020.06.21 |
---|---|
[파이썬 자료구조] Floyd-Warshall Algorithm (0) | 2020.06.21 |
[파이썬 자료구조] Partition or Disjoint Set (0) | 2020.06.20 |
[파이썬 자료구조] Kruskal 알고리즘 (0) | 2020.06.20 |
[파이썬 자료구조] 그래프(Graph) (0) | 2020.06.20 |