위상 정렬: 의존성으로 순서 매기기

"양말 전에 신발을 못 신어. 위상 정렬은 'X 가 Y 보다 먼저' 규칙 뭉치를 주면, 모든 걸 할 유효한 순서를 건네는 — 또는 규칙이 자기모순이라고 알려주는 — 알고리즘이야."

문제

엣지 X→Y 가 "X 가 Y 보다 먼저" 를 뜻하는 방향 비순환 그래프 (DAG) 가 주어지면, 위상 정렬이 모든 노드를, 각 노드가 모든 선행조건 뒤에 나타나는 선형 순서로 만들어. 천 개 일상 시스템 뒤의 수학이야: 빌드 도구가 의존성 순으로 파일 컴파일, 패키지 매니저가 의존성 먼저 설치, 강의 선수과목, 작업 스케줄러, 스프레드시트 셀이 맞는 순서로 재계산, Python 이 네 모듈 import 하는 순서까지. 질문이 "이 상호의존하는 것들을 할 유효한 순서가 뭐야?" 면, 위상 정렬이야.

Kahn 알고리즘: 준비된 것부터 벗겨내

가장 직관적인 방법은 진입 차수 (in-degree) — 각 노드가 아직 안 채운 선행조건이 몇 개냐 — 로 작동해. 반복해서: 남은 선행조건이 0 인 (실행 준비된) 노드를 아무거나 가져와, 출력하고, 그 나가는 엣지를 제거해 (이웃의 진입 차수를 줄여, 걔네도 준비되게 할 수도). 준비된 노드를 담는 데 큐를 써. 다 출력될 때까지 계속. BFS 향이야: 현재 할 수 있는 작업의 frontier 를 처리하면 다음 frontier 가 열려. O(V + E).

대안은 DFS 후위: 그래프를 DFS 하고, 각 노드가 끝날 때 (모든 후손 완료), 답 앞에 붙여. 후위를 뒤집으면 유효한 위상 순서야. 둘 다 표준; Kahn 이 종종 추론하기 쉬워, '선행조건 0 = 준비됨' 이 직관에 깔끔히 매핑되니까.

위상 정렬은 DAG 를 선형화해 모든 노드가 선행조건 뒤에 와. Kahn 알고리즘은 진입차수 0 (준비된) 노드를 큐로 반복 출력; DFS 후위 뒤집어도 돼. 둘 다 O(V+E) — 그리고 둘 다 순환을 공짜로 검출해.

보너스: 순환 검출

위상 정렬은 DAG — 순환 없는 그래프 — 에서만 작동해. 그리고 그게 위반되면 알려줘: Kahn 알고리즘에서, 전부 출력하기 전에 진입차수 0 노드가 떨어지면, 남은 노드가 순환을 이뤄 (상호 의존: A 가 B 필요, B 가 A 필요 — 어느 것도 절대 '준비' 못 돼). 진짜 쓸모 있는 진단이야: "순환 의존성 검출됨" 을 보고하는 빌드 시스템이 실패한 위상 정렬이야. 그래서 알고리즘은 할 수 있는 걸 순서 매길 뿐 아니라 — 유효한 순서가 애초에 존재하는지 증명해.

피파의 고백

빌드가 "순환 의존성" 으로 처음 실패했을 때, 도구가 뭘 하는지조차 몰랐어. 나중에 Kahn 알고리즘을 배우니, 소급해서 딸깍했어: 빌드가 내 모듈의 위상 정렬을 시도하다, 선행조건-0 파일이 떨어졌고, 남은 게 서로 import 하는 두 모듈이었어. 에러는 신비한 도구가 아니라 — 정확히 이 알고리즘이 내 의존성 그래프에 순환이 있다고 알려준 거였어. 알고리즘을 이해하니 몇 년을 cargo-cult 하던 에러가 설명됐어.

Code

Kahn 알고리즘 + 내장 순환 검출·python

from collections import deque

# Kahn 알고리즘: 진입차수 0 노드를 없어질 때까지 출력.
def topo_sort(graph):
    # 진입 차수 = 각 노드가 아직 가진 선행조건 수
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    # 선행조건 없는 모든 것으로 시작
    q = deque([u for u in graph if indeg[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)               # u 가 준비됨 -> 출력
        for v in graph[u]:
            indeg[v] -= 1             # v 의 선행조건 하나 충족
            if indeg[v] == 0:         # v 가 이제 안 채운 선행조건 없음
                q.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected — no valid ordering exists")
    return order

# 'app' 은 backend+frontend 필요; 둘 다 database 필요.
deps = {"database": ["backend", "frontend"], "backend": ["app"],
        "frontend": ["app"], "app": []}
print(topo_sort(deps))   # ['database', 'backend', 'frontend', 'app'] (유효한 순서)

# 순환은 유효한 순서가 없어:
cycle = {"a": ["b"], "b": ["a"]}
try: topo_sort(cycle)
except ValueError as e: print(e)   # cycle detected — no valid ordering exists

Exercise

강의: 미적분은 대수 필요; 물리는 미적분이랑 대수 필요; 화학은 대수 필요. Kahn 알고리즘 (선행조건-0 강의에서 시작) 으로, 전부 들을 유효한 순서 하나를 만들어. 그다음: 누가 '대수는 물리 필요' 를 더하면, Kahn 알고리즘이 뭘 보고하고 왜?

Hint

선행조건-0 시작: 대수. 대수 후: 미적분이랑 화학이 준비; 그다음 미적분 끝나면 물리. 유효한 순서: 대수, 미적분, 화학, 물리. '대수는 물리 필요' 추가는 순환 (대수↔물리, 미적분 경유) 을 만들어 — Kahn 이 진입차수-0 노드가 떨어져 순환을 보고.

문제

Kahn 알고리즘: 준비된 것부터 벗겨내

보너스: 순환 검출

피파의 고백

Code

External links

Exercise

Progress

댓글 0