최소신장트리
-
[최소신장트리] 크루스칼(Kruskal) 알고리즘Problem-Solving/Algorithm 2023. 10. 29. 03:28
🍀 목차 크루스칼 알고리즘 같은 목적을 가진 알고리즘 기본 이해 구현(JavaScript) 시간 복잡도 크루스칼 알고리즘 최소 신장 트리 (MST : Minimum Spanning Tree) 알고리즘 중 하나. MST(Minimum Spanning Tree) 모든 정점을 잇는 최소 비용 Spanning Tree를 찾는 것이 목적. 무향 가중치 그래프에서 적용한다. 사이클이 포함되어서는 안 된다(트리는 사이클 없이 모든 정점이 연결되어 있는 그래프 자료구조). 기본적으로 그리디 알고리즘을 바탕으로 하고 있다. 항상 최소 비용을 찾고 탐욕적으로 선택한다. 간선 선택 기반 알고리즘이다. 간선을 가중치(비용) 오름차순으로 정렬하고 Union-Find 알고리즘을 적용하며 사이클 형성 유무를 판단하며 선택해 간다...
