Motivation

Топологический порядок существует только тогда, когда в графе нет циклов. Мы строим его с помощью алгоритма Кана, который многократно удаляет вершину, не имеющую оставшихся входящих ребер.

Зачем изучать топологическую сортировку?

• Упорядочивание с ограничениями: системы сборки, планирование задач, предварительные условия курсов и пересчет электронных таблиц — все это опирается на нее.
• Обнаружение циклов: если вы не можете упорядочить каждую вершину, значит, граф содержит цикл.
• Основа для алгоритмов на DAG: кратчайшие и длиннейшие пути в DAG (направленном ациклическом графе) вычисляются в топологическом порядке.

Может существовать множество допустимых порядков. Чтобы получить один предсказуемый ответ, мы всегда удаляем вершину с наименьшим номером, чья полустепень захода (in-degree) равна 0.