[ 알고리즘 개념 ] 크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)

 

1. 개념

크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이며, 그리디 알고리즘에 해당한다.

신장트리 및 최소 신장 트리에 대한 개념은 아래 글에 정리해두었다.

https://codingexplore.tistory.com/61?category=886802 

[ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree)

2. 동작 과정

1) 간선을 가중치(Cost) 기준 오름차순으로 정렬 (가중치가 낮은 간선부터 처리)

2) 간선을 차례대로 확인하며 해당 간선이 사이클을 형성하는지 확인

- 사이클이 발생하지 않으면 최소 신장 트리에 포함 O

- 사이클이 발생하는 경우 최소 신장 트리에 포함 X

3) 모든 간선에 대해 2번 과정 반복

3. 동작 예

#E0 : 초기 그래프

그래프 예

 

#E1 : 가장 비용이 낮은 간선 선택 (1)

#E2 : 두번째 간선 선택 (2)

#E3 : 세번째 간선 선택 (3)

#E4 : 네번째 간선 선택 (5)

( 가장 가중치가 낮은 간선은 4이지만 해당 노드는 2->3->4 의 사이클을 형성하므로 선택하지 않는다 )

관련글

다음은 또다른 최소 신장 트리(MST) 알고리즘인 프림 알고리즘과 관련한 글이다.

프림 알고리즘

https://codingexplore.tistory.com/63

[ 알고리즘 개념 ] 프림 알고리즘 (Prim Algorithm)

---

참고자료

https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/

Minimum Spanning Tree Tutorials & Notes | Algorithms | HackerEarth