Що таке топологічне сортування? Для яких графів воно можливе?

Топологічне сортування - це впорядкування вершин орієнтованого графа, при якому кожне ребро йде тільки від більш ранньої вершини до пізнішої.

Іншими словами: Якщо є ребро u → v, то в порядку топологічного сортування u стоїть раніше v.

---

#Коли можливе

Топологічне сортування можливе тільки для ациклічних орієнтованих графів (DAG - Directed Acyclic Graph). Якщо в графі є цикл, впорядкувати вершини так, щоб не порушити напрямок ребер, неможливо.

---

#Приклад

Нехай граф показує залежності між задачами:

Один з можливих порядків: A, D, B, C (Спочатку A, тому що від неї залежать інші.)

---

#Як це працює (ідея)

1. Знайти вершини без вхідних ребер, вони можуть йти першими.
2. Видалити їх з графа разом із вихідними ребрами.
3. Повторювати, поки не видалені всі вершини.

(Так працює, наприклад, алгоритм Кана або DFS-сортування.)

---

#Застосування

• Планування задач із залежностями (наприклад, компіляція коду).
• Визначення порядку виконання кроків (будівництво, проєкти).
• Аналіз залежностей модулів, курсів, подій.

---

Підсумок: Топологічне сортування - це лінійний порядок вершин DAG-графа, що відображає залежність: «якщо A веде до B, то A повинна стояти перед B».