Motivation

위상 정렬(topological order)은 그래프에 사이클이 없을 때만 존재합니다. 우리는 진입 차수(incoming edges)가 없는 정점을 반복적으로 제거하는 Kahn의 알고리즘(Kahn's algorithm)을 사용하여 이를 구축합니다.

왜 위상 정렬을 배워야 할까요?

• 제약 조건이 있는 정렬: 빌드 시스템, 작업 스케줄링, 선수 과목, 그리고 스프레드시트 재계산 등이 모두 이에 의존합니다.
• 사이클 감지: 모든 정점을 정렬할 수 없다면 그래프에 사이클이 포함되어 있는 것입니다.
• DAG 알고리즘의 기초: DAG에서의 최단 경로 및 최장 경로는 위상 순서대로 계산됩니다.

여러 개의 유효한 순서가 존재할 수 있습니다. 예측 가능한 하나의 결과를 얻기 위해, 우리는 항상 진입 차수(in-degree)가 0인 정점 중 번호가 가장 작은 정점을 제거합니다.