728x90
크루스칼 알고리즘(Kruskal MST)
탐욕적인(Greedy) 방법을 이용하여 그래프의 모든 정점을 최소비용으로 연결하는 최적 해답을 구하는 것
동작과정
1. 간선데이터를 비용에따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 싸이클을 발생 시키는지 확인
2-1.사이클이 발생하지 않은 경우 최소 신장 트리에 포함
2-2.사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
3. 모든 간선에 대하여 2번을 반복
시간복잡도
간선의 갯수가 E개일때 : O(ElogE)
시간이 가장 오래걸리는 부분이 간선을 정렬하는 작업
정렬의 시간복잡도 = O(ElogE)
'자료구조' 카테고리의 다른 글
| 탐색 (Search), 순차 탐색, 이진 탐색, 색인 순차 탐색, 보간 탐색 (0) | 2021.05.10 |
|---|---|
| 프림 알고리즘 (Prim) (0) | 2021.05.10 |
| 신장트리 (Spanning Tree), 최소 신장트리 (Minimum Spanning Tree) (0) | 2021.05.08 |
| DFS(깊이 우선 탐색), BFS(너비 우선 탐색) (0) | 2021.05.08 |
| 위상 정렬 (Topology Sort) (0) | 2021.05.07 |