PSU/CSE 565 - Algorithm

[CSE 565] - 2019-10-07.pdf 일단 오늘꺼 정리

MJSon 2019. 10. 9. 12:24

 

다시 정리 




  1. Crossing Edge 는 항상 MST 에 속한다.

  • 증명 - 다른 crossing edge를 할 경우 결국 crossing edge 기존꺼가 더 작다고 해서 접근한다.

 

  1. Prim은 Priority Queue 를 사용해서 min crossing edge를 찾는다.

  2. Kruskal은 Cycle






https://progresivojs.tistory.com/7

 

 

 

https://progresivojs.tistory.com/3

 



저작자표시 (새창열림)