최소 스패닝 트리(MST)

최소 스패닝 트리(MST)

최소 스패닝 트리는 그래프에서 최소한의 간선만을 연결해 가중치가 최소가 되는 트리이자 그래프이다

그래프에서 최소한의 간선을 이용해 모든 정점을 연결하려면,
간선은 정점의 개수 - 1개 만큼을 필요로 한다

그리고 임의의 그래프를 최소 스패닝 트리로 만드는 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘을 사용할 수 있다

크루스칼(Kruskal)

크루스칼 알고리즘은 그래프의 가중치가 가장 작은 간선부터 사이클이 생기지 않도록 정점의 개수(V)-1개 만큼 선택하는 그리디 알고리즘이다

사이클의 발생 여부는 분리 집합을 통해 선택할 간선의 두 정점이 서로 같은 부모를 가리키는지 확인함으로써 판단할 수 있다

실습 1

[1197] 최소 스패닝 트리에 크루스칼을 적용해 문제를 해결하면 다음과 같이 코드를 작성할 수 있다

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def find_parent(x):
    if x == pointer[x]: return x

    pointer[x] = find_parent(pointer[x])
    return pointer[x]

def union(a, b):
    x = find_parent(a)
    y = find_parent(b)

    if x < y: pointer[y] = x
    else: pointer[x] = y

def is_union(a, b):
    x = find_parent(a)
    y = find_parent(b)

    if x == y: return True
    else: return False

V, E = map(int, input().split())
pointer = [i for i in range(V+1)]
edge = []
total = 0
for _ in range(E):
    A, B, C = map(int, input().split())
    edge.append((C, A, B))

edge.sort()

for w, a, b in edge:
    if is_union(a, b): continue

    union(a, b)
    total += w

print(total)

이 과정에 대한 시간복잡도는 $O(ElogE)$ 이며, 간선 E개를 오름차순으로 정렬하는 과정에서 이러한 시간복잡도가 나게 된다

프림(Prim)

프림 알고리즘은 임의의 한 노드를 지정하고 그 노드로부터 가장 적은 가중치와 인접된 노드를 선택해나가며 적은 가중치의 간선을 선택하고 갱신하는 그리디 알고리즘이다

위 그래프에서 임의의 한 노드로 1번 노드를 시작으로 하고 알고리즘을 진행해보자

이때 각 노드에 대한 정보를 담은 초기 테이블은 다음과 같다

이제 다음 과정을 거친다

1. 방문이 완료되지 않은 노드중에 인접 간선의 값이 가장 작은 노드를 선택한다

2. 1에서 선택된 노드와 인접한 노드를 최소 가중치 값으로 갱신한다

위 1, 2의 과정을 남은 방문이 완료되지 않은 노드에 대해 모두 방문할 때까지 진행한다

원래 3번 노드는 1과 인접하여 3으로 갱신되었으나, 2와 인접하여 더 작은 2로 갱신된 것이다

3번 노드를 방문 완료할 때는 갱신할 값이 없고, 4를 방문 완료할 때에도 그렇다

따라서 최종 테이블은 다음과 같다

결국 노드가 가지는 값은 선택한 가장 작은 간선이 무엇인지를 의미하는 것이 된다

실습 2

[1197] 최소 스패닝 트리에 프림을 적용해 문제를 해결하면 다음과 같이 코드를 작성할 수 있다

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def Prim(x):
    length[x] = 0
    heap = [(0, x)]
    while heap:
        _, s = heappop(heap)
        current = s
        visited[current] = True
        if s not in graph: continue

        for d, e in graph[current]:
            if not visited[e] and d < length[e]:
                length[e] = d
                heappush(heap, (d, e))

        del(graph[current])

V, E = map(int, input().split())
length = [0] + [float('inf') for _ in range(V)]
visited = [True] + [False for _ in range(V)]
graph = {
    # 출발 정점 s : { ( 가중치 w, e), ... }
}
for _ in range(E):
    A, B, C = map(int, input().split())
    if A not in graph:
        graph[A] = [(C, B)]
    else: graph[A].append((C, B))

    if B not in graph:
        graph[B] = [(C, A)]
    else: graph[B].append((C, A))

Prim(1)
print(sum(length))

1번 노드를 선택해 1번 노드부터 다른 노드로 뻗어나가도록 구성했다

최소 값을 가지는 방문하지 않은 정점을 찾는데의 시간으로인해 프림 알고리즘은 $O(V^2)$의 시간복잡도를 가지지만, 최소 힙을 통해 최소 값을 가지는 정점을 빠르게 찾는다면 $O(ElogV)$까지 단축시킬 수 있다