Kruskal

[MST] Kruskal 알고리즘

• Algorithm
• 2021년 4월 12일

그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방법 (Greedy) 간선 선택 기반 알고리즘 간선 선택 단계에서 사이클을 포함하지 않고 최소 비용 간선을 선택 부분 트리집합을 병합하면서 하나의 트리로 확장 희소그래프에 적합 ( V > E ) 정렬 속도가 시간복잡도에 영향 2. Pesudo Code 3. 구현 Note...