[algorithms] ch5. Greedy algorithms (MST: prim algorithm)

(23.03.24)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

 

정리한 내용

5.1 Minimum spanning trees

-> prim's algorithm

 

---

 

Prim's algorithm

- dijkstra와 비슷한 방법으로 priority queue를 사용한다.

- priority queue에다가 weight를 저장하여 가장 작은 weight을 가진 노드를 꺼내는 방식으로 진행한다. 꺼낸 노드에 인접한 노드의 cost와 edge의 weight을 비교하여 더 적은 값으로 업데이트한다.

 

 

 

 

prim's algorithm 예시