Algorithm Guidecomplexity: O(V+E)

위상 정렬 (Topological Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

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 쉽게 이해하기

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

Guide Progress0%