🗂️ Graph Theory 5: MST with Kruskal & Prim

🎡 Spanning Tree

그래프 내부에 포함된 모든 노드를 포함하는 트리를 의미한다. 모든 정점을 포함하긴 하지만 근본은 트리라서 사이클이 발생하면 안되며, 최소의 간선을 사용해 모든 노드를 연결해야 한다. 따라서 Spanning Tree 의 간선 개수는 노드 개수-1에 해당한다.

💵 Minimum Spanning Tree

그래프 상에서 발생할 수 있는 여러 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미한다. MST를 구현하는 알고리즘은 대표적으로 Kruskal, Prim알고리즘이 있다. 전자의 시간 복잡도는 O(ElogE), 후자는 기본적으로 O(N^2)이라서 노드에 비해 간선 개수가 적은 희소 그래프의 경우는 Kruskal을, 노드에 비해 간선이 많은 밀집 그래프의 경우는 Prim을 사용하는게 시간 복잡도 측면에서 유리하다. 한편, Prim은 구현시에 선택하는 자료구조에 따라서 시간 복잡도를 최적화할 수 있다. 자세한 내용은 개별 알고리즘에 대한 설명에서 다루도록 하겠다.

🍃 Kruskal Algorithm (간선 선택)

그리디하게 그래프의 모든 정점을 최소 비용으로 연결하는 방법이다. 구체적으로는 개별 시점에서 사이클을 이루지 않으면서 최소 비용인 간선을 경로로 선택한다. 그리디를 기반으로 하기 때문에 이전 결과, 미래 결과를 고려하지 않고 현재 최소 비용이 되는 간선만을 선택한다. 알고리즘의 구체적인 동작 과정은 다음과 같다.

• 1) 그래프의 간선들을 오름차순으로 정렬, 가중치 기준
• 2) 사이클을 발생시키는지 여부를 체크하면서 순서대로 선택
  • 가장 낮은 가중치부터 접근해 체크
  • 사이클 발생 X라면 선택
• 3) 선택한 간선을 MST집합에 추가

사이클을 발생시키는지 여부를 체크하는 부분이 구현할 때 까다로울 수 있는데, Union-Find 알고리즘을 도입하면 수월하게 만들어 낼 수 있다. Union-Find를 도입한 Kruskal Algorithm을 Python 코드로 작성하면 다음과 같다.

""" kruskal algorithm example: baekjoon 1043 """

import sys

def find(arr: list, x: int) -> int:
    """ method for finding root node """
    if arr[x] != x:
        arr[x] = find(arr, arr[x])
    return arr[x]

def union(arr: list, x: int, y: int):
    """ method for union-find """
    x = find(arr, x)
    y = find(arr, y)
    if x < y:
        arr[y] = x
    else:
        arr[x] = y

N = int(sys.stdin.readline())  # number of nodes
M = int(sys.stdin.readline())  # number of edges
graph, parent = [], [0]*(N+1)

# 0-0) 간선 연결 정보 초기화, 정렬
for _ in range(M):
    src, end, cost = map(int, sys.stdin.readline().split())
    graph.append((cost, src, end))
graph.sort()

# 0-1) 연결 정보 초기화
for i in range(1, N+1):
    parent[i] = i

# 1) Kruskal Algorithm
result = 0
for j in range(M):
    weight, start, final = graph[j]
    if find(parent, start) != find(parent, final):
        union(parent, start, final)
        result += weight

print(result)

find 메서드는 입력한 노드의 루트 노드를 찾아 반환한다. 이것을 활용해 서로 다른 노드가 같은 집합(트리)에 속하는지 손쉽게 판정할 수 있으며 이것은 바꿔 생각해보면 선택된 두 노드가 사이클을 발생시키는지 여부를 알아 낼 수 있다는 것이다. 만약 두 노드가 같은 루트 노드값을 갖는다면, 결국 같은 집합(트리)에 속한다는 것을 의미하며, 이것은 사이클을 유발하게 되는 것이다. 따라서 사이클을 유발하는 정점은 선택하지 않으며, 트리의 성질을 유지할 수 있는 노드를 선택해 union 연산에 대입한다.

🔴 Prim Algorithm (정점 선택)

특정 정점에서 시작해서 가중치가 작은 간선들 순서대로 트리를 확장해나가는 방법이다. 시작점을 지정한다는 점에서 다익스트라와 유사하며, 간선의 숫자가 많은 밀집 그래프 상황에서 Kruskal보다 빠르다. 구체적인 동작 방식은 다음과 같다.

• 1) 선택 노드를 MST 집합에 추가
• 2) MST 집합에 포함된 노드들에 인접한 정점들 탐색
  • 사이클 발생 여부 확인
    • 사이클 발생 X: 최소 가중치의 간선을 선택
• 3) 전체 간선의 개수가 N-1개가 될 때까지, 1 & 2 과정 Iteration

기본적으로는 O(N^2)의 시간복잡도를 기록한다. 하지만 자료구조 최적화에 따라서 Kruskal과 비슷한 시간복잡도인 O(ElogE)정도로까지 만들어 낼 수 있다. 최소 힙정렬과 우선순위 큐를 이용하면 된다. 힙정렬을 이용해 그래프 연결 정보를 가중치를 기준으로 오름차순 정렬을 한 뒤에, 사이클을 발생시키지 않는 인접 노드를 선택하도록 만든다.

""" prim algorithm example: baekjoon 1197 """

import sys, heapq
from typing import List
"""
[풀이]
1) Prim with 우선순위 큐 (힙)
    - 시작점 선택, MST 집합에 추가
    - MST 집합의 노드들에 인접한 모든 정점 탐색
        - 사이클 발생 여부 확인: 방문 여부로 판정
        - 사이클 발생 X: 최소 가중치 간선 선택 (heapify를 통해 개별 노드마다 간선들을 가중치 기준 오름차순 정렬)
"""

def prim(grid: List[List], visit: List[bool], start: int) -> int:
    visit[start] = True
    tmp = grid[start]  # 선택된 노드에 대한 모든 인접 간선 추출
    heapq.heapify(tmp)  # 이미 생성되어 있는 자료구조에 대해서는 heapq.heapify를 사용하면 힙 성질을 만족하도록 할 수 있다
    mst, total = [], 0
    while tmp:
        weight, u, v = heapq.heappop(tmp)
        if not visit[v]:  # 미방문 노드로의 간선만 선택하는 방식으로, 사이클 발생 여부 판정하는 알고리즘을 구현
            visit[v] = True
            mst.append((u, v))
            total += weight
            for edge in graph[v]:
                if not visit[edge[2]]:
                    heapq.heappush(tmp, edge)
    return total

def solution():
    result = prim(graph, visited, 1)  # 시작 노드를 어떤 것으로 설정해도 상관 없음
    print(result)

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    V, E = map(int, sys.stdin.readline().split())
    graph, visited = [[] for _ in range(V+1)], [False]*(V+1)
    for _ in range(E):
        src, end, cost = map(int, sys.stdin.readline().split())
        graph[src].append([cost, src, end])
        graph[end].append([cost, end, src])
    solution()

시작 정점은 아무거나 선택해도 상관없다. 그리고 가장 주목할 부분은 노드 선택시 사이클 여부를 판정하는 방법을 어떻게 구현했는가이다. 개별 노드에 대한 방문여부를 기록하는 배열을 따로 생성한 뒤, 방문(해당 노드와 연결되는 간선 선택)할 때 마다 방문 기록을 저장한다. 그리고 만약 어떤 노드를 선택했을 때, 이미 방문한 노드라면 해당 노드와 연결하는 간선의 가중치가 현재 가장 최소에 해당하더라도 사이클을 발생시키기 때문에 선택하지 않도록 사이클 여부를 판정하게 만들었다.
Kruskal처럼 전체 모든 간선을 알고 있는 상태가 아님에도 최소 스패닝 트리의 조건을 만족하는 결과를 만들어 낼 수 있는 이유는 미리 개별 노드별 간선들을 가중치 기준으로 오름차순 정렬 해뒀기 때문이다. 이것 때문에 지역 최적들의 합이 전역 최적이 되어야 하는 그리디의 제약 조건을 만족시킬 수 있게 된다.