Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке топологічне сортування в графах?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Топологічне сортування** - це лінійний порядок вершин орієнтованого ациклічного графа (DAG), у якому для кожного ребра u→v вершина u йде раніше за вершину v. Воно існує лише для графів без циклів і зазвичай будується за O(V+E) за допомогою алгоритму Кана (через вхідні степені) або обходу в глибину (DFS). **Ключове:** порядок може бути не єдиним - за наявності «незалежних» вершин допустимі різні коректні послідовності.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Топологічне сортування - це лінійний порядок вершин орієнтованого ациклічного графа (DAG), у якому для кожного ребра u→v вершина u йде раніше за вершину v. Воно існує лише для графів без циклів і зазвичай будується за O(V+E) за допомогою алгоритму Кана (через вхідні степені) або обходу в глибину (DFS). ## Детальний розбір ### Визначення Топологічне сортування задає лінійне впорядкування всіх вершин орієнтованого ациклічного графа так, щоб кожне обмеження-залежність (ребро u→v) дотримувалося: u стоїть перед v. Порядок може бути не єдиним - за наявності «незалежних» вершин допустимі різні коректні послідовності. ### Коли застосовна - Лише для орієнтованих ациклічних графів (DAG). Якщо є цикл - коректного порядку не існує. - Для виявлення циклу: в алгоритмі Кана - якщо після обробки залишилися вершини з ненульовою вхідною степінню; у DFS - виявлення зворотного ребра (вершини на стеку/сірого кольору). ### Ключові властивості - Коректність: для кожного ребра u→v вершина u розташована раніше за v. - Існування: можливе лише для DAG; наявність циклу робить сортування неможливим. - Неєдиність: може бути багато валідних порядків. Єдиність досягається, якщо на кожному кроці алгоритму Кана вибір вершини однозначний (у черзі завжди рівно 1 вершина з нульовою вхідною степінню). Еквівалентно: у графі фактично задано «майже повний» порядок залежностей (є гамільтонів шлях). - Складність: обидва класичні алгоритми працюють за O(V+E) за часом і O(V+E) за пам'яттю. ### Алгоритми 1. Алгоритм Кана (через вхідні степені): - Порахувати вхідну степінь кожної вершини. - Покласти в чергу всі вершини з нульовою вхідною степінню. - Поки черга не порожня: видалити вершину, додати у відповідь, «видалити» її ребра, зменшуючи вхідну степінь сусідів; ті, що з'явилися з нульовою степінню, - у чергу. - Якщо оброблено менше вершин, ніж є в графі - є цикл. 2. DFS-підхід (зворотний постпорядок): - Запустити DFS; перед виходом з вершини додавати її до списку. - Після обходу всіх компонентів графа розвернути список - це і є топологічний порядок. - Виявлення циклу: потрапляння в «сіру» вершину (на стеку рекурсії) означає цикл. ### Приклад графа і коректних порядків Нехай вершини: 0,1,2,3,4. Ребра: 0→2, 1→2, 1→3, 3→4. Коректні топологічні порядки включають, наприклад: [1,0,3,4,2], [0,1,3,4,2], [1,3,4,0,2]. Зауважте, що 0 і 1 незалежні одна від одної і можуть йти в будь-якому порядку до 2. ### Код: алгоритм Кана (JavaScript) ``` /* n - кількість вершин (0..n-1) edges - масив пар [u, v] для ребер u→v Повертає { order, unique } або кидає помилку за наявності циклу */ function topoSortKahn(n, edges) { const adj = Array.from({ length: n }, () => []); const indeg = Array(n).fill(0); for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; } const queue = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i); const order = []; let unique = true; // буде хибним, якщо на якомусь кроці є вибір із >1 вершини while (queue.length) { if (queue.length > 1) unique = false; // Можна відсортувати queue для детермінізму, але це змінює лише вигляд порядку, не коректність const u = queue.shift(); order.push(u); for (const v of adj[u]) { indeg[v]--; if (indeg[v] === 0) queue.push(v); } } if (order.length !== n) { throw new Error("Граф містить цикл: топологічне сортування неможливе"); } return { order, unique }; } // Приклад використання: const n = 5; const edges = [ [0,2], [1,2], [1,3], [3,4] ]; const result = topoSortKahn(n, edges); console.log(result.order); // Наприклад: [1,0,3,4,2] console.log(result.unique); // false - на кроках був вибір ``` ### Код: реалізація DFS (Python) ``` from typing import List, Tuple # n - кількість вершин (0..n-1) # edges - список ребер (u, v) для u→v # Повертає список вершин у топологічному порядку def topo_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> List[int]: adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) WHITE, GRAY, BLACK = 0, 1, 2 color = [WHITE] * n order = [] def dfs(u: int): color[u] = GRAY for v in adj[u]: if color[v] == GRAY: raise ValueError("Граф містить цикл: топологічне сортування неможливе") if color[v] == WHITE: dfs(v) color[u] = BLACK order.append(u) # зворотний постпорядок for u in range(n): if color[u] == WHITE: dfs(u) order.reverse() return order # Приклад використання n = 5 edges = [(0, 2), (1, 2), (1, 3), (3, 4)] print(topo_sort_dfs(n, edges)) # Наприклад: [1, 0, 3, 4, 2] ``` ### Перевірка унікальності порядку Під час алгоритму Кана стежте за розміром черги: якщо коли-небудь у ній більше однієї вершини з нульовою вхідною степінню, єдиності немає. Якщо на кожному кроці рівно одна вершина - порядок єдиний. ### Застосування - Планування завдань із залежностями (CI/CD пайплайни, оркестрація кроків). - Збирання проєктів і системи модулів (визначення порядку компіляції/лінкування). - Розв'язання залежностей пакетів, завантаження модулів/міграцій БД у правильному порядку. - Курси з передумовами; обчислення порядку проходження. ### Часті помилки - Застосування до графа з циклами - потрібно або видаляти цикл, або сигналізувати про помилку. - У DFS додають вершину до обходу дітей - правильно додавати після обходу (постпорядок) і потім розвертати. - Забувають обробляти ізольовані вершини (без ребер) - вони повинні бути присутні в порядку. - Неправильна інтерпретація напрямку ребра (міняють місцями залежність і залежний вузол). - Очікування єдиного результату там, де граф допускає кілька коректних порядків. ### Складність І алгоритм Кана, і DFS-варіант працюють за O(V+E) за часом; за пам'яттю зберігають граф і додаткові структури (вхідні степені/кольори, чергу/стек), що також укладається в O(V+E).Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.