Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке топологічне сортування? Для яких графів воно можливе?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Топологічне сортування** - це впорядкування вершин **орієнтованого графа**, при якому кожне ребро йде тільки від більш ранньої вершини до пізнішої. **Ключове:** топологічне сортування можливе тільки для ациклічних орієнтованих графів (DAG).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Топологічне сортування** - це впорядкування вершин **орієнтованого графа**, при якому **кожне ребро йде тільки від більш ранньої вершини до пізнішої**. Іншими словами: Якщо є ребро **u → v**, то в порядку топологічного сортування **u стоїть раніше v**. --- ### Коли можливе Топологічне сортування можливе **тільки для ациклічних орієнтованих графів (DAG - Directed Acyclic Graph)**. Якщо в графі є **цикл**, впорядкувати вершини так, щоб не порушити напрямок ребер, **неможливо**. --- ### Приклад Нехай граф показує залежності між задачами: ```javascript A → B → C A → D ``` Один з можливих порядків: **A, D, B, C** (Спочатку A, тому що від неї залежать інші.) --- ### Як це працює (ідея) 1. Знайти вершини **без вхідних ребер**, вони можуть йти першими. 2. Видалити їх з графа разом із вихідними ребрами. 3. Повторювати, поки не видалені всі вершини. (Так працює, наприклад, **алгоритм Кана** або **DFS-сортування**.) --- ### Застосування - Планування задач із залежностями (наприклад, компіляція коду). - Визначення порядку виконання кроків (будівництво, проєкти). - Аналіз залежностей модулів, курсів, подій. --- **Підсумок:** Топологічне сортування - це **лінійний порядок вершин DAG-графа**, що відображає залежність: «якщо A веде до B, то A повинна стояти перед B».Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.