위상 정렬

수치해석 소프트웨어 시뮬레이션 마지막 수정: 2026-08-28 04:31:09

1. 개요[편집]

위상 정렬 Topological sorting
대상	유향 비순환 그래프(DAG)
정의	모든 간선 $u \to v$ 에 대해 $u$ 가 $v$ 보다 앞서는 정점 나열
존재 조건	사이클이 없을 것 — 필요충분
알고리즘	칸(1962, 진입차수 큐) · DFS 후위순 역순
복잡도	$\Theta(V+E)$
유일성	매 단계 진입차수 0 정점이 하나 ⟺ 해밀턴 경로 존재
대표 파생	DAG 최장경로(CPM) · 역모드 자동미분 · 희소 삼각 풀이

위상 정렬(topological sorting)은 유향 비순환 그래프의 정점을, 모든 간선 $u \to v$ 에 대해 $u$ 가 $v$ 보다 앞에 오도록 일렬로 늘어놓는 것이다. 순서집합의 언어로는 부분순서를 그것과 모순되지 않는 전순서로 확장하는 것이라 선형 확장(linear extension)이라고도 부른다. “선후 관계가 정해진 것들은 그 순서를 지키고, 안 정해진 것들은 아무렇게나 놔도 된다”는 게 전부다.

정의가 이렇게 싱거운데도 이 문서가 존재하는 이유는 두 가지다. 첫째, 존재 조건이 곧 사이클 탐지다. 위상 정렬이 존재하지 않는다는 것과 그래프에 사이클이 있다는 것이 정확히 같은 말이라, 위상 정렬 알고리즘은 정렬기이자 동시에 사이클 검출기다. 사이클이 있는 그래프에 억지로라도 순서를 주고 싶다면 강한 연결 요소로 먼저 뭉개는 수밖에 없다. 둘째, DAG 위의 거의 모든 동적 계획법이 위상 순서를 전제로 한다. 최장경로, 경로 개수 세기, 역전파 — 전부 “선행자가 이미 확정돼 있어야” 성립하는 점화식이고, 그 “이미”를 보장하는 것이 위상 순서다.

2. 존재와 유일성[편집]

정리. 유향그래프 $G$ 에 위상 정렬이 존재한다 $\iff$ $G$ 가 DAG 다.

( $\Rightarrow$ ) 순서 $v_1, \dots, v_n$ 이 있는데 사이클이 있다면, 사이클 위 정점 중 순서상 가장 앞선 것으로 들어오는 간선이 그보다 뒤에 있는 정점에서 나와야 하므로 모순이다. ( $\Leftarrow$ ) DAG 에는 진입차수 0 인 정점이 반드시 있다(없으면 아무 정점에서 역방향으로 계속 걸어갈 수 있는데, 정점이 유한하므로 언젠가 반복 → 사이클). 그것을 맨 앞에 놓고 지운 뒤 귀납. $\blacksquare$

정렬은 대개 여러 개다. 극단적으로 간선이 하나도 없으면 $n!$ 개다. 세는 문제 — 선형 확장의 개수 — 는 놀랍게도 #P-완전이라 다항시간에 정확히 셀 수 없고, 실무에서는 마르코프 연쇄 몬테카를로로 근사한다.¹

유일한 경우는 정확히 기술할 수 있다. 다음이 서로 동치다.

위상 정렬이 유일하다.
칸 알고리즘의 매 단계에서 진입차수 0 인 정점이 정확히 하나다.
그 순서 $v_1, \dots, v_n$ 에서 연속한 쌍마다 간선 $v_i \to v_{i+1}$ 이 존재한다 — 즉 DAG 에 해밀턴 경로가 있다.
이행 폐포가 전순서다(모든 정점 쌍이 비교 가능).

마지막 조건이 실무 감각을 준다. 빌드 의존성이 “유일한 순서”를 갖는다는 것은 곧 병렬화할 여지가 하나도 없다는 뜻이다. 순서가 많이 갈릴수록 좋은 그래프다. 일반 그래프의 해밀턴 경로 판정은 NP-완전이지만 DAG 에서는 위상 정렬 한 번으로 끝난다는 것도 여기서 나오는 덤이다.

3. 칸 알고리즘[편집]

아서 칸이 1962년에 발표한, 사람이 손으로 하는 방식 그대로다.²

진입차수 indeg[] 계산
Q = { v : indeg[v] == 0 }
while Q not empty:
    v = Q.pop();  결과에 v 추가
    for each edge v -> w:
        if --indeg[w] == 0: Q.push(w)
if 결과 길이 < V: 사이클 존재

$\Theta(V+E)$ 이고, 마지막 두 줄이 공짜 사이클 검출이다. 큐에 남지 못한 정점들의 집합이 바로 “사이클에 갇혔거나 사이클에서 도달 가능한” 부분이라, 진단 메시지를 만들 때 그대로 쓸 수 있다.

Q 의 자료구조를 바꾸면 성질이 달라진다.

FIFO 큐 — 각 반복에서 동시에 꺼낼 수 있는 정점 집합이 자연스럽게 레벨로 묶인다. 레벨 $k$ 는 “소스에서 가장 긴 경로 길이가 $k$ 인 정점들”이고, 레벨 개수가 곧 임계 경로 길이다. 병렬 스케줄링의 wavefront 가 이것이다.
최소 힙(우선순위 큐) — 사전순으로 가장 작은 위상 정렬을 준다. $O((V+E)\log V)$ . “결과가 재현 가능해야 하는” 빌드 도구가 이 짓을 한다.
LIFO 스택 — 결과가 DFS 방식과 비슷해지지만 같지는 않다. 스택 순서는 캐시 지역성이 좋다.

4. DFS 후위순 뒤집기[편집]

두 번째 고전 방법. DFS 를 돌리며 정점의 탐색이 끝나는 순간(후위, postorder) 리스트에 밀어 넣고, 마지막에 뒤집는다.

dfs(v):
    color[v] = GRAY
    for each edge v -> w:
        if color[w] == GRAY: 사이클!      # 역간선
        if color[w] == WHITE: dfs(w)
    color[v] = BLACK;  post.push(v)
결과 = reverse(post)

옳은 이유는 한 줄이다. 간선 $u \to v$ 가 있으면 DAG 에서는 항상 $v$ 의 종료 시각이 $u$ 보다 이르다. ( $v$ 가 흰색이면 $u$ 안에서 재귀 호출되어 먼저 끝나고, 검은색이면 이미 끝났으며, 회색이면 역간선 = 사이클이라 가정에 어긋난다.) 따라서 종료 시각 내림차순이 위상 순서다.

사이클 검출은 회색 정점으로 가는 간선(역간선)으로 한다. visited 불리언 하나만 쓰고 3색을 쓰지 않으면 교차 간선을 사이클로 오인해서 멀쩡한 DAG 를 순환이라고 신고하는데, 실무 코드에서 꾸준히 반복되는 버그다.

칸과 DFS 중 무엇을 쓸지는 취향과 부수 요구사항이 정한다. 사전순 최소나 레벨 구조가 필요하면 칸, 재귀로 이미 그래프를 훑고 있고 정렬은 부산물이면 DFS. 다만 DFS 는 강한 연결 요소의 타잔 알고리즘과 코드가 거의 겹치므로, 사이클이 있을 수도 있는 그래프를 다룬다면 애초에 SCC 를 구하고 축약 그래프를 위상 정렬하는 편이 낫다. 그러면 “사이클이 있어서 실패”가 아니라 “사이클 덩어리는 이것들이고 그 사이의 순서는 이렇다”는 훨씬 쓸모 있는 답이 나온다.

5. DAG 최장경로와 임계 경로[편집]

일반 그래프의 최장경로는 NP-완전이다(해밀턴 경로가 특수 사례). 그런데 DAG 에서는 위상 순서 한 번이면 $\Theta(V+E)$ 에 끝난다. 위상 순서대로 훑으며

d[v] \;=\; \max_{u \to v}\ \bigl(d[u] + w(u,v)\bigr), \qquad d[\text{소스}] = 0

을 채우면 그만이다. 순서를 지켜 훑기 때문에 $d[u]$ 가 항상 이미 확정돼 있다는 것이 유일한 논거다. 음수 가중치도 문제없고 — 사이클이 없으니 음수 사이클도 없다 — 그래서 벨만-포드 알고리즘이나 다익스트라 알고리즘보다 빠르고 조건도 느슨하다. DAG 라는 정보 하나가 최단경로 문제를 동적 계획법 문제로 강등시키는 셈이다.

프로젝트 관리에서 이것을 임계 경로법(CPM)이라 부른다. 작업이 정점, 선후 관계가 간선, 소요 시간이 가중치일 때 최장경로가 전체 공기이고, 그 경로 위의 작업들이 임계 작업이다. 위상 순서로 한 번 전진해 가장 이른 시작시각(ES)을, 역위상 순서로 한 번 후진해 가장 늦은 시작시각(LS)을 구하면 여유(slack) $= LS - ES$ 가 나온다. 여유 0 인 작업이 임계 작업이고, 그것만 늦어도 전체가 늦는다. 전진·후진 두 번의 스윕이라는 구조는 뒤에 나올 역모드 자동미분과 정확히 같은 골격이다.

6. 시뮬레이션 쪽 응용[편집]

6.1. 역모드 자동 미분[편집]

자동 미분의 역방향 모드는 계산 그래프를 순방향으로 한 번 평가하며 기록한 뒤, 역위상 순서로 수반값(adjoint)을 누적한다.

\bar{v} \;=\; \sum_{v \to u} \bar{u}\,\frac{\partial u}{\partial v}

이 합이 옳으려면 $v$ 를 처리하는 시점에 $v$ 를 쓰는 모든 후속 노드 $u$ 의 $\bar u$ 가 완성돼 있어야 한다. 그것을 보장하는 것이 정확히 역위상 순서다. 딥러닝 프레임워크의 테이프(tape)는 사실 순방향 실행 순서를 그대로 기록한 것이고, 그 순서가 이미 하나의 위상 정렬이므로 뒤집어 쓰면 된다 — 역전파에서 “그냥 거꾸로 돌린다”고 말하는 그 동작의 정체가 이것이다.

여기에도 조건이 붙는다. 계산 그래프가 DAG 여야 한다. 순환 신경망은 시간 축으로 펼쳐(unroll) DAG 로 만든 뒤에야 미분되고, 암시적 층(고정점 반복, 미분방정식 솔버)은 아예 펼치지 않고 수반 방정식을 따로 세운다. 사이클이 있으면 위상 정렬이 없다는 명제가 여기서 실무 제약으로 되돌아온다.

6.2. 희소 삼각 풀이와 소거 순서[편집]

희소행렬에서 하삼각 $L$ 에 대해 $Lx = b$ 를 푸는데 $b$ 도 희소하다면, $x$ 의 0 이 아닌 위치는 $L$ 의 그래프에서 $b$ 의 비영 위치로부터 도달 가능한 정점 집합이다. 그 집합을 DFS 로 구하면서 후위순을 뒤집으면 곧바로 위상 순서가 나오고, 그 순서대로만 대입하면 전체 $n$ 이 아니라 실제 연산량에 비례하는 시간에 풀린다. 길버트-파이얼스의 좌향(left-looking) 희소 LU 가 열마다 이 짓을 반복해서 만들어진다.³ LU 분해를 희소로 옮길 때 “그래프 알고리즘이 왜 여기 나오냐”는 질문의 답이 이것이다.

한 걸음 더 나가면, DAG 를 위상 순서대로 번호 매기는 것은 곧 인접행렬을 상삼각으로 만드는 치환이다. 강한 연결 요소 쪽에서 다루는 블록 삼각화가 SCC + 위상 정렬로 이루어지는 이유가 여기 있다. 반대로 병렬 삼각 풀이의 레벨 스케줄링은 칸 알고리즘을 FIFO 로 돌린 그 레벨 집합을 그대로 쓴다 — 같은 레벨 안의 미지수들은 서로 의존하지 않으므로 동시에 계산해도 된다. 레벨 수가 적을수록 병렬성이 좋고, 그래서 전처리기 설계에서 “레벨이 몇 개 나오나”가 실제 성능 지표로 쓰인다.

6.3. 모듈러 시뮬레이션과 대수 루프[편집]

미분대수방정식이나 블록 선도 기반 모델링에서, 방정식과 미지수를 짝지은 뒤 위상 정렬을 시도하면 정렬이 되면 축차 대입으로 풀리고, 안 되면 대수 루프다. 공동 시뮬레이션(FMI co-simulation)에서 여러 FMU 의 입출력을 연결했을 때 방향 그래프에 사이클이 생기면 같은 스텝 안에서 서로의 출력을 기다리는 교착이 생기고, 이때는 지연 요소를 끼우거나 루프를 하나의 비선형 방정식계로 묶어 푼다. 진단 도구가 “순서를 찾을 수 없습니다”라고 말할 때 내부에서 실패한 것이 정확히 이 절차다.

6.4. 그 밖에[편집]

빌드 시스템(make 의 타깃 그래프), 패키지 의존성 해결, 스프레드시트 재계산 순서(순환 참조 오류 = 위상 정렬 실패), 명령어 스케줄링, 메시 생성 후처리의 절차 의존성, 게임 엔진의 렌더 패스 그래프 — 목록은 사실상 무한하다. 공통점은 하나다. “뭘 먼저 해야 하나”를 사람이 손으로 관리하는 순간 그 시스템은 반드시 썩는다는 것.

7. 관련 문서[편집]

강한 연결 요소 · 2-SAT · 이행 폐포
깊이 우선 탐색 · 임계 경로법 · 빌드 시스템
동적 계획법 · 다익스트라 알고리즘 · 벨만-포드 알고리즘 · 우선순위 큐
자동 미분 · 역전파
희소행렬 · LU 분해 · 전처리기 · 미분대수방정식
NP-완전 · 조합 최적화 · 마르코프 연쇄 몬테카를로

Brightwell, G. & Winkler, P. (1991). “Counting linear extensions”. Order 8, 225–242. “정렬 하나 찾기는 선형 시간, 몇 개인지 세기는 #P-완전”이라는 이 격차는 조합론에서 흔한 패턴이다. 근사 쪽은 사정이 좋아서 선형 확장을 균등하게 뽑는 마르코프 연쇄가 빠르게 섞인다는 것이 알려져 있고, 덕분에 개수 추정은 실용적으로 가능하다. 정확히 세는 것만 안 될 뿐이다. ↩
Kahn, A. B. (1962). “Topological sorting of large networks”. CACM 5(11), 558–562. 제목의 “large”가 그 시절엔 정점 수천 개였다. 논문의 동기가 PERT/CPM 이라는 점도 재미있는데, 결국 60년이 지나 같은 알고리즘이 신경망 역전파를 돌리고 있다. ↩
Gilbert, J. R. & Peierls, T. (1988). “Sparse partial pivoting in time proportional to arithmetic operations”. SIAM J. Sci. Stat. Comput. 9(5), 862–874. 제목이 곧 결론이다. 그 전까지 희소 LU 는 “부분 피벗팅을 하면 패턴을 미리 못 정하니 어쩔 수 없이 손해”라는 게 통념이었는데, 도달성 계산을 매 열마다 끼워 넣어 그 손해를 없앴다. 그래프 알고리즘이 수치선형대수에 정면으로 들어온 사건. ↩