위상 정렬 (Topological Sort)

위상 정렬 (Topological Sort)

방향 비순환 그래프(DAG)에서 간선 방향을 거스르지 않도록 정점을 선형으로 나열하는 알고리즘

목적: 의존성 순서, 작업 스케줄링, 선행 조건

특징: DAG만 가능, 여러 해 가능, 선형 순서

조건: 방향 비순환 그래프(DAG), 사이클 있으면 불가능

구현 방법

• •DFS 기반: 후위 순회 후 역순
• •Kahn 알고리즘: 진입 차수(in-degree) 0인 정점부터 제거

시간 복잡도: O(V + E)

공간 복잡도: O(V)

장점: 의존성 순서 보장, 선형 시간, 여러 해

단점: DAG만 가능, 사이클 탐지 필요

적용사례: 빌드 시스템(make), 패키지 의존성, 과목 선수 조건, 작업 스케줄링, 컴파일 순서

비교: DFS 기반(후위/역순) vs Kahn(진입차수/큐)

연관: DAG, DFS, 사이클 검사, 의존성, 스케줄링