MST와 위상정렬 (그래프 알고리즘)
그래프 알고리즘의 두 번째 영역은 연결성 구조를 다루는 알고리즘들이다. 모든 정점을 가장 싸게 연결하는 최소 신장 트리(MST)와, 선후 관계가 있는 작업을 올바른 순서로 늘어놓는 위상 정렬(Topological Sort)은 통신망 설계·강의 수강 순서·빌드 시스템·의존성 해결처럼 일상적 시스템의 핵심에 깔려 있다. 본 글은 Kruskal·Prim 두 MST 알고리즘과 Union-Find 자료구조, 그리고 Kahn·DFS 두 위상 정렬 알고리즘을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 23·22장). 제가 학교 알고리즘 과제에서 Kruskal을 단순 배열 검사로 짰다가 노드 1만짜리 그래프에서 30초 걸리던 코드가 Union-Find로 갈아 끼우자 0.2초로 떨어지는 모습을 본 후로는 "MST의 90%는 Union-Find 자료구조"라는 인상을 손끝으로 받아들였다.
최소 신장 트리(MST)의 정의와 두 가지 알고리즘
신장 트리(Spanning Tree)란 가중치 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 가리키며, 정점이 V개라면 간선은 정확히 V-1개를 갖는다. 그 신장 트리 중에서 간선 가중치 합이 최소인 것이 최소 신장 트리(MST, Minimum Spanning Tree)이다. MST는 도로·통신·전력망 설계의 표준 도구이며, 모든 정점을 가장 싸게 연결해야 하는 거의 모든 인프라 문제의 추상 모델이다.
| 알고리즘 | 전략 | 시간복잡도 | 핵심 자료구조 |
|---|---|---|---|
| Kruskal | 간선 가중치 오름차순 정렬 후 사이클 없는 간선부터 선택 | O(E log E) | Union-Find |
| Prim | 한 정점에서 시작해 매번 트리에 가장 가까운 정점 추가 | O(E log V) | 우선순위 큐 |
두 알고리즘 모두 그리디 전략이지만 접근 방식이 다르다. Kruskal은 간선 중심으로 전체에서 작은 간선부터 골라 가고, Prim은 정점 중심으로 한 지점에서 시작해 트리를 키워 간다. 어느 쪽이 빠른지는 그래프의 밀도(density)에 달려 있다. 간선이 적은 희소 그래프에서는 Kruskal이, 간선이 많은 밀집 그래프에서는 Prim이 일반적으로 빠르다.
# Kruskal — Union-Find 기반
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # 경로 압축
x = self.parent[x]
return x
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return False
if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
return True
def kruskal(n, edges):
# edges: [(weight, u, v), ...]
edges.sort()
uf = UnionFind(n)
mst = []
total = 0
for w, u, v in edges:
if uf.union(u, v):
mst.append((u, v, w))
total += w
if len(mst) == n - 1: break
return total, mst여기서 Union-Find(또는 서로소 집합, Disjoint Set)란 여러 원소를 서로소 집합으로 관리하면서 find(x)(원소가 속한 집합 대표 찾기)와 union(x, y)(두 집합 합치기) 두 연산을 매우 빠르게 수행하는 자료구조를 가리키며, 경로 압축(path compression)과 랭크에 의한 합치기(union by rank)를 결합하면 거의 O(1)에 가까운 시간(아커만 함수의 역수 α(n))에 동작한다. MST·연결 컴포넌트·동적 그래프 연결성 검사의 표준 도구이다.
# Prim — 우선순위 큐 기반
import heapq
def prim(graph, start=0):
# graph: {u: [(v, weight), ...], ...}
visited = {start}
pq = [(w, start, v) for v, w in graph[start]]
heapq.heapify(pq)
mst = []
total = 0
while pq and len(visited) < len(graph):
w, u, v = heapq.heappop(pq)
if v in visited: continue
visited.add(v)
mst.append((u, v, w))
total += w
for nv, nw in graph[v]:
if nv not in visited:
heapq.heappush(pq, (nw, v, nv))
return total, mstKruskal·Prim 모두 그리디 선택 속성이 cut property로 증명된다. cut property란 그래프를 임의로 두 집합으로 분할했을 때, 두 집합을 잇는 간선 중 최소 가중치 간선은 반드시 MST에 포함된다는 성질을 가리키며, 두 알고리즘이 매 단계 cut property를 만족하는 간선만 선택하기에 항상 최적이 보장된다.
솔직히 제 경험상 학교에서 처음 Kruskal을 단순 배열에 for 두 번 돌리는 사이클 검사로 짰을 때 시간복잡도가 O(EV)로 폭증했고, Union-Find로 갈아 끼웠을 때 처음으로 자료구조 한 줄의 선택이 알고리즘 전체 성능을 결정한다는 점을 손끝으로 받아들였다.
위상 정렬(Topological Sort) — Kahn과 DFS
위상 정렬(Topological Sort)은 방향성이 있고 사이클이 없는 그래프(DAG, Directed Acyclic Graph)의 정점을 선후 관계가 깨지지 않도록 일렬로 늘어놓는 알고리즘이다. 강의 수강 순서(선수과목)·작업 순서·빌드 시스템 의존성·Makefile·git rebase의 commit 순서·Spark·Airflow 같은 워크플로우 엔진의 DAG 실행 순서가 모두 위상 정렬의 응용이다.
| 알고리즘 | 전략 | 시간복잡도 | 사이클 검출 |
|---|---|---|---|
| Kahn (BFS 기반) | 진입 차수 0인 정점부터 차례로 제거 | O(V + E) | 모든 정점 처리 못하면 사이클 존재 |
| DFS 기반 | DFS의 후위 순회(post-order) 결과 역순 | O(V + E) | 회색 노드 재방문 시 사이클 |
여기서 진입 차수(in-degree)란 한 정점으로 들어오는 간선의 개수를 가리키며, 위상 정렬에서 "현재 시점에 시작할 수 있는 작업"을 식별하는 핵심 지표이다. Kahn 알고리즘의 본질은 매번 진입 차수가 0인 정점을 골라 빼내고, 그 정점에서 나가는 간선을 제거해 다른 정점의 진입 차수를 줄이는 일이다.
# Kahn 위상 정렬 (BFS 기반)
from collections import deque
def topological_sort_kahn(graph):
# graph: {u: [v, ...], ...}
in_deg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_deg[v] = in_deg.get(v, 0) + 1
if v not in graph: graph[v] = []
q = deque([u for u in in_deg if in_deg[u] == 0])
result = []
while q:
u = q.popleft()
result.append(u)
for v in graph[u]:
in_deg[v] -= 1
if in_deg[v] == 0:
q.append(v)
if len(result) != len(in_deg):
return None # 사이클 존재 (위상 정렬 불가)
return result
# 예시: 강의 선수과목
graph = {
"프로그래밍기초": ["자료구조", "이산수학"],
"자료구조": ["알고리즘"],
"이산수학": ["알고리즘"],
"알고리즘": ["DB응용"],
"DB응용": []
}
print(topological_sort_kahn(graph))
# ['프로그래밍기초', '자료구조', '이산수학', '알고리즘', 'DB응용']
# (BFS 순서에 따라 자료구조와 이산수학의 순서는 바뀔 수 있음)# DFS 기반 위상 정렬
def topological_sort_dfs(graph):
visited = {} # 0=미방문, 1=진행중(회색), 2=완료(검정)
stack = []
has_cycle = [False]
def dfs(u):
if visited.get(u) == 1:
has_cycle[0] = True # 회색 재방문 → 사이클
return
if visited.get(u) == 2: return
visited[u] = 1
for v in graph.get(u, []):
dfs(v)
visited[u] = 2
stack.append(u) # 후위 순회 (post-order)
for u in graph:
if visited.get(u, 0) == 0:
dfs(u)
return None if has_cycle[0] else stack[::-1]DFS 방식의 핵심 트릭이 회색·검정 두 상태로 사이클 검출이다. 회색(진행 중)인 노드를 다시 만나면 사이클이 있다는 뜻이고, 검정(완료)인 노드는 그냥 건너뛴다. 후위 순회 시점에 스택에 쌓고 마지막에 역순으로 뒤집으면 그것이 위상 정렬 결과가 된다는 점은 처음 볼 때는 직관적이지 않지만, "내 다음 단계가 모두 끝난 후에 내가 끝난다"는 DAG의 본질을 정확히 반영한 결과이다.
솔직히 이건 예상 밖이었는데, 학교에서 처음 위상 정렬이 BFS와 DFS 두 가지로 동시에 풀린다는 사실을 알고 나서 "한 문제에 두 표준 해법이 있을 때는 각각 어떤 상황에 더 자연스러운지 알아두는 게 시험과 실무 모두에서 유리하다"는 점을 손끝으로 받아들였다. Kahn은 사이클 검출과 함께 진행되어 직관적이고, DFS는 코드가 짧고 후속 의존성 분석 같은 확장에 유리하다.
MST·위상 정렬의 실전 응용
마지막으로 MST와 위상 정렬이 실제로 어디에 쓰이는지 정리하면 다음과 같다.
| 영역 | MST 응용 | 위상 정렬 응용 |
|---|---|---|
| 통신·인프라 | 광케이블 최소 비용 설계 | — |
| 소프트웨어 엔지니어링 | — | Makefile 빌드 순서·Git rebase |
| 워크플로우 엔진 | — | Apache Airflow·Spark DAG |
| 교육·HR | — | 강의 선수과목·온보딩 단계 |
| 클러스터링 | 데이터 마이닝의 single-linkage | — |
| 회로 설계 | VLSI 라우팅 | 게이트 평가 순서 |
특히 빌드 시스템·CI/CD·데이터 파이프라인이 모두 DAG 기반으로 작업 의존성을 표현하고 위상 정렬로 실행 순서를 결정한다는 점에서, 위상 정렬은 컴퓨터 시스템에서 가장 자주 실행되는 알고리즘 중 하나이다(출처: 위키백과 — Topological sorting).
마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "최소 신장 트리(MST)는 가중치 그래프의 모든 정점을 연결하면서 간선 가중치 합이 최소인 부분 트리이며, Kruskal(간선 정렬 + Union-Find, O(E log E))과 Prim(우선순위 큐, O(E log V)) 두 그리디 알고리즘이 표준이다. 위상 정렬은 DAG의 정점을 선후 관계가 깨지지 않게 늘어놓는 알고리즘이며, Kahn(진입 차수 BFS)과 DFS(후위 순회 역순) 두 방식이 모두 O(V+E)에 동작하고 사이클이 있으면 위상 정렬이 불가능하다"는 두 문장이 표준 답안 표현으로 통한다.
메타 디스크립션: 최소 신장 트리(MST) 두 알고리즘 Kruskal·Prim과 Union-Find 자료구조, 위상 정렬의 두 표준 알고리즘 Kahn(BFS)·DFS, 그리고 빌드 시스템·DAG 워크플로우 같은 실전 응용을 알고리즘 입문자 관점에서 세심하게 정리합니다.