· 개발

위상 정렬과 순환 감지: 진입 차수로 순서를 정하고 막힌 곳 찾기

의존 관계를 실행 순서로 바꾸는 위상 정렬을 진입 차수 방식으로 구현하고, 순환이 있을 때 무엇이 남는지와 Python graphlib의 TopologicalSorter·CycleError 동작을 정리합니다.

algorithmsgraphtopological-sortpython

빌드 단계, 패키지 설치, 데이터베이스 마이그레이션처럼 “A가 끝나야 B를 할 수 있다”는 제약이 여러 개 얽혀 있으면, 모든 제약을 지키는 실행 순서를 하나 정해야 합니다. 이 작업이 위상 정렬(topological sort)입니다. 제약이 꼬여 순환을 이루면 그런 순서는 존재하지 않기 때문에, 위상 정렬은 순환 감지와 함께 다루는 편이 실용적입니다.

이 글에서는 진입 차수(in-degree)를 세는 방식으로 위상 정렬을 직접 구현하고, 순환이 있을 때 알고리즘이 어디서 멈추는지 살펴본 뒤, Python 표준 라이브러리의 graphlib.TopologicalSorter가 같은 문제를 어떤 API로 다루는지 봅니다. Python 동작은 3.13, 3.14, 3.15 공식 문서를 기준으로 했습니다.

위상 순서의 정의

방향 그래프에서 모든 간선 u → v에 대해 u가 v보다 앞에 오도록 정점을 일렬로 나열한 것을 위상 순서라고 합니다. 완전한 위상 순서는 그래프에 방향 순환이 없을 때, 즉 DAG(directed acyclic graph)일 때만 존재합니다.

여기서 두 가지를 먼저 짚어 두겠습니다.

  • 답이 하나가 아닐 수 있습니다. 서로 의존하지 않는 두 작업은 어느 쪽이 먼저 와도 됩니다.
  • 간선 방향의 의미를 먼저 고정해야 합니다. 이 글에서 u → v는 “u가 v보다 먼저 와야 한다”는 뜻입니다.

진입 차수로 구현하기

진입 차수가 0인 정점, 즉 기다릴 선행 작업이 없는 정점은 지금 바로 내보낼 수 있습니다. 정점 하나를 내보내고 그 정점에서 나가는 간선을 지우면, 진입 차수가 새로 0이 되는 정점이 생깁니다. 이 과정을 더 내보낼 정점이 없을 때까지 반복합니다.

from collections import deque

def topo_sort(nodes, edges):
    # edges의 (u, v)는 "u가 v보다 먼저"를 뜻한다
    indegree = {n: 0 for n in nodes}
    succ = {n: [] for n in nodes}
    for u, v in edges:
        succ[u].append(v)
        indegree[v] += 1

    queue = deque(n for n in nodes if indegree[n] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in succ[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order  # len(order) < len(nodes)이면 순환이 있다

정점은 큐에 최대 한 번 들어가고, 간선마다 진입 차수를 한 번씩 줄이므로 시간 복잡도는 O(V + E)입니다. 진입 차수 표와 인접 리스트를 합친 추가 공간도 O(V + E)입니다.

순환이 있으면 어디서 멈추나

순환 위의 정점들은 서로를 기다리기 때문에 어느 것도 진입 차수가 0이 되지 못합니다. 그래서 큐가 먼저 비고, order의 길이가 정점 수보다 짧아집니다. 위 코드는 이 차이로 순환 여부를 판단할 수 있습니다. 반대로 순환이 없다면 남은 정점 중 진입 차수 0인 정점이 항상 하나는 있으므로 모든 정점이 출력됩니다.

다만 남은 정점이 전부 순환에 속하는 것은 아닙니다. a와 b가 서로를 기다리고 b → c 간선이 있다면 c도 남지만, c는 순환의 일부가 아니라 순환 뒤에서 막혀 있을 뿐입니다. 사용자에게 “이 노드들이 순환을 이룬다”고 알려 주려면 남은 정점 안에서 실제 순환을 따로 찾아야 합니다.

방법은 간단합니다. 남은 정점은 모두 남은 선행 정점을 하나 이상 가집니다(진입 차수가 0보다 크니까요). 따라서 아무 남은 정점에서 출발해 남은 선행 정점을 계속 거슬러 올라가면, 정점 수가 유한하므로 언젠가 이미 지나온 정점을 다시 만납니다. 그 사이 구간이 순환입니다.

def find_cycle(nodes, edges, order):
    done = set(order)
    preds = {n: [] for n in nodes}
    for u, v in edges:
        if u not in done and v not in done:
            preds[v].append(u)

    n = next(x for x in nodes if x not in done)
    seen = {}
    path = []
    while n not in seen:
        seen[n] = len(path)
        path.append(n)
        n = preds[n][0]
    # path는 선행 방향으로 거슬러 올라간 순서이므로 뒤집어서 반환한다
    return (path[seen[n]:] + [n])[::-1]

반환값은 첫 원소와 마지막 원소가 같고, 각 원소가 다음 원소의 직접 선행 정점인 리스트입니다. 아래에서 볼 graphlib의 순환 보고 형식과 같은 규칙으로 맞췄습니다.

Python graphlib.TopologicalSorter

Python 3.9부터 표준 라이브러리에 graphlib 모듈이 있고, 위상 정렬용 TopologicalSorter 클래스를 제공합니다. 노드는 해시 가능해야 합니다.

가장 먼저 헷갈리는 부분은 그래프를 넘기는 방향입니다. 생성자에 넘기는 딕셔너리는 키가 노드, 값이 그 노드의 선행 노드들입니다. 흔히 쓰는 “노드 → 후행 노드” 인접 리스트와 반대이므로, 그대로 넘기면 순서가 뒤집힙니다.

from graphlib import TopologicalSorter

# 키: 작업, 값: 그 작업보다 먼저 끝나야 하는 작업들
deps = {
    "test": {"build"},
    "build": {"codegen", "fetch"},
    "codegen": {"fetch"},
}
print(list(TopologicalSorter(deps).static_order()))
# ['fetch', 'codegen', 'build', 'test']

이 그래프는 가능한 위상 순서가 하나뿐이라 출력이 정해져 있습니다. 서로 독립인 노드가 있으면 사정이 다릅니다. 공식 문서는 반환 순서가 그래프에 항목을 넣은 순서에 따라 달라질 수 있다고 명시하고, add() 호출 순서만 바꿔 다른 결과가 나오는 예를 보여 줍니다. 테스트에서 특정 순서를 그대로 비교하기보다 “모든 간선 u → v에서 u가 앞에 있는가”를 검사하는 편이 안전합니다.

병렬 실행용 API

static_order()는 한 줄로 순서를 받을 때 쓰고, 작업을 병렬로 돌릴 때는 prepare(), get_ready(), done()을 직접 씁니다.

ts = TopologicalSorter(deps)
ts.prepare()
while ts.is_active():
    for task in ts.get_ready():
        run(task)      # 실제로는 작업 큐에 넣는다
        ts.done(task)  # 끝난 작업을 알려야 후행 작업이 풀린다

get_ready()는 지금 실행할 수 있는 노드를 모두 담은 튜플을 반환합니다. 처음에는 선행 노드가 없는 노드 전부이고, 이후에는 done()으로 선행 노드가 모두 처리된 노드가 새로 나옵니다. 같은 호출에서 함께 나온 노드끼리는 서로 기다릴 필요가 없으므로 동시에 실행할 수 있습니다. 공식 문서의 예제도 get_ready() 결과를 작업 큐에 넣고, 워커가 끝낸 노드를 받아 done()을 부르는 구조입니다. 위 코드는 흐름을 보이려고 같은 자리에서 done()을 불렀을 뿐입니다.

is_active()는 더 진행할 수 있으면 True를 반환합니다. 문서의 정의로는 순환에 막히지 않았고, 아직 get_ready()로 넘겨지지 않은 준비된 노드가 있거나 done() 처리된 노드 수가 get_ready()로 넘겨진 노드 수보다 적은 경우입니다.

CycleError

prepare()는 그래프에 순환이 있으면 ValueError의 하위 클래스인 graphlib.CycleError를 발생시킵니다. static_order()로 순회할 때도 마찬가지입니다.

from graphlib import TopologicalSorter, CycleError

deps = {"a": {"b"}, "b": {"c"}, "c": {"a"}}
try:
    list(TopologicalSorter(deps).static_order())
except CycleError as e:
    print(e.args[1])

순환은 예외 객체의 args 두 번째 원소에 노드 리스트로 들어 있습니다. 리스트의 각 노드는 다음 노드의 직접 선행 노드이고, 순환임을 알 수 있도록 첫 노드와 마지막 노드가 같습니다. 순환이 여러 개면 그중 하나만 보고되며 어느 것이 선택될지는 정해져 있지 않습니다. 위 예제에서도 리스트가 어느 노드에서 시작할지는 문서가 보장하지 않으므로, 출력값을 테스트에 고정하지 않는 편이 좋습니다.

prepare()가 CycleError를 던진 뒤에도 get_ready()는 계속 쓸 수 있고, 순환에 막히기 전까지 처리 가능한 노드를 최대한 얻을 수 있습니다. 앞에서 본 “순환 뒤에서 막히는 노드”는 이 방식으로도 끝내 나오지 않습니다.

버전별로 다른 점

  • graphlib은 Python 3.9에서 추가되었습니다.
  • prepare() 이후에는 그래프를 바꿀 수 없고, add()를 부르면 ValueError가 납니다.
  • Python 3.14부터는 정렬을 시작하기 전이라면 prepare()를 여러 번 불러도 됩니다. 이전 버전에서는 두 번째 호출이 ValueError였습니다. static_order()나 get_ready()로 정렬을 시작한 뒤에 prepare()를 부르면 3.14 이후에도 ValueError입니다.

구현할 때 확인할 것

  • 간선 방향: 직접 구현에서는 “u가 v보다 먼저”, graphlib에서는 “키의 값 = 선행 노드”입니다. 두 규칙을 섞으면 결과가 거꾸로 나옵니다.
  • 순환 판정: 출력된 정점 수가 전체보다 적으면 순환이 있습니다. 남은 정점 목록을 그대로 순환이라고 보고하면 순환 뒤에서 막힌 정점까지 섞입니다.
  • 출력 순서: 독립 노드 사이의 순서는 입력 순서에 따라 달라질 수 있으므로, 테스트는 특정 순서가 아니라 제약 충족 여부를 확인해야 합니다.

블로그로