1. 크루스칼 알고리즘 (Kruskal Algorithm)
: 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘.
최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘.
예) 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘
* 용어
노드 = 정점 = 도시 : 그래프에서 동그라미
간선 = 거리 = 비용 : 그래프에서 선
간선을 거리가 짧은 순서대로 그래프에 포함시킨다
→ 일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에
모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시킨다
* 최소 비용 신장트리
1. 정렬된 순서에 맞게 그래프에 포함시킨다
2. 포함시키기 전에는 사이클 테이블을 확인한다
3. 사이클을 형성하는 경우 간선을 포함하지 않는다
(사이클 : 그래프가 서로 연결되어 사이클을 형성하는 것)
2. 크루스칼 알고리즘의 시간 복잡도 = 정렬 알고리즘의 시간 복잡도
크루스칼 알고리즘 = 정렬 알고리즘 + Union-Find 알고리즘
'🤖 Data Study > Algorithm' 카테고리의 다른 글
| [알고리즘] 15. 다이나믹 프로그래밍(Dynamic Programming) (0) | 2020.05.01 |
|---|---|
| [알고리즘] 14. 이진 트리의 구현과 순회(Traversal) 방식 (0) | 2020.05.01 |
| [알고리즘] 12. Union-Find(합집합 찾기) (0) | 2020.04.30 |
| [알고리즘] 11. 깊이 우선 탐색 (DFS) (0) | 2020.04.30 |
| [알고리즘] 10. 너비 우선 탐색 (BFS) (0) | 2020.04.30 |