Oh My Algorithm
Algorithm Guidecomplexity: O(V+E)

위상 정렬 (Topological Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
Topological Sort
Ain=0Bin=0Cin=2Din=1Ein=1Fin=2

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

Logic Node1 / 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

04 자주 묻는 질문

FAQ
위상 정렬 (Topological Sort)란 무엇인가요?+

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

위상 정렬 (Topological Sort)의 시간복잡도는 어떻게 되나요?+

위상 정렬 (Topological Sort)의 시간복잡도는 O(V+E) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

위상 정렬 (Topological Sort)은(는) 어디에 사용하나요?+

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

위상 정렬 (Topological Sort)를 쉽게 비유하면?+

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

→ 그래프 전체 보기Related
🕸다익스트라 (Dijkstra)
O(E log V)
🕸벨만-포드 (Bellman-Ford)
O(V·E)
🕸크루스칼 (Kruskal MST)
O(E log E)
🕸프림 (Prim MST)
O(E log V)