[자료구조] 트리/Kruskal's Algorithm

* greedy algorithm을 따른다

* minimum cost spanning tree를 얻기 위한 과정

* 

 

과정

1. edge를 다 지운다

2. 제일 cost가 작은 edge를 하나 더해준다

3. 

 

 

Q) global optimum을 얻지 못할 수도 있지 않을까?
A) 항상 global optimum을 얻을 수 있다는 것이 증명되었다. 교재에 proof 있음