위상 정렬을 적용하려면 그래프가 어떤 조건을 만족해야 하는가?

방향성이 있고 순환하지 않는 그래프(DAG) 조건을 만족해야 한다.

순환이 존재하면 시작점을 찾지 못해 정렬을 시작할 수 없다. 진입 차수가 0인 노드가 반드시 하나 이상 존재해야 정렬을 시작한다. 모든 노드가 서로를 향하는 순환 고리가 있으면 진입 차수가 모두 1 이상이 된다.

위상 정렬은 진입 차수 배열을 쓰는 칸 알고리즘이나 DFS로 구현한다. 칸 알고리즘은 진입 차수가 0인 노드를 큐에 넣으며 탐색한다. 노드를 방문할 때마다 연결된 간선을 지우고 새로 진입 차수가 0이 된 노드를 큐에 추가한다.

모든 노드를 방문하기 전에 큐가 비면 그래프에 순환이 있다고 판단한다. 이 방식으로 작업 간의 충돌이나 교착 상태를 미리 감지한다.