Algorithm Guidecomplexity: O(V+E)

위상 정렬 (Topological Sort)

방향 비순환 그래프(DAG)에서 모든 간선이 앞에서 뒤로만 향하도록 정점을 일렬로 나열합니다. Kahn 알고리즘은 진입차수(indegree)가 0인 노드를 큐로 관리하며 차례로 출력해, 작업 스케줄링·의존성 해소·빌드 순서 결정의 기반이 됩니다.

01위상 정렬 (Topological Sort)

알고리즘 작동 원리 탐색

위상 정렬을 시작합니다. 각 노드의 진입차수(indegree)를 세고, 진입차수가 0인 A·B를 준비 큐에 넣습니다.

큐에서 A를 꺼내 순서에 추가합니다. A→C 간선을 제거해 C의 진입차수를 2에서 1로 줄입니다.

B를 꺼내 순서에 추가합니다. B→C로 C의 진입차수가 0이 되어 C를 큐에 넣습니다.

C를 꺼냅니다. C→D, C→E로 D와 E의 진입차수가 각각 0이 되어 둘 다 큐에 들어갑니다.

D를 꺼냅니다. D→F로 F의 진입차수를 2에서 1로 줄이지만, 아직 0이 아니라 큐에 넣지 않습니다.

E를 꺼냅니다. E→F로 F의 진입차수가 0이 되어 마지막으로 F를 큐에 넣습니다.

F를 꺼내 순서에 추가합니다. 큐가 비어 모든 노드가 위상 순서로 나열됐습니다.

완료 · 위상 순서 A → B → C → D → E → F. 모든 간선이 앞에서 뒤로만 향하는 유효한 정렬입니다.

Live Python

1from collections import deque

2def topo_sort(graph, indeg):

# indeg==0 → queue: A, B

3 q = deque(v for v in graph if indeg[v] == 0)

4 order = []

5 while q:

6 u = q.popleft()

7 order.append(u)

8 for v in graph[u]:

9 indeg[v] -= 1

10 if indeg[v] == 0:

11 q.append(v)

12 return order

1 / 8

02 쉽게 이해하기

For Everyone

🔑핵심 동작

의존 관계가 있는 작업을 선행 작업이 항상 먼저 오도록 한 줄로 세웁니다. 사이클이 있으면 그런 순서가 존재하지 않습니다.

💡쉽게 말하면

방향 그래프에서 '먼저 와야 하는 것'을 앞에 두도록 정점을 일렬로 세웁니다.

진입차수 0인 것부터 차례로 빼내요.

📍어디에 쓰나

–작업 스케줄링
–빌드 의존성
–강의 선수 관계

03 파이썬 구현 코드

위상 정렬 (Topological Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

from collections import deque

def topo_sort(graph, indeg):
    q = deque(v for v in graph if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order