Топологическая сортировка

Топологическая сортировка (topological sort) — линейное упорядочивание вершин ориентированного ациклического графа (DAG), при котором для каждого ребра u→v вершина u стоит перед v; сложность O(V + E).

Зачем нужно

Топологическая сортировка решает задачи планирования с зависимостями: нельзя запустить задачу B до завершения A, если A → B. Это стандартный алгоритм для пакетных менеджеров, систем сборки, разрешения зависимостей и планировщиков. Также позволяет обнаружить циклические зависимости.

Где используется

  • Пакетные менеджеры (npm, pip): порядок установки зависимостей
  • Системы сборки (Make, Webpack): порядок сборки модулей
  • Планировщики задач: учебный план (A требует B, B требует C)
  • Компиляторы: порядок компиляции файлов с зависимостями

Основной контент

Условие применимости

Топологическая сортировка возможна только для DAG (Directed Acyclic Graph). При наличии цикла — невозможна. Алгоритм попутно обнаруживает циклы.

Алгоритм 1: DFS (алгоритм Тарьяна)

function topologicalSortDFS(graph) {
  // graph: Map<node, Array<node>>
  const visited = new Set();
  const stack = ;
  let hasCycle = false;

  const inStack = new Set(); // для обнаружения циклов

  function dfs(node) {
    if (hasCycle) return;
    if (inStack.has(node)) { hasCycle = true; return; } // цикл!
    if (visited.has(node)) return;

    visited.add(node);
    inStack.add(node);

    for (const neighbor of graph.get(node) || ) {
      dfs(neighbor);
    }

    inStack.delete(node);
    stack.push(node); // добавляем после обработки всех зависимостей
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) dfs(node);
  }

  if (hasCycle) return null; // цикл — топосортировка невозможна
  return stack.reverse();    // разворачиваем для правильного порядка
}

// Пример: A→C, B→C, C→D
const graph = new Map([
  ['A', ['C']], ['B', ['C']], ['C', ['D']], ['D', ]
]);
console.log(topologicalSortDFS(graph));
// ['A', 'B', 'C', 'D'] или ['B', 'A', 'C', 'D']

Алгоритм 2: Кан (Kahn's algorithm — BFS-based)

function topologicalSortKahn(graph) {
  // Подсчёт входящих рёбер (in-degree)
  const inDegree = new Map();
  for (const [node, neighbors] of graph) {
    if (!inDegree.has(node)) inDegree.set(node, 0);
    for (const n of neighbors) {
      inDegree.set(n, (inDegree.get(n) || 0) + 1);
    }
  }

  // Начинаем с вершин без входящих рёбер
  const queue = ;
  for (const [node, deg] of inDegree) {
    if (deg === 0) queue.push(node);
  }

  const result = ;
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph.get(node) || ) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) queue.push(neighbor);
    }
  }

  // Если result не содержит все вершины — граф содержит цикл
  return result.length === inDegree.size ? result : null;
}

Сравнение алгоритмов

Критерий DFS (Тарьян) Kahn (BFS)
Время O(V + E) O(V + E)
Обнаружение цикла Через inStack Если result.length < V
Детерминизм Зависит от DFS порядка Зависит от очереди
Понятность Сложнее Проще

Пример: порядок установки пакетов

react → react-dom
react-dom → react

После топосортировки: [react, react-dom]
→ сначала устанавливаем react, потом react-dom

Частые ошибки

  • Применять к графу с циклами — бесконечная рекурсия в DFS или неполный результат в Kahn.
  • Не проверять наличие цикла — алгоритм «молча» даёт неверный результат.
  • Считать порядок единственным — при нескольких вершинах с in-degree=0 возможны разные корректные топосортировки.
  • Применять к неориентированному графу — топологическая сортировка определена только для DAG.

Связанные темы

Ресурсы