Что такое 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 GraphKahn algorithm
Идея:
- Считаем indegree для каждой вершины.
- Кладем вершины с
indegree = 0в queue. - Достаем вершину, добавляем в ответ.
- Уменьшаем indegree соседей.
- Если сосед стал
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 после шага | Взяли | Уменьшили indegree | order |
|---|---|---|---|---|
| старт | [JS] | - | indegree: JS 0, TS 1, React 2, Next 1 | [] |
| 1 | [TS] | JS | TS 1 -> 0, React 2 -> 1 | [JS] |
| 2 | [React] | TS | React 1 -> 0 | [JS, TS] |
| 3 | [Next] | React | Next 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).