N 개의 정점(노드)와 M 개의 간선(에지)로 이루어진 그래프가 있을 때, 스패닝 트리란 아래 조건을 만족하는 에지들의 집합이다.

1. 임의의 두 노드를 골랐을 때, 스패닝 트리에 속하는 간선만을 이용해서 두 노드가 연결될 수 있어야 하며,

2. 스패닝 트리를 구성하는 간선의 개수는 총 N-1개이다.

즉 모든 노드들이 어떻게든 직간접적으로 연결되어야 하는데, 이 때 간선의 개수를 최소로 하는 트리를 의미하는 것이다.

위의 전체 그래프에서 스패닝 트리는 굵은 선으로 이루어진 트리 외에도 다양하게 만들어낼 수 있다.

모든 노드가 연결되고, 간선의 개수가 N-1개인 싸이클을 형성하지 않는 트리이면 모두 가능하지만, 여기서 굵은 선으로 이루어진 트리의 경우에는 조금 특별하다.

이를 수많은 스패닝 트리들 중에, 트리를 이루는 간선들의 가중치의 합이 최소가 되는, 최소 스패닝 트리(MST) 라고 한다.

개념

이런 최소 스패닝 트리를 만들기 위한 알고리즘들 중 하나가 크루스칼 알고리즘이다.

크루스칼은 그리디를 기반으로 하여 그래프를 구성한다.

MST의 목표는 모든 노드들을 최대한 적은 비용으로 연결시키는 것이기 때문에, 그리디한 방식으로 단순히 가장 적은 가중치(비용)를 갖는 간선부터 순서대로 선택하는 것이다.

그러나 무지성으로 적은 비용의 순서대로만 추가하면 문제가 발생하는데, 어떤 에지를 추가시킴으로써 MST 내에서 싸이클이 형성되는 경우가 이에 해당한다.

MST의 전체 간선이 N-1개라는 것은 임의의 두 노드 사이에 연결되는 경로는 어떻게든 하나만 존재한다는 뜻이며, 그렇기 때문에 모든 노드가 최소한의 간선으로만 연결될 수 있다는 뜻인데, 싸이클이 형성되는 경우에는 불필요한 간선들이 추가되는 것이기 때문이다.

사실 싸이클이 형성되지 않아야 한다는 조건은 트리라는 개념의 기본적인 조건이기도 하다.

에지를 순서대로 검사하는 과정에서 이들이 싸이클을 형성하는지 확인하는 방법으로는 유니온 파인드를 활용할 수 있다.

에지를 이루는 두 노드의 루트 노드를 탐색하여, 같은 루트일 경우에는 이미 서로 연결된 상태이기 때문에 싸이클이 형성되기 때문이다.

이렇게 가중치 순서대로 에지를 검사해나가며, 총 N-1개의 에지가 MST를 구성하는 순간 목표를 달성했기 때문에 나머지 에지들은 검사해줄 필요가 없으므로 종료한다.

코드

import heapq

# 순환 여부를 확인하기 위한 유니온-파인드 활용
parents = [i for i in range(N)]
def _find(x):
    # 경로 압축 기법 활용
    if parents[x] == x: return x
    parents[x] = _find(parents[x])
    return parents[x]

# 입력으로 들어오는 에지 리스트를 모두 우선순위큐에 가중치를 기준으로 입력
# 우선순위큐에는 거리(가중치)가 짧은 에지들부터 나오게 됨
pq = []
for line in edges.split('\n'):
    p, q, w = map(int, line.split())
    heapq.heappush(pq, (w, (p, q)))

# cnt = 최소 스패닝 트리를 형성 중인 에지의 수
cnt = 0
# cost = 최소 스패닝 트리의 비용
cost = 0
while len(pq) > 0:
    # 가장 거리가 짧은 에지를 뽑아낸 뒤
    c, (a, b) = heapq.heappop(pq)
    # 에지를 이루는 두 노드가 서로 연결되는지(순환을 이루는지) 확인
    A, B = _find(a), _find(b)
    # 만약 순환을 이루지 않는다면, 이번 에지를 MST에 연결시켜도 됨
    if A != B:
        cnt += 1
        cost += c
        parents[A] = B
    # 에지가 N-1 개 연결됐다는 뜻은, 모든 노드가 한 줄로 연결됐다는 뜻이므로 종료
    if cnt == N-1:
        break
print(cost)

예시

아래와 같은 N = 6, M = 7 인 그래프에서 최소 스패닝 트리를 구하는 과정을 살펴보자.

1. 입력으로 들어오는 모든 에지들을, 가중치를 기준으로 하는 우선순위 큐에 넣었다고 생각함으로써 가중치가 낮은 간선들부터 확인해나간다.

2. 가장 낮은 가중치를 갖는 간선은 노드 2-4 가 연결된 에지이며, 두 노드는 연결되어있지 않은 상태이기 때문에 MST에 포함시킨 뒤, parents 배열을 수정하여 연결 처리를 해준다.

3. 그다음 가중치는 노드 1-2가 연결된 에지이며, 마찬가지로 연결되지 않았기 때문에 동일하게 처리해준다.

4. 그다음 에지 4-6 과 1-3 까지 위와 동일하게 처리해주고, 현재까지의 MST는 위에서부터 3-1-2-4-6 으로 연결 되어있다.

5. 다음으로는 가중치 5를 갖는 에지 2-3을 확인하는데, 노드 2와 노드 3은 이미 MST에 둘 다 포함되어있기 때문에, 이 에지를 연결할 경우 순환이 발생하며 MST가 깨지게 된다.

6. 따라서 해당 에지를 포함시키지 않고 건너뛴 다음, 에지 4-5를 확인하여 포함시킨다.

7. 4-5 에지까지 넣음으로써 간선의 개수가 5개가 되었고, 모든 노드들이 다 연결되었기 때문에 MST가 만들어지며 다른 에지들을 검사할 필요가 없어지므로 여기서 종료하면 된다.