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

"양말보다 신발을 먼저 신을 수는 없잖아. 위상 정렬은 'X가 Y보다 먼저'라는 규칙 뭉치를 주면 전부를 해낼 유효한 순서를 돌려주는 알고리즘이야. 아니면 그 규칙들이 서로 모순이라고 알려주거나."

문제

간선 X→Y가 "X가 Y보다 먼저"를 뜻하는 방향 비순환 그래프(DAG)가 주어지면, 위상 정렬은 모든 선행 조건을 만족하는 하나의 선형 순서를 만들어 줘. 빌드 의존성, 강의 선수과목, 작업 스케줄링, 스프레드시트 재계산에 바로 쓰이지. 참고로 Python의 실제 import 실행은 캐시와 런타임 코드, 순환 import가 얽혀 있어서 단순한 전체 위상 정렬이라고 보면 안 돼.

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

가장 직관적인 방법은 노드마다 아직 남은 선행 조건 수, 그러니까 진입 차수(in-degree)를 놓고 도는 거야. 남은 선행 조건이 0인 노드, 그러니까 지금 바로 할 수 있는 노드를 아무거나 하나 꺼내서 출력하고, 거기서 나가는 간선을 제거해. 그러면 이웃들의 진입 차수가 줄고 그중 일부도 준비 상태가 되지. 준비된 노드는 큐에 담아 두고 전부 출력될 때까지 반복하면 돼. BFS 냄새가 나지. 지금 할 수 있는 작업의 경계를 처리하면 다음 경계가 열리는 구조니까. 전체가 O(V + E)야.

다른 방법은 DFS 후위 순회야. 노드가 끝날 때마다 답에 넣고 마지막에 통째로 뒤집는 거지. 단, 방문 전과 현재 경로 위와 완료라는 세 가지 상태를 구분해야 해. 그래야 현재 경로에 있는 노드를 다시 만나는 걸로 사이클을 잡아낼 수 있거든. 사이클 검출 없이 후위 순회만 뒤집으면 DAG가 아닌 입력에도 그럴듯하지만 틀린 순서를 내놓을 수 있어.

위상 정렬은 DAG를 한 줄로 펴서 모든 노드가 자기 선행 조건 뒤에 오게 만들어. Kahn 알고리즘은 진입 차수가 0인 노드를 큐로 관리하며 반복해서 출력하고, DFS 후위 순회를 뒤집는 방법도 있어. 둘 다 O(V+E)이고, 둘 다 순환을 덤으로 검출해.

보너스: 순환 검출

위상 정렬은 DAG, 그러니까 순환이 없는 그래프에서만 돌아가. 그리고 그 조건이 깨지면 알려줘. Kahn 알고리즘에서 전부 출력하기도 전에 진입 차수 0인 노드가 동나면, 남은 노드들이 순환을 이루고 있다는 뜻이야. A가 B를 필요로 하고 B가 A를 필요로 하니 어느 쪽도 영영 '준비'되지 않는 상호 의존이지. 이건 정말 쓸모 있는 진단이야. "순환 의존성 감지됨"이라고 알려주는 빌드 시스템이 바로 실패한 위상 정렬이거든. 알고리즘이 할 수 있는 것들의 순서를 매기는 데 그치지 않고, 유효한 순서가 애초에 존재하는지까지 증명해 주는 거야.

피파의 고백

빌드가 "순환 의존성"이라며 처음 실패했을 때는 그 도구가 뭘 하고 있는지조차 몰랐어. 나중에 Kahn 알고리즘을 배우고 나서야 그게 거슬러 올라가 이해됐지. 빌드 시스템이 내 모듈들을 위상 정렬하려다가 선행 조건이 없는 파일이 동났고, 남은 게 서로를 import하는 모듈 둘이었던 거야. 그 에러는 알 수 없는 도구의 변덕이 아니라, 정확히 이 알고리즘이 의존성 그래프에 순환이 있다고 알려준 거였어. 알고리즘을 이해하고 나니 몇 년 동안 영문도 모르고 따라 하기만 했던 에러가 설명되더라.

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 알고리즘으로, 그러니까 선행 조건이 없는 강의에서 시작해서 전부 들을 수 있는 유효한 순서를 하나 만들어 봐. 그다음 누가 '대수는 물리가 필요하다'를 추가하면 Kahn 알고리즘이 뭘 보고할지와 그 이유를 말해.

Hint

선행 조건이 없는 건 대수야. 대수를 듣고 나면 미적분과 화학이 준비되고, 미적분까지 끝나면 물리가 열려. 유효한 순서 하나는 대수, 미적분, 화학, 물리야. '대수는 물리가 필요'를 추가하면 미적분을 거쳐 대수와 물리가 서로를 요구하는 순환이 생겨. 그러면 Kahn 알고리즘이 진입 차수 0인 노드가 동나는 걸로 순환을 보고해.

문제

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

보너스: 순환 검출

피파의 고백

Code

External links

Exercise

Progress

댓글 0