위상 정렬: 먼저 할 일부터 한 줄로 세우기

어느 모듈부터 컴파일할지, 어느 과목부터 들을지처럼 「이것을 끝내야 저것을 한다」는 조건이 얽혀 있으면 차례를 정해야 합니다. 「다음」을 눌러 한 걸음씩 줄을 세워 보세요.

한 줄 답. 위상 정렬은 「먼저 해야 하는 일」이 간선(edge)으로 적힌 그래프에서, 모든 간선이 앞에서 뒤로 향하게 정점(vertex)을 한 줄로 세우는 것입니다. 쉬운 방법은 들어오는 간선이 없는 정점(먼저 할 것이 없는 일)을 큐에 넣고, 하나씩 꺼내 줄에 세우면서 그 정점에서 나가는 간선을 지우는 것입니다. 간선이 사이클(cycle)을 이루면 그런 줄은 없습니다. 걸리는 시간은 정점 수 + 간선 수에 비례합니다.

큐(앞 → 뒤). 왼쪽 끝이 다음에 나옵니다:
정한 순서:

정점 하나를 꺼내는 일을 걸음 셋으로 나눴습니다: 큐에서 꺼내 순서에 놓기 → 나가는 간선을 지우고 진입 차수 줄이기 → 0 이 된 정점을 큐에 넣기. 상자 오른쪽 위 숫자는 아직 지우지 않은 들어오는 간선의 수(진입 차수)이고, 줄어드는 걸음에는 「2 → 1」처럼 옛 값과 새 값을 적습니다. 상자 아래 이름표 「3번째」는 정한 순서의 자리, 「큐 1」은 큐의 자리(1 이 다음에 나옴), 「못 놓음」은 끝까지 놓지 못한 정점입니다. 상자 위 작은 화살표는 이번 걸음에 꺼낸 정점(「꺼냄」)이나 큐에 들어간 정점(「큐에 들어감」)을 가리킵니다. 주황은 지금 다루는 정점과 지금 지우는 간선(점선), 초록은 순서에 놓은 정점, 파란 점선은 큐에서 기다리는 정점, 빨강은 끝까지 놓지 못한 정점과 사이클을 이루는 굵은 간선(「사이클」)입니다. 흐린 간선은 이미 지운 것입니다. 「거꾸로 가는 간선 더하기」를 누르면 처음 걸음으로 돌아갑니다.

1. 방향 그래프와 위상 정렬

위 그래프의 정점은 지어낸 프로그램의 모듈 8개입니다. 간선 X → Y 는 「X 를 먼저 빌드해야 Y 를 빌드할 수 있다」, 곧 Y 가 X 를 가져다 쓴다는 뜻입니다. 그래프 탐색 쪽의 간선은 양쪽으로 다닐 수 있었지만, 여기 간선에는 방향이 있습니다. 이런 그래프를 방향 그래프라고 부릅니다.

위상 정렬은 정점을 한 줄로 세우되, 모든 간선이 줄의 앞 정점에서 뒤 정점으로 향하게 하는 것입니다. 이 줄대로 빌드하면 어느 모듈을 빌드하든 그것이 가져다 쓰는 모듈은 이미 빌드되어 있습니다.

간선을 따라가다 처음 정점으로 돌아오는 사이클이 있으면 이런 줄은 없습니다. 사이클 위의 정점은 저마다 사이클의 앞 정점보다 뒤에 서야 해서, 한 바퀴 돌면 자기가 자기보다 뒤에 서야 하기 때문입니다. 사이클이 없는 방향 그래프를 DAG 라고 부르고, 위상 순서는 그래프가 DAG 일 때, 그리고 그때만 있습니다(출처 ①).

Python 으로는 정점마다 그 정점 뒤에 와야 하는 정점(간선이 가는 곳)을 적은 dict 로 담습니다. 간선은 9개입니다.

after = {"config": ["db"], "utils": ["db", "ui"], "db": ["auth", "api"], "auth": ["api"],
         "api": ["app"], "ui": ["app"], "app": ["test"], "test": []}

2. Kahn 알고리즘(Kahn's algorithm): 기다릴 것이 없는 일부터

정점마다 들어오는 간선의 수를 셉니다. 책에서는 진입 차수라고 부릅니다. 「먼저 끝나야 하는 일이 아직 몇 개 남았나」입니다.

  1. 진입 차수가 0 인 정점을 모두 큐에 넣는다. 먼저 할 것이 없는 일이다.
  2. 큐에서 정점 하나를 꺼내 줄의 맨 뒤에 세운다.
  3. 그 정점에서 나가는 간선을 지운다. 곧 간선이 가는 정점마다 진입 차수를 1 줄이고, 0 이 된 정점을 큐에 넣는다.
  4. 큐가 빌 때까지 2 ~ 3 을 되풀이한다.

꺼낸 정점은 진입 차수가 0 이라, 그 정점보다 앞에 와야 하는 정점은 이미 모두 줄에 서 있습니다. 그래서 줄 맨 뒤에 세워도 거꾸로 가는 간선이 생기지 않습니다.

해 볼 것. ① 처음 큐에는 config, utils 둘이 들어갑니다. 들어오는 간선이 없는 정점은 이 둘뿐입니다. ② 「다음」을 20 번 누르면 순서는 config, utils, db, ui, auth, api, app, test 입니다. 정점 8개를 꺼내는 걸음 8번, 간선을 지우는 걸음 7번(test 는 나가는 간선이 없음), 큐에 넣는 걸음 5번입니다. 그림의 간선 9개가 모두 이 순서의 앞에서 뒤로 갑니다. ③ 걸음 6 에서 db 를 꺼내고 걸음 7 에서 그 간선을 지우면 auth 는 0 이 되지만 api 는 1 로 남습니다. api 는 auth 도 기다리기 때문입니다. 그래서 걸음 8 에서 큐에 들어가는 것은 auth 하나입니다. ④ 큐는 가장 길 때 2 칸입니다(처음, 걸음 5, 걸음 8).

3. 손으로 따라가기

위 실험과 같은 그래프입니다. 처음 진입 차수는 config 0, utils 0, db 2, auth 1, api 2, ui 1, app 2, test 1 입니다. 한 줄이 큐에서 정점 하나를 꺼내는 한 차례입니다. 위 실험은 한 차례를 꺼내기, 간선 지우기, 큐에 넣기의 걸음 셋으로 나눠 보여 줍니다(지울 간선이나 0 이 된 정점이 없으면 그 걸음은 없습니다). 큐는 왼쪽이 앞(다음에 나올 것)입니다.

차례꺼낸 정점진입 차수를 줄인 정점(줄인 뒤 값)꺼낸 뒤 큐정한 순서왜
0(처음)–config utils(없음)들어오는 간선이 없는 정점은 이 둘뿐이다
1configdb 1utilsconfigdb 는 utils 도 기다린다
2utilsdb 0, ui 0db uiconfig utilsdb 와 ui 가 기다리던 정점이 모두 줄에 섰다
3dbauth 0, api 1ui authconfig utils dbauth 는 db 만 기다렸고, api 는 auth 도 기다린다
4uiapp 1authconfig utils db uiapp 은 api 도 기다린다
5authapi 0apiconfig utils db ui authapi 가 기다리던 db, auth 가 모두 줄에 섰다
6apiapp 0appconfig utils db ui auth apiapp 이 기다리던 ui, api 가 모두 줄에 섰다
7apptest 0testconfig utils db ui auth api apptest 는 app 만 기다렸다
8test(나가는 간선 없음)(빔)config utils db ui auth api app test큐가 비어 끝난다

4번째 차례를 보세요. ui 를 꺼내 app 을 1 로 줄였지만 app 은 아직 api 를 기다립니다. app 은 6번째 차례에서 api 가 나온 뒤에야 큐에 들어갑니다.

4. 사이클이 있으면 끝까지 못 간다

실험의 「거꾸로 가는 간선 더하기」를 누르면 auth → config 간선이 생깁니다. config 가 auth 를 가져다 쓰게 바꾼 것입니다. 그러면 config → db → auth → config 가 사이클이 됩니다. 셋 다 사이클의 앞 정점을 기다리니, 셋 중 아무도 먼저 큐에 들어가지 못합니다.

해 볼 것. ① 켜면 처음 큐에는 utils 하나만 들어갑니다. config 에 간선이 하나 들어와 진입 차수가 1 이 되었기 때문입니다. ② 「다음」을 다섯 번 누르면 utils, ui 를 놓고 큐가 빈 채로 끝납니다. ③ 남은 정점은 config, db, auth, api, app, test 6 개입니다. 사이클 위에 있는 것은 config, db, auth 셋이고, api, app, test 는 사이클 뒤에 있어서 같이 막혔습니다.

그래서 Kahn 알고리즘은 사이클 검사도 됩니다. 큐가 비었을 때 줄에 선 정점이 전체보다 적으면 사이클이 있습니다. 다만 남은 정점이 모두 사이클 위에 있는 것은 아닙니다.

5. 깊이 우선으로: 후위 순서를 뒤집기

깊이 우선 탐색으로도 줄을 세울 수 있습니다. 간선 방향으로만 들어가며 훑되, 한 정점에서 나가는 간선을 끝까지 다 따라간 다음(그 정점이 「끝난」 때) 그 정점을 목록에 적습니다. 사이클이 없는 그래프에서 이 후위 순서(postorder)를 뒤집으면 위상 순서입니다(출처 ①).

까닭은 이렇습니다. 사이클이 없을 때 X → Y 간선이 있으면 Y 는 X 보다 먼저 끝납니다. Y 를 이미 훑었다면 벌써 끝났고, 아직이라면 X 가 끝나기 전에 Y 로 들어가 끝내고 나오기 때문입니다. 그래서 후위 순서를 뒤집으면 X 가 Y 앞에 섭니다.

def topo_dfs(after):
    done, finished = set(), []
    def visit(node):
        done.add(node)
        for next_node in after[node]:
            if next_node not in done:
                visit(next_node)
        finished.append(node)   # 나가는 간선을 다 따라간 뒤에 적는다
    for node in after:
        if node not in done:
            visit(node)
    return finished[::-1]

print(topo_dfs(after))   # ['utils', 'ui', 'config', 'db', 'auth', 'api', 'app', 'test']
후위 순서(먼저 끝난 것이 왼쪽) testappapiauthdbconfiguiutils utilsuiconfigdbauthapiapptest 뒤집은 순서 = 위상 순서
후위 순서를 뒤집기. 위 코드가 1절의 그래프를 훑으면 test 가 가장 먼저 끝나고 utils 가 가장 늦게 끝납니다(위 줄). 이 줄을 뒤집은 아래 줄이 위 코드가 내놓는 순서이고, 간선 9개가 모두 왼쪽에서 오른쪽으로 갑니다.

Kahn 알고리즘과 다른 순서가 나왔지만 이것도 간선 9개를 모두 지킵니다. 이 코드는 사이클을 검사하지 않습니다. 사이클이 있으면 위상 순서가 없으니, 무엇을 내놓든 거꾸로 가는 간선이 생깁니다. 사이클이 없는지는 따로 확인해야 합니다.

6. 걸리는 시간

걸리는 시간 ∝ V + E          (책의 표기: O(V + E))

깊이 우선 방법도 정점마다 한 번 들어가고 간선마다 한 번 따라가므로 V + E 에 비례합니다(출처 ①). 위 그래프는 V = 8, E = 9 입니다.

7. 언제 무엇을 쓰나

방법걸리는 시간(가장 좋을 때 · 보통 · 가장 나쁠 때)더 드는 메모리좋은 점나쁜 점쓰는 경우
Kahn 알고리즘(진입 차수)V + E · V + E · V + E. 늘 모든 정점과 간선을 한 번씩 본다(둘 다 두 배면 두 배)진입 차수 V 칸 + 큐(많아야 V 칸)재귀가 없다. 큐가 빌 때 남은 정점으로 사이클을 바로 알아챈다. 같은 때 큐에 있는 정점끼리는 서로 기다리지 않는다진입 차수를 미리 세야 한다사이클이 있을 수 있는 입력, 순서와 함께 사이클 검사가 필요할 때
깊이 우선(후위 순서 뒤집기)같다방문 표시 V 칸 + 후위 순서 목록 V 칸 + 재귀 깊이(많아야 V)깊이 우선 탐색 코드에 「끝날 때 적기」 한 줄을 더하면 된다사이클을 따로 검사해야 한다. 재귀로 짜면 아주 긴 경로에서 호출이 너무 깊어질 수 있다사이클이 없다고 알고 있을 때, 깊이 우선 탐색을 이미 쓰고 있을 때

직접 짜기 싫으면 Python 표준 라이브러리의 graphlib 을 씁니다(8절).

8. Python 으로

from collections import Counter, deque

def topo_queue(after):
    indegree = Counter(node for targets in after.values() for node in targets)   # 정점마다 들어오는 간선 수
    queue, order = deque(node for node in after if indegree[node] == 0), []
    while queue:
        node = queue.popleft()
        order.append(node)
        for next_node in after[node]:
            indegree[next_node] -= 1
            if indegree[next_node] == 0:
                queue.append(next_node)
    return order   # 정점 수보다 짧으면 사이클이 있다

print(topo_queue(after))   # ['config', 'utils', 'db', 'ui', 'auth', 'api', 'app', 'test']

after 는 1절의 dict 입니다. 표준 라이브러리에도 있습니다(Python 3.9 부터).

from graphlib import TopologicalSorter

before = {node: [m for m in after if node in after[m]] for node in after}   # 정점마다 먼저 와야 하는 정점
print(list(TopologicalSorter(before).static_order()))   # ['config', 'utils', 'db', 'ui', 'auth', 'api', 'app', 'test']

TopologicalSorter 는 간선을 거꾸로 받습니다. dict 의 키가 정점이고, 값은 그 정점보다 먼저 와야 하는 정점들입니다. static_order() 는 위상 순서로 정점을 내놓고, 나오는 순서는 넣은 순서에 따라 달라질 수 있습니다. 사이클이 있으면 CycleError(ValueError 의 한 갈래)를 냅니다(출처 ②).

어디에 쓰나

자주 묻는 것

위상 순서는 하나뿐인가요?

아닙니다. 이 쪽의 그래프에서 Kahn 알고리즘은 config, utils, db, ui, auth, api, app, test 를, 깊이 우선 방법은 utils, ui, config, db, auth, api, app, test 를 냅니다. 둘 다 모든 간선을 지킵니다. Python 의 graphlib 문서도 나오는 순서가 넣은 순서에 따라 달라질 수 있다고 적습니다.

사이클이 있는지는 어떻게 아나요?

Kahn 알고리즘에서 큐가 비었는데 줄에 서지 못한 정점이 남으면 사이클이 있습니다. graphlib 의 TopologicalSorter 는 CycleError 를 냅니다. 남은 정점이 모두 사이클 위에 있는 것은 아닙니다. 사이클 뒤에 있어서 같이 막힌 정점도 남습니다.

너비 우선 탐색과 같은 것인가요?

둘 다 큐를 쓰지만 넣는 때가 다릅니다. 너비 우선 탐색은 이웃을 보자마자 넣고, 위상 정렬의 Kahn 알고리즘은 들어오는 간선이 모두 지워져 진입 차수가 0 이 되었을 때만 넣습니다. 그래서 출발 정점 하나가 아니라 진입 차수가 0 인 정점 모두에서 시작합니다.

낱말

여기서 쓴 말책에서 부르는 말
정점정점(vertex), 노드(node)
간선방향 간선(directed edge)
방향 그래프방향 그래프(directed graph, digraph)
사이클방향 순환(directed cycle)
사이클 없는 방향 그래프DAG(directed acyclic graph)
들어오는 간선의 수진입 차수(indegree)
들어오는 간선이 없는 정점소스(source)
한 줄로 세우기위상 정렬(topological sort)
세운 줄위상 순서(topological order)
진입 차수와 큐를 쓰는 방법Kahn 알고리즘(Kahn's algorithm)
끝난 순서후위 순서(postorder)
끝난 순서를 뒤집은 것역후위 순서(reverse postorder)

출처

← 그래프 탐색: 너비·깊이 우선다익스트라 →