MJay

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

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

 



저작자표시

'PSU > CSE 565 - Algorithm' 카테고리의 다른 글

[CSE 565] - 2019-10-02.pdf leftist tree  (0) 2019.10.10
[CSE 565] - 2019-10-02.pdf Binary Heap  (0) 2019.10.10
[CSE 565] - 2019-10-07.pdf  (0) 2019.10.09
[CSE 565] - 2019-10-07.pdf  (0) 2019.10.09
[CSE 565] 시험 공부  (0) 2019.10.09
'PSU/CSE 565 - Algorithm' Related Articles more