re:re:actable
Урок 073 минуты чтения

Что такое topological sort?

На этой странице
Кратко

Topological sort - порядок вершин directed acyclic graph, где каждая зависимость идет раньше того, что от нее зависит. Используется для курсов, задач, сборки проекта, dependency resolution.

Вопрос

Что такое topological sort и как найти порядок выполнения зависимых задач?

Когда нужен topological sort?

Если есть зависимости:

TypeScript -> React -> Next.js

Нельзя изучать/собирать dependent item раньше dependency.

Topological sort работает только для DAG:

Directed Acyclic Graph

Kahn algorithm

Идея:

  1. Считаем indegree для каждой вершины.
  2. Кладем вершины с indegree = 0 в queue.
  3. Достаем вершину, добавляем в ответ.
  4. Уменьшаем indegree соседей.
  5. Если сосед стал 0, добавляем в queue.
function topologicalSort(nodes: string[], edges: Array<[string, string]>): string[] {
  const graph = new Map<string, string[]>()
  const indegree = new Map<string, number>()
 
  for (const node of nodes) {
    graph.set(node, [])
    indegree.set(node, 0)
  }
 
  for (const [from, to] of edges) {
    graph.get(from)!.push(to)
    indegree.set(to, (indegree.get(to) ?? 0) + 1)
  }
 
  const queue = nodes.filter((node) => indegree.get(node) === 0)
  let head = 0
  const order: string[] = []
 
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
 
    for (const next of graph.get(node) ?? []) {
      indegree.set(next, indegree.get(next)! - 1)
      if (indegree.get(next) === 0) queue.push(next)
    }
  }
 
  return order.length === nodes.length ? order : []
}

Пример - порядок изучения тем:

JS -> TS -> React -> Next
JS -> React
Шагqueue после шагаВзялиУменьшили indegreeorder
старт[JS]-indegree: JS 0, TS 1, React 2, Next 1[]
1[TS]JSTS 1 -> 0, React 2 -> 1[JS]
2[React]TSReact 1 -> 0[JS, TS]
3[Next]ReactNext 1 -> 0[JS, TS, React]
4[]Next-[JS, TS, React, Next]

indegree - сколько еще не выполненных зависимостей у вершины. Вершина попадает в очередь, когда все ее зависимости уже в ответе.

Cycle

Если в graph есть cycle, topological order невозможен.

Признак в Kahn algorithm:

order.length < nodes.length

Например, A -> B -> C -> A: у всех трех вершин indegree = 1, очередь с самого начала пуста, order остается пустым.

Что отвечать на собеседовании?

Topological sort упорядочивает вершины directed acyclic graph так, что все зависимости идут раньше зависимых вершин. Его можно реализовать через DFS или Kahn algorithm с indegree и queue. Если после алгоритма не все вершины попали в ответ, значит есть цикл.

Что важно помнить: частые ошибки

  • Применять topological sort к undirected graph.
  • Не проверять cycle.
  • Путать направление ребра.
  • Не добавлять vertices без edges.
  • Использовать shift() в queue.

Мини-шпаргалка

  • Только DAG.
  • Directed edges.
  • Dependency before dependent.
  • Kahn = indegree + queue.
  • Cycle -> order impossible.
  • Time O(V + E).

Документация

Wikipedia: Topological sorting.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам