Топологическая сортировка (алгоритм Кана)

Топологическая сортировка (алгоритм Кана): как это работает?

Посчитайте, сколько рёбер входит в каждую вершину. Это число называют входящей степенью.

Положите в очередь все вершины с нулевой входящей степенью. Они никому не должны и идут первыми.

Достаньте вершину и допишите её в ответ. Теперь она расставлена окончательно.

Пройдите по её исходящим рёбрам и уменьшите счётчик каждой цели. У цели стало на один долг меньше.

Счётчик, дошедший до нуля, попадает в очередь. Все её зависимости уже расставлены.

Если ответ короче числа вершин, в графе есть цикл. Вершины в цикле нуля не достигают.

1. степени: A 0, B 1, C 1, D 2Рёбра это A в B, A в C, B в D и C в D.
2. очередь = [A], ответ = []Никому не должна только A, она и есть точка старта.
3. берём A, ответ = [A]B и C теряют по одному долгу. Обе дошли до нуля.
4. очередь = [B, C]У D всё ещё два долга. Она ждёт.
5. ответ = [A, B, C, D]D входит, когда оба её долга закрыты.

function topoSort(n, adj) {
    const indeg = new Array(n).fill(0);
    for (const u in adj) for (const v of adj[u]) indeg[v]++;
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const u = queue.shift();
        order.push(u);
        for (const v of adj[u] || []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

Топологическая сортировка (алгоритм Кана): разбор примера

Порядок, в котором можно пройти все курсы

Дано число курсов и список пар с предварительными требованиями. Верните порядок, в котором можно пройти всё.

Если такого порядка нет, верните пустой список.

Постройте список смежности и входящие степени за один проход.

Потом крутите цикл очереди. Ответ короче числа курсов означает цикл.

function findOrder(numCourses, prerequisites) {
    const next = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, needs] of prerequisites) {
        next[needs].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const order = [];
    for (let i = 0; i < queue.length; i++) { // index walk, never shift
        const node = queue[i];
        order.push(node);

        for (const target of next[node]) {
            if (--indegree[target] === 0) queue.push(target);
        }
    }

    // a short answer means some nodes never reached zero
    return order.length === numCourses ? order : [];
}

Топологическая сортировка (алгоритм Кана): когда применять?

Эти формулировки в условии ведут сюда:

• •задача должна идти перед другой
• •порядок, соблюдающий зависимости
• •обнаружить цикл в предпосылках
• •порядок сборки / расписание курсов / порядок установки
• •ориентированный граф, X должен произойти перед Y

Топологическая сортировка (алгоритм Кана): с чем путают?

• Обход графа BFS / DFS (Graph BFS / DFS): Обычный обход посещает вершины в любом удобном порядке. Здесь порядок и есть ответ.
• Компоненты связности (Connected components): Компоненты не смотрят на направление и только группируют вершины. Здесь направление задаёт весь ответ.
• Система непересекающихся множеств (Union-find (disjoint set)): Она считает любое ребро ненаправленным. Направление здесь и есть самое главное.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Правило жадное: берите всё, у чего не осталось долгов. Удаление вершины не может добавить зависимость.

Топологическая сортировка (алгоритм Кана): частые ошибки

• Строят рёбра в обратную сторону

  Пара читается как курс и требование к нему. Переворот молча решает совсем другую задачу.

• Не проверяют длину в конце

  Цикл даёт короткий ответ, а не ошибку. Сравните длину с числом вершин.

• Ждут единственный правильный порядок

  Готовых вершин в один момент бывает несколько. Любой порядок среди них верен.

• Берут shift на очереди

  В JavaScript это O(n) на каждое удаление. Идите по массиву индексом.

Топологическая сортировка (алгоритм Кана): задачи с собеседований

• Расписание курсов: Нужно только знать, существует ли порядок.
• Расписание курсов II: Нужен сам порядок, а не ответ да или нет.
• Словарь инопланетян: Рёбра выводятся сравнением соседних слов.
• Деревья минимальной высоты: Здесь слои листьев снимают снаружи внутрь.
• Восстановление последовательности: Проверьте, что на каждом шаге готова ровно одна вершина.
• Параллельные курсы: Считаются раунды, а не выдаётся порядок.
• Сортировка элементов по группам: Два порядка: внутри групп и между ними.

Топологическая сортировка (алгоритм Кана): сложность по времени и памяти

O(V+E)

V вершин и E рёбер дают O(V + E). Каждое ребро убирается ровно один раз.