UK 
EnglishТипова
Polski🔀 Топологічне сортування — впорядкування DAG
Упорядкуйте вершини орієнтованого ациклічного графа так, щоб кожне ребро вказувало вперед. Дивіться, як алгоритм Кана знімає вузли з нульовим входом — планування за системами збірки та передумовами курсів.
Про цю симуляцію
Ця симуляція будує випадковий орієнтований ациклічний граф (DAG) — мережу односторонніх зв'язків без петель, — проводячи ребра лише від вузла з меншим індексом до вузла з більшим індексом, що математично гарантує відсутність циклів у початковому графі. Потім вона анімує алгоритм Кана: обчислює вхідний ступінь (indegree) кожного вузла (кількість вхідних ребер), поміщає всі вузли з нульовим вхідним ступенем у чергу і повторно видаляє з черги один вузол, додає його до зростаючого топологічного порядку та зменшує вхідний ступінь його наступників, додаючи в чергу ті, що досягли нуля. Повзунок «Вузли» (4–9) задає розмір графа, а повзунок «Швидкість» керує темпом відтворення кроків у режимі «Відтворити».
🔬 Що показано
Кожен вузол показує позначку «in:» із поточним вхідним ступенем. Зелене кільце позначає вузол із нульовим вхідним ступенем, що перебуває в черзі й готовий бути розміщеним; суцільний фіолетовий — вузол, щойно видалений на цьому кроці; тьмяний фіолетовий — вже розміщені вузли; сірі вузли ще мають невиконані залежності. Ребра тьмяніють, щойно їхній вихідний вузол видаляється, а зростаючий топологічний порядок з'являється у вигляді нумерованого списку поруч із полотном.
🎮 Як користуватись
Перетягніть повзунок «Вузли N» (4–9), щоб змінити розмір графа, і натисніть «Регенерувати», щоб намалювати новий випадковий DAG. Натисніть «Відтворити», щоб автоматично запустити алгоритм Кана (у темпі повзунка «Швидкість»), або «Крок», щоб виконати рівно одну операцію видалення з черги та зменшення. «Додати ребро» вставляє одне додаткове випадкове ребро — зазвичай пряме ребро, яке зберігає DAG коректним, але іноді зворотне ребро, яке створює цикл, щоб ви побачили, як симуляція його виявляє.
💡 Чи знали ви?
Алгоритм Кана був опублікований Артуром Б. Каном 1962 року в статті «Topological sorting of large networks» і працює за час O(V + E). Реальні інструменти збірки, такі як Make і Bazel, використовують саме цю ідею — розглядаючи файли чи пакети як вузли, а залежності як ребра, — щоб визначити безпечний порядок компіляції та негайно повідомити про помилку, щойно виявлять циклічну залежність.
Часті питання
Як симуляція гарантує, що початковий граф не має циклів?
Кожному вузлу присвоюється фіксований індекс від 0 до N−1, а можливі ребра додаються лише від меншого індексу до більшого (від i до j лише коли i < j). Оскільки за такої індексації ребро ніколи не може вказувати назад, проходження будь-яким ланцюгом ребер завжди збільшує індекс, тож неможливо повернутися до вузла, з якого почали — граф є ациклічним за побудовою ще до запуску алгоритму Кана.
Що означають кольори вузлів і позначка «in:»?
Позначка «in:» показує поточний вхідний ступінь вузла — кількість ребер, які досі вказують на нього. Зелене кільце означає нульовий вхідний ступінь — вузол не має невиконаних залежностей і перебуває в черзі, готовий до розміщення. Суцільний фіолетовий позначає вузол, щойно видалений на цьому кроці, тьмяний фіолетовий — вузли, розміщені на попередніх кроках, а звичайні сірі вузли ще мають принаймні одну невиконану залежність.
Що відбувається, коли я натискаю «Додати ребро»?
«Додати ребро» вставляє одне нове випадкове ребро й перезапускає алгоритм із нуля. Приблизно у 60% випадків обирається пряме ребро (від меншого індексу до більшого), яке зберігає граф коректним DAG. В решті випадків, або коли додати пряме ребро вже неможливо, обирається зворотне ребро, яке створює цикл, щоб ви побачили, як спрацьовує виявлення циклів у симуляції.
Як симуляція виявляє й повідомляє про цикл?
Вона виконує алгоритм Кана до завершення, видаляючи з черги й розміщуючи вузли, поки черга не спорожніє. Якщо всі вузли розміщено, сортування успішне. Якщо черга спорожніє раніше, а вузли залишаються нерозміщеними, ці вузли обов'язково лежать на циклі, оскільки вхідний ступінь циклу ніколи не може стати нулем, і симуляція перелічує їх під написом «Цикл серед» із червоним банером на полотні.
У чому різниця між кнопками «Крок», «Відтворити» та «Регенерувати»?
«Крок» виконує рівно одну ітерацію алгоритму Кана: видаляє з черги один вузол із нульовим вхідним ступенем, додає його до порядку та зменшує вхідний ступінь його наступників. «Відтворити» повторює той самий крок автоматично, приблизно кожні 28 кадрів анімації, поділені на значення повзунка «Швидкість», поки черга не спорожніє. «Регенерувати» відкидає поточний граф і малює абсолютно новий випадковий DAG із поточним значенням «Вузли N», скидаючи стан алгоритму.