Топологическая сортировка: Кан и DFS

Интерактивный разбор: https://grundyjs.ru/algorithms/topological-sort/?utm_source=rutube&utm_medium=social&utm_campaign=topological_sort&utm_content=horizontal В каком порядке выполнять задачи с зависимостями? Топологическая сортировка располагает все вершины так, чтобы для каждого направленного ребра его начало стояло раньше конца. Сравниваем алгоритм Кана и поиск в глубину (DFS) на одном графе. Кан считает входящие рёбра и хранит готовые вершины в FIFO-очереди. После A вершина C ещё ждёт B; когда степень становится нулевой, добавляем вершину в конец очереди. DFS хранит текущий путь в стеке, записывает вершины после проверки исходящих рёбер и разворачивает полный порядок выхода. В примере без цикла Кан получает A, B, C, D, E, F, а DFS — B, D, A, C, E, F. Оба ответа соблюдают все зависимости. В другом примере Кан выдаёт только A, затем очередь пустеет. DFS находит конкретный цикл B → C → D → B. Вершины E и F тоже заблокированы, но в этот цикл не входят. При цикле полного топологического порядка нет. В интерактивном разборе можно выбирать готовые графы или менять зависимости, проходить шаги, сравнивать состояния, делиться ссылкой и сохранять анимацию. Такты анимации и счётчики рёбер не являются сравнением времени работы алгоритмов. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно. #алгоритмы #топологическаясортировка #DFS #графы #программирование