목록Kruskal Algorithm (1)

개발하는SM

[그래프] MST 구현 알고리즘 - Kruskal Algorithm

MST란? 2021.03.13 - [Algorithm - 이론] - [그래프] 최소 신장 트리(MST, Minimum Spanning Tree) Kruskal Algorithm Kruskal Algorithm 은 간단히 말해 아래와 같다. 1. 그래프의 간선들을 가중치의 오름차순으로 정렬 2. 정렬된 간선 리스트를 앞에서부터 순서대로 탐색하면서, Cycle 을 형성하지 않는 경우만 선택함 3. 2에서 선택된 간선을 MST 의 집합에 추가함. Cycle 판별하기 2번에서 선택된 간선이 Cycle 을 형성하는지 아닌지 판별하는 것이 핵심인데, Cycle 이 형성되는지 아닌지는 'Union-Find 알고리즘' 을 이용한다. Union-Find Disjoint Set(서로소 집합)을 표현하는 자료구조 서로 다른..
Algorithm - 이론 2021. 3. 13. 11:23
이전 Prev 1 Next 다음