목차
개념
크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다.
그래프에는 정점과 간선이 있는데, 간선에 가중치가 포함되어 있습니다.
그래프 내의 모든 정점을 포함하고 사이클이 없는 연결선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용합니다.
즉, 최소 신장 트리를 구하기 위한 알고리즘 입니다.
신장 트리와 최소 신장 트리
신장 트리(Spannging tree) 다음과 같이 정의합니다.
그래프에서
1) 모든 정점을 포함하고
2) 정점 간 서로 연결되어 있으며 싸이클이 존재하지 않는 그래프
(싸이클이 존재하는 않는 것은 tree 기본 조건)
예를 들어 아래와 같은 그래프가 있다고 가정해 보겠습니다.
여기서 나올 수 있는 신장 트리들은 여러 가지인데, 아래와 같은 예시가 있을 수 있습니다.
두 신장 트리들 모두 모든 정점이 포함되어 있으며, 모든 노드는 적어도 하나의 간선으로 연결되어 있습니다.
또한, 연결 관계에서 사이클을 형성하지 않습니다.
신장 트리는 정점의 갯수가 n일 때, 간선이 n-1개가 됩니다.
간선 위의 적힌 숫자는 그 간선의 가중치를 의미합니다.
왼쪽 그래프의 가중치는 1 + 6 + 4 + 5 = 16
오른쪽 그래프의 가중치는 1 + 2 + 6 + 4 = 13
만약 신장 트리가 두 개 밖에 없다면 가중치의 합이 최소가 되는 최소 신장 트리는 가중치가 13으로 더 작은 오른쪽 그래프가 됩니다.
이렇든 신장 트리들 중 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 합니다.
최소 신장 트리(Minimum Spanning Tree, MST)
가중치의 합이 최소가 되는 신장 트리
위의 그래프에서 최소 신장 트리는 다음과 같습니다.
크루스칼 알고리즘은 바로 이 최소 신장 트리를 구하기 위한 알고리즘 입니다.
크루스칼 알고리즘
최소 신장 트리를 구하기 위한 알고리즘
크루스칼 알고리즘 구현 과정
크루스칼 알고리즘은 그리디 알고리즘의 일종입니다.
크루스칼 알고리즘을 구현하기 위해서 다음을 사용했습니다.
PriorityQueue
간선의 가중치가 최소인 것을 구하기 위해 사용됩니다.
Union - Find 알고리즘
정점들 사이 연결 여부를 확인하기 위해 사용됩니다.
1. 그래프 간선의 가중치를 오름차순으로 정렬합니다. (PriorityQueue)
2. 가중치가 가장 적은 a-b를 선택합니다. (PriorityQueue - poll)
3. 그 다음으로 가중치가 적은 a-d를 선택합니다. (PriorityQueue - poll)
4. 그 다음으로 가중치가 적은 b-d를 선택하면 a-b-d 사이클이 형성되므로 선택하지 않습니다.
(유니온 파인드 사용, 파인드로 두 노드의 부모를 확인해서 같으면 연결되어 있으므로 continue)
5. 그 다음 가중치가 적은 b-c를 선택합니다. 선택된 간선의 갯수가 정점의 갯수 -1이 되면 종료합니다.
(혹은 유니온 파인드로 모든 정점의 부모가 같으면 이어저 있다는 뜻으로 종료합니다.)
참조
https://chanhuiseok.github.io/posts/algo-33/
알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)
##
chanhuiseok.github.io
