크루스칼 (Kruskal) 알고리즘, 최소 신장 트리 (MST)

Kruskal Algorithm

• 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용 (간선에 가중치가 포함)
• 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용
• 최소 신장 트리를 구하기 위한 알고리즘

신장 트리 (Spanning tree)

• 그래프에서 모든 정점을 포함하고 정점 간 서로 연결이 되며 사이클 (cycle)이 존재하지 않는 그래프
• 연결 관계에서 사이클 형성 안함
• 모든 정점이 포함되어 있으면서 모든 노드는 적어도 하나의 간선으로 연결되어 있음
• 신장 트리는 정점이 n개일 때, 간선이 n-1개
• 신장 트리들 중 가중치의 합이 최소가 되는 신장트리를 최소 신장 트리 (Minimum Spanning Tree, MST)라고 함
• 이 최소 신장 트리를 구하기 위한 알고리즘이 크루스칼 알고리즘

MST를 구하는 문제 예시

• 여러 개의 네트워크 지점들이 있는데, 모든 지점들을 유선으로 연결하되 연결선의 총 길이가 최소가 되어야 하는 문제
• 도시를 모두 연결하되, 연결하는 도로의 길이 합이 최소가 되어야 하는 문제

Kruskal Algorithm 과정

• 그리디 알고리즘의 일종
• 그래프 간선들을 가중치의 오름차순으로 정렬한 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선 선택

1. 그래프 간선을 가중치 오름차순 정렬
2. 가중치(비용)가 적은 간선부터 그래프에 포함
3. 포함시키기 전에는 사이클 형성 확인
4. 사이클을 형성하는 경우 간선 포함시키지 않음
5. 선택된 간선의 수가 정점의 수 - 1 만큼 되면 종료

사이클 발생 여부

• Union-Find 알고리즘 사용
  • Disjoint Set (서로소 집합)을 표현하는 자료구조
  • 서로 다른 두 집합을 병합하는 union 연산, 집합 원소가 어떤 집합에 속해있는지 찾는 find 연산
• 각 노드의 부모가 동일한지 아닌지 확인하는 것으로 사이클 발생 여부 알 수 있음