위상 정렬 Kahn vs DFS 고르는 법, 순환 의존 탐지 비용과 점검표

빌드 단계나 마이그레이션, 작업 스케줄러에 의존 관계 정렬을 넣으려는데 Kahn 으로 갈지 DFS 로 갈지, 아니면 표준 라이브러리를 쓸지 고민되시죠? 결론부터 말하면 순서와 병렬 단계가 필요하면 Kahn(진입 차수 + 큐), 사이클이 났을 때 "어디가 고리인지" 보여 줘야 하면 3색 DFS를 고르고, 서비스에서는 둘을 같이 쓰는 경우가 많아요. 시간 복잡도는 둘 다 O(V+E) 라서 고르는 기준은 속도보다 "무엇을 돌려줘야 하나"예요.

이 글은 원리 증명 대신 고르는 기준과 직접 잰 숫자를 다뤄요. 시간은 Apple M1, 파이썬 3.15.2 로 쟀어요(2026-11-05). 절대 시간은 기기마다 다르니 방식 사이의 배수로 읽어 주세요. 최단 거리냐 경로 모양이냐로 BFS·DFS 를 고르는 큰 기준은 BFS DFS 언제 쓰나, 문제 유형별 판단표에 있고, 여기서는 방향 그래프의 순서 정하기와 고리 찾기만 봐요.

위상 정렬·사이클 탐지 판단표, 무엇을 돌려줘야 하나

같은 그래프를 다루더라도 호출하는 쪽이 원하는 결과가 다르면 고를 방법이 달라져요. 먼저 "정상일 때 무엇을, 사이클일 때 무엇을 돌려줄지"를 한 줄씩 적어요.

표에서 Kahn 과 DFS 가 갈리는 지점은 두 줄이에요. 병렬 단계는 Kahn 이 거저 주고, 고리 경로는 DFS 가 거저 줘요. Kahn 은 사이클이 있으면 "끝까지 못 꺼낸 정점이 남는다"는 것만 알려 주고, DFS 는 회색(지금 재귀 경로 위) 정점을 다시 만나는 순간 그 경로를 그대로 돌려줄 수 있어요.

파이썬 실행 시간 직접 재기, Kahn·DFS·graphlib

CSES 1679 Course Schedule 의 제약(정점 n ≤ 10⁵, 간선 m ≤ 2·10⁵, 1초)과 같은 크기의 무작위 DAG 를 만들고, 다섯 구현을 각각 5번 돌려 가장 빠른 값을 적었어요. 모든 결과가 "모든 간선 u→v 에서 u 가 v 보다 앞"인지 따로 검증했어요.

읽을 점이 셋이에요.

• Kahn 과 반복형 DFS 는 사실상 같아요. 205ms 대 209ms 라 속도로 고를 이유가 없어요. 재귀 DFS 가 134ms 로 가장 빨랐지만, 정점이 일렬로 길게 이어지면 재귀 깊이 문제가 생겨요(아래).
• 사전순 최소 순서는 힙 비용이 들어요. 같은 그래프에서 354ms, 큐의 약 1.7배였어요. "실행할 때마다 같은 순서"만 필요하면 사전순까지 갈 필요 없이 준비 목록을 정렬하는 것으로 충분한 경우가 많아요.
• graphlib 은 약 8배 느렸어요. 중앙값으로 나눠 보면 딕셔너리 만들기 234ms, TopologicalSorter 생성 640ms, prepare() 460ms, get_ready()/done() 반복 336ms 였어요. CPython 소스를 보면 prepare() 가 순서를 내기 전에 _find_cycle() 로 사이클 검사를 한 번 따로 돌려요. 정점 수천 개짜리 설정 파일이나 빌드 단계라면 몇 ms 라 문제없고, 요청마다 정점 수만 개를 정렬하는 경로라면 직접 짜는 쪽이 나아요.

메모리는 tracemalloc 최고치로 Kahn 2.3MiB, 반복형 DFS 2.7MiB, 재귀 DFS 3.4MiB, graphlib 42.8MiB 였어요. graphlib 은 정점마다 정보 객체를 하나씩 만들어서 커요.

재귀 DFS 의 깊이 한계

기본 재귀 한도는 1000 이라서, 정점이 일렬로 이어진 체인에서는 길이 약 1,000 근처에서 RecursionError 가 났어요(호출한 쪽 프레임도 한도에 포함돼요). 파이썬 3.12 변경 사항 문서대로 재귀 한도는 이제 파이썬 코드에만 적용돼서, 한도를 10⁷ 로 올리면 메인 스레드에서도 체인 10만은 110ms, 100만은 1.24초에 끝났어요. 다만 sys.setrecursionlimit 문서는 한도가 너무 높으면 크래시가 날 수 있다고 적어요. 운영 코드라면 반복형으로 짜는 편이 안전해요.

visited 하나로 짠 사이클 검사, 실제로 얼마나 틀리나

방향 그래프에서 "이미 방문한 정점을 또 만나면 사이클"로 짠 코드는 사이클 없는 그래프에서도 사이클이라고 답해요. 다른 가지에서 이미 끝난 정점(검은색)으로 들어가는 간선 하나만 있어도 걸리기 때문이에요. 얼마나 자주인지 세 봤어요.

간선이 정점 수의 4분의 1뿐인 성긴 그래프도 97% 가 틀렸어요. 모든 정점에서 DFS 를 시작하는 바깥 루프가 있으니, 앞에서 끝난 정점을 뒤의 시작점이 가리키기만 해도 오답이 나요. 공통 라이브러리 하나를 두 모듈이 같이 쓰는 정상 의존성이 바로 이 모양이에요.

고치는 법은 상태를 셋으로 나누는 거예요. 들어갈 때 회색, 이웃을 다 본 뒤 검은색으로 칠하고, 회색으로 가는 간선만 사이클로 봐요. 나올 때 다시 흰색으로 되돌리면 답은 맞지만 같은 정점을 경로 수만큼 다시 돌아서 최악에는 지수 시간이 돼요.

순환 의존 오류가 났을 때 확인 순서, 체크리스트

운영에서 사이클 오류는 대부분 "설정을 누가 바꿨는데 어디가 고리인지 모르겠다"는 형태로 와요. 이때 Kahn 만 쓰면 남은 정점 목록이 고리보다 훨씬 넓게 나와요.

파이썬 graphlib 은 두 쪽을 다 줘요. graphlib 공식 문서에 따르면 prepare() 가 CycleError 를 던져도 get_ready() 로 처리 가능한 정점은 계속 꺼낼 수 있고, 고리는 예외의 args[1] 에 처음과 끝이 같은 목록으로 들어 있어요.

from graphlib import TopologicalSorter, CycleError

deps = {"web": {"api"}, "api": {"auth", "log"},
        "auth": {"user"}, "user": {"auth"}, "report": {"api"}}
ts = TopologicalSorter(deps)
try:
    ts.prepare()
except CycleError as e:
    print("cycle:", e.args[1])

done = []
while ready := ts.get_ready():
    done += ready
    ts.done(*ready)
nodes = set(deps) | {d for ds in deps.values() for d in ds}
print("processed:", done)
print("stuck:", sorted(nodes - set(done)))

cycle: ['auth', 'user', 'auth']
processed: ['log']
stuck: ['api', 'auth', 'report', 'user', 'web']

고리는 2개 정점인데 막힌 정점은 5개예요. 사용자에게 보여 줄 메시지는 고리 경로, 영향 범위 안내는 막힌 목록으로 나눠 쓰면 돼요. 문서는 고리가 여럿이면 그중 무엇이 보고될지 정해져 있지 않다고 적으니, 하나 고친 뒤 다시 돌려 남은 고리를 찾아요.

확인 순서는 이렇게 잡아요.

1. 간선 방향부터. "A 가 B 에 의존"을 A→B 로 그렸는지 B→A 로 그렸는지 코드 한 줄에 주석으로 적어요. graphlib 사전은 "키가 값들에 의존"이라 일반 인접 리스트와 방향이 반대예요.
2. 자기 간선. A 가 자기 자신을 의존 목록에 넣은 경우도 고리예요. 설정 파일 복사·붙여넣기에서 흔해요.
3. 고리 경로 하나를 출력. Kahn 의 남은 목록만 보고 찾지 말고 DFS 나 graphlib 으로 경로를 받아요.
4. 선택적 의존인지. 실행 시점에만 필요한 의존(지연 로딩, 런타임 조회)을 시작 순서 그래프에 넣어서 생긴 고리가 많아요. 그래프에서 빼거나 둘로 나눠요.
5. 도구가 주는 그림. 테라폼은 graph 명령 문서대로 -draw-cycles 로 고리 간선을 색칠해 줘요. 사례는 테라폼 parallelism·depends_on 판단표에 정리해 뒀어요.
6. 언어 차원의 금지. Go 는 언어 명세에 패키지가 자기 자신을 직접이든 간접이든 import 하면 안 된다고 적어서, 모듈 사이 고리는 빌드 단계에서 막혀요. 파이썬처럼 순환 import 를 허용하는 언어는 반쯤 초기화된 모듈 오류로 늦게 드러나요.

간선을 하나씩 추가할 때 사이클 검사 비용

워크플로 편집기나 작업 의존 설정 화면처럼 사용자가 간선을 하나씩 추가하고, 고리를 만드는 간선은 그 자리에서 거절해야 하는 경우가 있어요. 가장 쉬운 구현은 간선을 넣을 때마다 전체 위상 정렬을 다시 돌리는 건데, 간선 E 개를 넣으면 O(E·(V+E)) 가 돼요.

대신 간선 u→v 를 넣기 전에 v 에서 u 로 갈 수 있는지만 보면 돼요. 갈 수 있으면 새 간선이 고리를 닫고, 못 가면 안전해요.

def would_create_cycle(adj, u, v):
    stack, seen = [v], {v}
    while stack:
        x = stack.pop()
        if x == u:
            return True
        for y in adj[x]:
            if y not in seen:
                seen.add(y); stack.append(y)
    return False

무작위 DAG 의 간선을 섞은 순서로 하나씩 넣으며 두 방식을 비교했어요.

전체 재검사는 크기를 2배로 키울 때마다 약 4배씩 늘어 정점 4,000·간선 8,000 에서 30초였고, 도달 검사는 14ms 였어요. 다만 도달 검사도 최악은 간선마다 O(V+E) 예요. 무작위 그래프에서는 v 에서 닿는 범위가 좁아서 빨랐던 것이고, 긴 사슬 끝에 간선을 계속 붙이는 그래프라면 더 느려질 수 있어요. 간선이 수십만 개로 커지고 추가가 잦다면 증분 위상 순서를 유지하는 알고리즘을 따로 검토해요.

병렬 실행 단계 수와 작업자 수 계산

Kahn 으로 진입 차수 0인 정점을 한 번에 묶어 꺼내면 "동시에 돌릴 수 있는 작업 묶음"이 나와요. graphlib 의 get_ready()/done() 이 이 모양이에요. 정점 10만 DAG 는 이 방식으로 16단계였어요.

작업자를 늘리면 얼마나 빨라지는지는 두 값으로 정해져요. 전체 작업 시간 합 ÷ 작업자 수와 가장 긴 의존 사슬(임계 경로)의 시간 중 큰 값이 하한이에요. 작업 200개, 간선 400개, 작업마다 1~10초인 무작위 그래프로 계산했어요. 합은 1,106초, 임계 경로는 61초, 단계는 11개, 가장 넓은 단계는 56개였어요. 준비된 작업을 번호 순으로 빈 작업자에게 넘기는 단순한 방식으로 돌렸어요.

16명까지는 하한에 가깝게 줄고, 32명에서 임계 경로 61초에 닿은 뒤로는 작업자를 더 넣어도 안 줄어요. CI 러너나 배치 워커 수를 정할 때 이 계산을 먼저 해 보면 "작업자를 늘려도 안 빨라지는" 지점을 미리 알 수 있어요. 그 지점을 넘기려면 작업자가 아니라 임계 경로 위의 작업을 쪼개거나 의존을 끊어야 해요.

모든 사이클을 나열하면 안 되는 이유

"사이클을 전부 보여 주세요"라는 요구가 오면 개수부터 계산해 봐요. 정점 k 개가 서로 다 이어진 방향 그래프의 단순 사이클 수는 길이 j 마다 C(k, j)·(j−1)! 개라 합하면 아래처럼 늘어요.

정점 12개만 촘촘히 엮여도 1억 개가 넘어요. 고리 정보를 사용자에게 줄 때는 "고리 하나의 경로" 또는 "고리에 엮인 정점 묶음(강연결 성분)"으로 제한하는 게 맞아요. 강연결 성분은 O(V+E) 로 끝나고, 크기가 2 이상인 성분(또는 자기 간선 정점)이 곧 고칠 대상 목록이에요.

도입 전에 따질 것

• 그래프 크기와 호출 빈도. 정점 수천 개를 하루 몇 번 정렬한다면 graphlib 처럼 검증된 라이브러리가 가장 싸요. 요청마다 수만 개라면 직접 짠 Kahn 이 8배쯤 빨랐어요.
• 순서의 재현성. 같은 입력에 같은 순서가 나와야 로그 비교와 캐시가 쉬워요. 문서상 graphlib 은 같은 단계 안의 순서를 삽입 순서로 정해요. 입력을 만드는 쪽이 매번 같은 순서인지 확인하고, 아니면 준비 목록을 정렬해요.
• 사이클일 때의 정책. 전부 멈출지, 고리와 상관없는 작업은 먼저 돌릴지 정해요. 후자라면 graphlib 처럼 고리 보고 뒤에도 꺼낼 수 있는 구조가 필요해요.
• 변경 방식. 그래프가 한 번 만들어지고 끝나는지, 간선이 계속 추가되는지에 따라 위의 도달 검사 같은 증분 방식이 필요해요.

자주 묻는 질문

위상 정렬은 Kahn 과 DFS 중 무엇이 빠른가요?

둘 다 O(V+E) 이고 정점 10만·간선 20만에서 Kahn 205ms, 반복형 DFS 209ms 로 거의 같았어요. 속도보다 필요한 결과로 골라요. 병렬 단계가 필요하면 Kahn, 고리 경로를 보여 줘야 하면 DFS 예요.

방문 배열 하나로 사이클을 검사하면 왜 틀리나요?

이미 끝난 정점(다른 가지)으로 들어가는 간선도 사이클로 보기 때문이에요. 사이클 없는 정점 20·간선 10 무작위 그래프 1만 개 중 9,999개를 사이클이라고 답했어요. 흰·회·검 세 상태로 나누고 회색으로 가는 간선만 사이클로 봐요.

graphlib TopologicalSorter 를 운영 코드에 써도 되나요?

정점 수천 개 이하라면 충분히 빠르고, 고리 경로와 처리 가능한 정점을 함께 줘서 편해요. 정점 10만에서는 직접 짠 Kahn 보다 약 8배 느렸으니, 큰 그래프를 자주 정렬한다면 직접 짜요.

Kahn 에서 남은 정점이 전부 사이클인가요?

아니에요. 고리 뒤에서 고리를 기다리는 정점도 남아요. 예시에서 고리는 2개였는데 남은 정점은 5개였어요. 원인을 찾으려면 DFS 나 graphlib 의 CycleError 로 고리 경로를 따로 받아요.

간선을 추가할 때마다 사이클을 검사하면 너무 느려요.

매번 전체 정렬을 다시 돌리고 있을 가능성이 커요. 간선 u→v 를 넣기 전에 v 에서 u 로 갈 수 있는지만 보면 돼요. 정점 4,000·간선 8,000 에서 전체 재검사 30초가 14ms 로 줄었어요.

작업자를 늘려도 빌드가 더 안 빨라져요.

가장 긴 의존 사슬(임계 경로) 시간에 닿았을 가능성이 커요. 작업 200개 예시에서 32명부터 61초로 고정됐어요. 임계 경로 위 작업을 쪼개거나 불필요한 의존을 끊어야 줄어요.

정리

• Kahn 과 3색 DFS 는 속도가 비슷해요. 병렬 단계·사전순이 필요하면 Kahn, 고리 경로가 필요하면 DFS 로 고르고, 운영에서는 둘을 같이 쓰는 경우가 많아요.
• visited 하나짜리 사이클 검사는 정상 그래프 대부분을 사이클로 봐요. 회색으로 가는 간선만 사이클이에요.
• 사이클 오류는 방향 → 자기 간선 → 고리 경로 → 선택적 의존 순서로 확인하고, Kahn 의 남은 목록은 영향 범위로만 써요.
• 간선 추가 시 검사는 도달 검사로, 작업자 수는 합 ÷ 작업자와 임계 경로 중 큰 값으로 계산해요.
• 그래프 탐색에서 BFS·DFS 를 고르는 기준과 재귀 깊이 측정은 BFS DFS 언제 쓰나, 가중치가 0과 1뿐인 최단 경로는 0-1 BFS 언제 쓰나에서 이어서 볼 수 있어요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 DFS 3색 사이클 탐지 원리 — 역방향 간선과 위상 정렬에서 도식과 코드로 단계별로 풀었어요.