Подробно объясни алгоритм Кана

Кан — один из самых известных алгоритмов топологической сортировки графа и детекции цикла в ориентированном графе. Он работает по принципу устранения вершин с нулевой степенью входа и последующего уменьшения степеней входа соседних вершин. Что такое топологическая сортировка - Это линейное упорядочение вершин графа так, чтобы для любой дуги u -> v вершина u стояла перед вершиной v. - Такая сортировка возможна только для DAG (ориентованных ациклических графов). Основная идея Кан-алгоритма - Считаем для каждой вершины в графе ее in-degree (количество входящих дуг). - Помещаем все вершины с in-degree 0 в очередь. - Повторяем: вынимаем вершину u из очереди, добавляем её в результат, удаляем все исходящие из нее дуги (уменьшаем in-degree соседей). Если чья-то in-degree становится нулём, добавляем её в очередь. - Если удалось обработать все вершины — получаем топологическую сортировку. Если нет — в графе есть цикл. Данные структуры - Граф представлен как adjacency list: для каждой вершины u список её соседей (v), к которым есть дуга u -> v. - Массив in_degree[v] = количество входящих дуг в вершину v. - Очередь (FIFO) или deque для вершин с in-degree 0. - Результат: список или массив идущих вершин в топологическом порядке. Пошаговый алгоритм (псевдокод) - Пусть граф задан как G = (V, E), n = |V|. 1) for v в V: in_degree[v] = 0 2) for u в V: for v в G[u]: in_degree[v] += 1 3) queue = { v | in_degree[v] == 0 } 4) order = [] 5) while queue не пуст: u = pop(queue) order.append(u) for v в G[u]: in_degree[v] -= 1 if in_degree[v] == 0: push(queue, v) 6) если длина order != n: вернуть "граф содержит цикл" иначе вернуть order как топологическую сортировку Корректность и инварианты - Инвариант: на любой момент времени в очереди находятся вершины с текущим in-degree 0 относительно оставшегося графа. - Доказательство корректности: после обработки вершины u все её исходящие дуги “удалены” (уменьшаем in-degree потомков). Любая вершина v, для которой существует дуга u -> v, не может находиться раньше u в топологическом порядке, и когда in-degree[v] достигает 0, это означает, что все предшественники v уже добавлены в order. Поэтому добавление u перед всеми его потомками соблюдает топологическую зависимость. Повторение по всем вершинам приводит к полной сортировке при отсутствии цикла. Если цикл есть, ни одна вершина цикла не достигнет in-degree 0, и длина order окажется меньше n. Сложность - Временная: O(n + m), где n — число вершин, m — число дуг. Каждая дуга рассматривается ровно один раз. - Пространственная: O(n + m) на хранение графа, in-degree и очереди. Особенности и вариации - Детекция цикла: если после алгоритма длина order меньше числа вершин, цикл присутствует. Это даёт детектор цикла в графе. - Лексикографически наименьшая топологическая сортировка: вместо обычной очереди можно использовать минимальную кучу (priority queue). Тогда на каждом шаге выбирается вершина с нулевым in-degree, которая имеет минимальный идентификатор/имя. - Несколько дуг и петли: в наш in-degree учитываются все входящие дуги, включая дубликаты. Самая петля (self-loop) создаёт цикл и помешает получить полную сортировку. - Вариации на тему: можно сохранить копию in-degree, чтобы использовать алгоритм повторно с теми же данными, или реализовать алгоритм на основе списков соседей, если граф представлен в другой структуре. Сравнение с DFS-основанной топологической сортировкой - Кан требовает меньшего риска переписать структуру графа; работает пошагово и естественно detect cycle через отсутствие вершин с in-degree 0. - DFS-основанный подход: выполнить DFS по всем вершинам, записывая вершины по выходу из DFS; перевернуть полученный порядок. Также можно детектировать цикл с помощью отслеживания текущего стека рекурсии. - Оба метода дают корректную топологическую сортировку для DAG; Кан более явный по детекции цикла через in-degree. Пример (маленький граф) - Вершины: A, B, C, D, E - Рёбра: A -> B, A -> C, B -> D, C -> D, E -> B - in-degree: A:0, B:2 (A,E), C:1 (A), D:2 (B,C), E:0 - queue инициализируется A и E - Обработка: - Вытаскиваем A → order: [A]; уменьшаем indeg(B)=1, indeg(C)=0 → добавляем C - Вытаскиваем E → order: [A, E]; indeg(B)=0 → добавляем B - Вытаскиваем C → order: [A, E, C]; indeg(D)=1 - Вытаскиваем B → order: [A, E, C, B]; indeg(D)=0 → добавляем D - Вытаскиваем D → order: [A, E, C, B, D] - Результат: любая корректная топологическая сортировка, например A, E, C, B, D или A, E, B, C, D. Когда применяют - Планирование задач с зависимостями, сборка проектов, курс-предметы с prerequisite, анализ зависимостей в компиляции, параллелизация задач и т.д. Если хочешь, могу привести другой конкретный пример с различной структурой графа и показать шаги по Кан-алгоритму детально, или привести код на каком-нибудь языке (Python, C++, Java) — просто скажи, какой формат предпочтительнее.