Kruskal

[MST] Kruskal 알고리즘

• Algorithm
• 2021년 4월 12일

그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방...