Топологічне сортування — це лінійне впорядкування вершин орієнтованого ациклічного графа таке, що для кожного орієнтованого ребра з u до v вершина u стоїть перед v у цьому порядку. Це порядок, у якому можна виконувати завдання, коли одні завдання мають завершитися раніше за інші. Граф може мати багато коректних топологічних порядків або жодного, якщо містить цикл.

Алгоритм Кана спершу обчислює напівстепінь заходу кожної вершини, а потім додає всі вершини з нульовим напівстепенем до черги. Він повторно вилучає вершину з черги, додає її до вихідного порядку та зменшує напівстепінь заходу кожного з її наступників. Будь-який наступник, чий напівстепінь падає до нуля, додається до черги, і процес повторюється, доки черга не спорожніє.

Напівстепінь заходу вершини — це кількість ребер, що вказують у неї, тобто кількість її прямих попередників. Вершина з нульовим напівстепенем заходу не має невиконаних залежностей і тому готова бути поставленою наступною в порядку. Алгоритм Кана повністю керується відстеженням того, як напівстепені заходу падають до нуля під час вилучення вершин.

Цикл означає, що група вершин залежить одна від одної прямо або опосередковано, тож жоден член циклу ніколи не може бути першим. За наявності циклу кожна вершина в ньому назавжди зберігає додатний напівстепінь заходу і ніколи не потрапляє до черги. Саме тому топологічний порядок існує лише для орієнтованого ациклічного графа (DAG).

Вона використовує властивість алгоритму Кана: якщо алгоритм завершується, а кількість поставлених у порядок вершин менша за загальну кількість вершин, то решта вершин обов'язково лежить на циклі. Симуляція дозволяє додати зворотне ребро, що створює цикл, і потім повідомляє, що топологічний порядок не існує, бо лічильник не досяг повного значення.

Ні. Щоразу, коли дві або більше вершин одночасно мають нульовий напівстепінь заходу, ви можете обрати наступною будь-яку з них, і кожен вибір може привести до іншого коректного порядку. Кількість різних топологічних порядків залежить від структури графа: повністю ланцюговий граф має рівно один, а граф без ребер допускає будь-яку перестановку.

Алгоритм Кана працює за час O(V + E), де V — кількість вершин, а E — кількість ребер. Кожну вершину один раз додають до черги і один раз вилучають, а кожне ребро переглядають один раз під час вилучення його джерела. Саме ця лінійна продуктивність робить топологічне сортування добре масштабованим на дуже великі графи залежностей.

Інструменти збірки на кшталт Make, Bazel і менеджерів пакетів моделюють файли або пакети як вершини, а їхні залежності як ребра, після чого топологічно сортують цей граф, щоб визначити безпечний порядок компіляції чи встановлення. Збирання цілі лише після того, як зібрані всі її залежності, — це саме та гарантія, яку дає топологічний порядок. Якщо граф залежностей містить цикл, інструмент збірки повідомляє про помилку, а не зациклюється назавжди.

Складання розкладу курсів із передумовами, перерахунок клітинок у таблицях, планування завдань і проєктів, планування інструкцій у компіляторах та розв'язання залежностей символів у компонувальниках — усе це спирається на топологічний порядок. Будь-яка ситуація, де одні елементи мають передувати іншим, є кандидатом. Це також перший крок в алгоритмах пошуку найдовшого чи найкоротшого шляху в DAG.

Алгоритм Кана є ітеративним і працює вперед, повторно вилучаючи вершини з нульовим напівстепенем заходу за допомогою черги. Підхід на основі пошуку в глибину натомість рекурсивно спускається спершу до найглибших нащадків і додає кожну завершену вершину на початок порядку, утворюючи обернений порядок часу завершення. Обидва працюють за час O(V + E) і обидва вміють виявляти цикли, але алгоритм Кана робить поняття готових до обробки залежностей більш явним.