알고리즘 | 그래프 탐색 | 크루스칼 알고리즘(Kruskal's Algorithm)

위와 같은 MST를 어떻게 자동적으로 찾을 수 있을까?

크루스칼 알고리즘과 프림 알고리즘은 MST를 찾는 대표적인 기법이다.

 

두 알고리즘의 시간복잡도와 공간복잡도는 다음과 같다. 

(V = 정점의 수, E = 간선의 수)	Kruskal 알고리즘	Prim 알고리즘
시간복잡도 (간선 기반)	O(E*log E)	O(E*log V)
시간복잡도 (우선순위 큐 사용)	-	O(E + V*log V)
공간복잡도	O(E + V)	O(E + V)

• Kruskal 알고리즘의 경우, 간선을 정렬하는 데 가장 많은 시간이 소요되므로 O(E*log E)의 시간복잡도를 갖는다.
• Prim 알고리즘은 각 정점마다 인접한 간선 중 가장 작은 가중치를 가진 간선을 선택하므로,
  우선순위 큐를 사용할 경우 O(E + V*log V)의 시간복잡도를 갖는다.
• 공간복잡도는 두 알고리즘 모두 간선과 정점을 저장해야 하므로 O(E + V)이다.

MST를 찾을 때 대부분의 경우에는 둘 중에 뭘 써도 상관이 없지만, 상황에 따라 더 유리한 접근 방법이 있다. 

	Kruskal's Algorithm	Prim's Algorithm
무엇을 기준으로 동작하는가?	간선(Edge)	정점(Vertex)
메모리 사용량	간선의 개수에 비례하는 메모리 사용	간선의 개수가 많아도 정점의 개수에 비례하는 메모리 사용
실행 속도	간선의 정렬에 따라 시간이 소요될 수 있음	정점의 개수에 따라 결정
구현 복잡성	Union-Find 자료구조 구현 필요	우선순위 큐만을 사용
적합한 그래프 유형	희소 그래프(sparse graph)	밀집 그래프(dense graph)
기타	특정 상황에 따라 다른 구조의 최소 신장 트리를 제공할 수 있음	특정 상황에서의 최소 신장 트리 구조가 필요할 때 적합

 

 

이중에서 더 대중적인 크루스칼 알고리즘에 대해서 먼저 알아보자. 

---

크루스칼 알고리즘 (Kruskal's Algorithms)

핵심 아이디어

Kruskal 알고리즘은 다음과 같은 아이디어에서 출발한다.

 

모든 정점을 이은 경로가 최소 비용이 되려면.. 그냥 비용이 가장 작은 간선부터 차례대로 골라나가면 되잖아?

 

 

이는 매 순간 최선의 선택을 하는 그리디 알고리즘의 원리에 기반한다. 간단하게 요약하면 Kruskal 알고리즘은 1) 간선을 가중치의 오름차순으로 정렬한 후, 매 순간 2) 사이클을 형성하지 않는 간선을 차례대로 선택하는 것이다. 이 과정을 반복하면서 MST를 만들어나간다. 

 

 

알고리즘 동작 과정

우선 Union-Find 자료구조에 대한 이해가 선행되어야 한다. 까먹었다면 다음 내용 참고: (https://hyuga.tistory.com/35)

 

(가정: 인접 리스트, 또는 인접 행렬로 표현된 리스트에는 간선 연결 정보와 가중치에 대한 정보가 포함되어 있다.)

1. 초기화:
   • 모든 간선을 가중치의 오름차순으로 정렬한다.
   • 각 노드에 대해 Union-Find 자료구조(보통 parent이라는 이름의 배열)를 초기화한다. 이때, 각 노드는 자신만을 원소로 갖는 집합을 형성하게 된다. 즉, 각 노드는 부모로 자기 자신을 가리키고 있다. 
2. 간선 선택:
   • 가중치가 가장 작은 간선부터 차례대로 검토한다. (오름차순으로 정렬된 간선 리스트를 순회)
   • 간선의 두 노드가 동일한 트리에 속하는지 여부는 find 연산을 통해 확인한다.
   • 만일 동일한 트리에 속해 있다면 (즉, 사이클을 형성한다면) 해당 간선은 스킵한다. 
   • 만일 서로 다른 트리에 속해 있다면 해당 간선을 MST의 일부로 추가하고, 두 노드를 포함하는 두 집합을 합친다. (union 연산)
3. 종료 조건:
   • 모든 간선에 대한 검토가 끝날 때까지 2번 과정을 반복한다. 
   • 간선 선택 과정이 끝났을 때 선택된 간선들 == 최소 신장 트리

Kruskal 알고리즘의 핵심은 '가중치가 가장 작은 간선부터 선택하면서 MST를 구성하는 것'이고, 그 과정에서 사이클을 형성하는 간선은 pass한다는 것이다. 이를 위해 Union-Find 자료구조를 활용하여 두 노드가 같은 집합에 속해 있는지 여부를 빠르게 판단한다. 

 

여기에 성능을 추가적으로 최적화하려면, 랭크를 고려하거나 MST에 추가된 간선은 다시 추가되지 않도록 로직을 구성한다. 

 

 

코드로 이해하기

백준 1197번 문제 '최소스패닝트리'를 통해서 실제 문제 사례에 적용해보자. (https://www.acmicpc.net/problem/1197)

문제:
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력:
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력:
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

최소 스패닝 트리의 경로를 출력할 필요는 없고, 가중치의 합만 계산한 후에 출력하면 된다. 

 

'''
[MST 찾기] - Kruskal's Algorithm
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

V, E = map(int, input().split())

# 간선 정보 초기화 + 정렬
edges = [] 
for i in range(E):
    edges.append(list(map(int,input().split())))

edges.sort(key=lambda x: x[2]) # '2번 인덱스 = 가중치'를 기준으로 간선들을 정렬

# make-set
parent = [i for i in range(V+1)] # union-find 트리 (부모 정보)
rank = [0 for i in range(V+1)] # 랭크 정보 담기

# find 함수 정의
def find(x):
    if parent[x] != x: # 루트 노드가 아니라면
        parent[x] = find(parent[x]) # 재귀적으로 탐색 + 경로 압축
    return parent[x] # 루트 노드 return

# union 함수 정의
def union(x, y):
    root_x = find(x)
    root_y = find(y)

    # union-by-rank
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_x] = root_y
        rank[root_x] += 1

# MST 추출 (간선 선택)
totalCost = 0
for edge in edges:
    node_one, node_two, weight = edge[0], edge[1], edge[2]
    if find(node_one) != find(node_two): # 사이클을 형성하지 않는다면 (같은 트리에 속해있지 않다면)
        union(node_one, node_two) # 경로에 추가 (같은 트리로 합치기)
        totalCost += weight

print(totalCost)

 

 

---

참고 자료

 

https://blog.naver.com/ndb796/221230994142

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