[Greedy] Kruskal Algorithm

크루스칼 알고리즘

 

최소 비용 신장트리를 찾는알고리즘 중 하나로

 

{ 노드 연결들중 최소비용 연결을 선택 } 을 반복합니다.

연결시 사이클이 이루어지면 선택하지 않습니다.

 

ex)

5, 5, 7, 8, 9, 13, 15, 20

-> 5 (A-D) 연결

-> 5 (C-E) 연결

-> 7 (C-D) 연결

-> 8 (B-F) 연결

-> 9 (D-E) 사이클로 연결X

-> 13 (A-B) 연결