学习首页/图算法/拓扑排序交互演示 · JavaScript

代码与动画 TOPOLOGICAL SORT

拓扑排序.

将入度为零的节点依次移出，形成依赖执行顺序。

时间 O(V + E)空间 O(V)Kahn 算法

原理与执行逻辑

将有向边解释为先后依赖，每次输出当前没有前置依赖的节点，并移除它对后继的依赖。得到的序列满足所有边的先后约束。

执行步骤

  1. 统计每个节点入度，将零入度节点加入队列。
  2. 取出一个零入度节点并输出。
  3. 将其后继的入度减一，降为零的后继入队。
  4. 队列耗尽后比较输出数量与顶点总数，数量不足表示存在有向环。

关键理解

当前入度表示尚未输出节点留下的依赖数量。拓扑序可能不唯一；孤立节点也是零入度节点，需要包含在输出中。

简短示例

A→C、B→C 中，A 与 B 可以先后任选，二者输出后 C 入度降为零；A、B、C 与 B、A、C 都有效。

代码与执行动画

STEP 0 / 13
拓扑排序
function topologicalSort(graph) {  const degree = Object.fromEntries(Object.keys(graph).map(v => [v, 0]));  for (const edges of Object.values(graph)) for (const next of edges) degree[next]++;  const queue = Object.keys(graph).filter(v => degree[v] === 0);  const result = []; let head = 0;  while (head < queue.length) {    const node = queue[head++];    result.push(node);    for (const next of graph[node]) {      if (--degree[next] === 0) queue.push(next);    }  }  if (result.length !== Object.keys(graph).length) throw Error('存在有向环');  return result;}
15 行 · 0 个片段标记
队列 A
A入度=0B入度=1C入度=1D入度=1E入度=1F入度=2
当前数据正在操作已访问 / 命中标记 / 指针
0

统计入度

将所有入度为零的节点加入初始队列。

配置演示数据

应用后重新生成执行过程，可单步观察结果。

实现说明

拓扑排序的操作规则

处理全部六个顶点，包括孤立节点。输出不足六个节点时存在有向环，不生成完整拓扑序。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。