Algorithm Guidecomplexity: O(V+E)

위상 정렬 (Topological Sort)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Topological Sort

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

Logic Node1 / 8

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

02 Understand It Simply

For Everyone

🔑Analogy

수강신청처럼 선수 과목을 먼저 듣도록 순서를 정하는 것.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 위상 정렬 (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