티스토리 뷰
* greedy algorithm을 따른다
* minimum cost spanning tree를 얻기 위한 과정
*
과정
1. edge를 다 지운다
2. 제일 cost가 작은 edge를 하나 더해준다
3.
Q) global optimum을 얻지 못할 수도 있지 않을까?
A) 항상 global optimum을 얻을 수 있다는 것이 증명되었다. 교재에 proof 있음
'Algorithm > 이론' 카테고리의 다른 글
| [자료구조] 트리/Sollin's Algorithm (0) | 2019.06.03 |
|---|---|
| [자료구조] 트리/Prim's Algorithm (0) | 2019.06.03 |
| [자료구조] binary search tree(이진 탐색 트리) (0) | 2019.05.31 |
| [자료구조] heap/최대 heap에서 delete (0) | 2019.05.31 |
| [자료구조] heap/ 최대 heap에서 insert (0) | 2019.05.31 |