拓扑排序计算器

使用 Kahn 算法或 DFS 计算有向无环图 (DAG) 的拓扑排序。支持检测循环并报告路径、构建并行执行层级视图、支持字典序最小排序，并提供交互式图表的步骤动画演示。

拓扑排序计算器

⚡ 尝试示例：

线性链穿衣顺序课程先修晨间常规构建目标邻接表示例包含环流水线 DAG

输入格式

→ 边列表 (A→B)

⧇ 邻接表 (A: B, C)

图数据

边格式：A -> B (也接受 →, =>, :)。最多 80 个顶点 / 800 条边。

邻接格式：A: B, C, D — 每行一个顶点，后接其直接后继节点。

算法

Kahn 算法（字典序）给出唯一的、可重现的顺序。DFS 后序遍历是经典的深度优先方法。

Embed 拓扑排序计算器 Widget

拓扑排序计算器

拓扑排序计算器用于计算有向无环图 (DAG) 顶点的线性排序，使得对于从 u 到 v 的每一条有向边，u 都在 v 之前。以边列表或邻接表的形式输入图数据，该工具将使用 Kahn 算法或 DFS 后序遍历返回拓扑排序结果，检测环（并给出精确的环路径），将任务划分为并行执行层，计算有效排序的总数，并在交互式图表上以动画形式演示每一步。

什么是拓扑排序？

给定一个有向图 G = (V, E)，拓扑排序（或拓扑序列）是其顶点的一种线性排列 v₁, v₂, …, vₙ，使得对于每一条有向边 (u → v)，u 在排列中都出现在 v 之前。当且仅当图中没有有向环时（即该图为 DAG），才存在拓扑排序。这种排序通常不是唯一的：当多个顶点的入度同时为零时，图可以有多种有效的拓扑排序。

拓扑排序定义

V 的一个排列 (v₁, v₂, …, v_n) 是拓扑排序，当且仅当
对于 E 中的每一条边 (u → v)：position(u) < position(v)

此计算器使用的算法

Kahn 算法 (基于 BFS，1962年)

Kahn 算法是最直观的拓扑排序算法。在每一步中，它选择一个入度为零（没有指向它的边）的顶点，将其添加到输出结果中，并从图中“移除”它（即减少其每个后继节点的入度）。当有多个顶点的入度为零时，可以使用最小堆（得到字典序最小的排序）或 FIFO 队列（得到插入顺序的排序）来打破僵局。Kahn 算法的运行时间为 O(|V| + |E|)，同时也可用作环检测器：如果队列为空后仍有顶点的入度 > 0，则说明图中存在环。

Kahn 算法 (伪代码)

Kahn(G):
  Q ← { v ∈ V : indeg(v) = 0 }
  L ← [ ]
  while Q 不为空:
    u ← Q.pop()
    L.append(u)
    for 每一条边 u → v:
      indeg(v) -= 1
      if indeg(v) = 0: Q.push(v)
  if |L| < |V|: 报告存在环
  else: 返回 L

DFS 后序遍历 (Tarjan，1976年)

DFS 算法运行深度优先搜索，每当一个顶点完成搜索（即其所有后继节点都已被完全探索）时，将其压入栈中。最后反转栈中的元素即可得到有效的拓扑排序。环检测非常自然：如果遇到一个仍处于进行中状态（标记为灰色）的顶点，说明发现了一条回边，因此该图不是 DAG。DFS 后序遍历的运行时间同样为 O(|V| + |E|)。

DFS 后序遍历 (伪代码)

DFS-Topo(G):
  for V 中的每个顶点 u: color[u] ← 白色
  L ← 空栈
  for V 中的每个顶点 u:
    if color[u] = 白色: visit(u)
  return reverse(L)

visit(u):
  color[u] ← 灰色
  for 每一条边 u → v:
    if color[v] = 灰色: 报告存在环
    if color[v] = 白色: visit(v)
  color[u] ← 黑色; L.push(u)

并行执行层

DAG 的分层视图将其顶点划分为不同的级别，使得每条边都从较低编号的级别指向较高编号的级别。同一层中的顶点相互独立，因此可以并行执行。层数等于最长路径的长度加一，这被称为 DAG 的关键路径，即即使拥有无限的并行能力，完成所有任务所需的最少顺序轮次。只要输入的是 DAG，此计算器就会自动生成分层视图。

环检测

如果图中包含有向环，则无法进行拓扑排序。我们的计算器会报告具体的环路径（例如 A → B → C → A），并在可视化界面上用红色标出环边。移除环上的任意一条边即可恢复无环状态。

输入格式

边列表

将每条有向边写为 起点 -> 终点，用逗号或换行符分隔。接受的箭头变体：->, →, =>, -->, :。你还可以使用链式表达：A -> B -> C 是 A->B 和 B->C 的简写。顶点标签可以是字母、数字、下划线、短横线和点。

A -> B, B -> C, A -> C
C -> D
衬衫 -> 领带 -> 夹克

邻接表

写下每个顶点、一个冒号及其直接后继节点（它指向的顶点）。没有后继节点的顶点仍需占一行，例如 D:。

A: B, C
B: D
C: D
D:

如何使用此计算器

选择格式： 使用单选按钮在边列表和邻接表之间切换。
输入图数据： 粘贴数据或点击快速示例（穿衣顺序、课程先修、构建目标、含环图等）。
选择算法： 选择 Kahn 字典序以获得唯一的、可重现的顺序；选择插入顺序以保留输入顺序；选择 DFS 后序遍历以使用经典深度优先方法；或选择“显示全部”并排查看每种排序。
点击“拓扑排序”： 排序结果、环检测、分层视图、关键路径长度、有效排序总数和交互式图表将显示在下方。
探索： 点击“播放”观看每个顶点逐步输出。入度徽章会实时更新。拖动任何节点可重新安排布局。

实际应用

构建系统和编译器

像 make、Bazel、Gradle 和 npm 这样的工具会对它们的构建目标进行拓扑排序，以便每个目标仅在其所有依赖项编译完成后才进行编译。依赖图中的环通常被报告为致命错误——构建系统无法确定从何处开始。

任务调度

项目经理使用 DAG 来记录任务依赖关系。拓扑排序给出了有效的执行顺序，而分层视图给出了无限并行情况下的最少轮次。最长链是决定项目持续时间的关键路径。

课程先修计划

大学课程目录是一个 DAG：边表示先修关系。拓扑排序是一个合法的学习计划，而层级则告诉学生每个学期可以并行修读哪些课程。

电子表格重算

当单元格发生变化时，电子表格必须按依赖顺序重新计算每个下游单元格——这是对单元格依赖 DAG 的拓扑排序。循环引用（环）会被应用程序拒绝。

包管理器和插件加载器

Apt、pip、Homebrew、Maven 和无数的插件框架通过对它们的依赖 DAG 进行拓扑排序来解决安装或加载顺序问题。

符号解析和指令调度

编译器使用拓扑排序来对声明进行排序，而 CPU 使用数据依赖 DAG 在重排序缓冲区中调度指令，以避免违反数据冒险。

计算拓扑排序的数量

对于一个包含 n 个顶点的 DAG，不同有效拓扑排序的数量范围从 1（完全排序的链）到 n!（无边的图）。计算精确数量通常是 #P-完全 问题，但对于最多 16 个顶点的图，此计算器使用位掩码动态规划公式进行计算：f(S) = Σ f(S ∪ {v})，其中 v ∉ S 且其所有前驱节点都在 S 中。

复杂度与性能

时间： Kahn 算法和 DFS 后序遍历的运行时间均为 O(|V| + |E|) —— 与图的大小呈线性关系。
空间： 用于入度跟踪和输出排序的 O(|V|)，加上用于邻接结构的 O(|V| + |E|)。
环检测： 已内置于两种算法中。当 |输出| < |V| 时，Kahn 算法检测到环；当发现回边（灰色邻居）时，DFS 检测到环。
工具限制： 交互式可视化最多支持 80 个顶点和 800 条边。排序计数上限为 16 个顶点。

常见问题

什么是拓扑排序？

有向无环图的拓扑排序是其顶点的一种线性排序，使得对于从 u 到 v 的每一条有向边，u 都排在 v 之前。它代表了在尊重任务依赖关系的前提下处理任务的合法顺序。

此计算器使用哪种算法？

计算器同时运行 Kahn 算法和 DFS 后序遍历。Kahn 算法通过不断移除入度为零的顶点并减少其后继节点的入度来工作。DFS 后序遍历运行深度优先搜索并反转完成顺序。两者的运行时间均为 O(|V| + |E|)。

如果我的图中有环怎么办？

含有有向环的图没有拓扑排序。计算器会检测到环，在可视化中用红色标出，并报告精确的环路径，以便你了解需要移除哪些边才能使图成为 DAG。

什么是字典序最小的拓扑排序？

当存在多种有效的拓扑排序时，通过在每一步始终选择入度为零且按字母顺序最小的顶点，可以获得字典序最小的排序。此计算器默认的 Kahn 模式会返回这种唯一的排序，它稳定且易于重现。

什么是层级或水平视图？

层级视图根据距任何源节点的最长路径长度对顶点进行分组。同一层中的顶点之间没有依赖关系，因此可以并行运行。层数等于最长依赖链加一，代表了完成所有任务所需的最少并行轮次。

一个图可以有多个有效的拓扑排序吗？

是的。如果在 Kahn 算法的任何步骤中有多个入度为零的顶点，则下一步可以选择其中的任何一个。此计算器可以计算包含最多 16 个顶点的图的不同拓扑排序的精确数量。

Kahn 算法和 DFS 后序遍历有什么区别？

Kahn 算法是自顶向下的：它反复选择源节点（入度为 0）并首先输出它们。DFS 后序遍历是自底向上的：它先完成汇节点并将它们置于排序末尾。两者都是 O(|V| + |E|) 并能产生有效的拓扑排序，但通常结果不同。Kahn 算法更易于并行化和适配字典序；DFS 更易于与其他基于 DFS 的分析（如强连通分量）结合。

该工具支持的最大图规模是多少？

该计算器支持最多 80 个顶点和 800 条边。计算有效拓扑排序的总数上限为 16 个顶点，因为该问题是 #P-完全的，且状态空间随 2ⁿ 增长。交互式可视化和算法动画可以在最大支持规模内平滑运行。

延伸阅读

引用此内容、页面或工具为：

"拓扑排序计算器" 于 https://MiniWebtool.com/zh-cn/拓扑排序计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队开发。更新日期：2026年4月20日

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

其他相关工具:

拓扑排序计算器

拓扑排序计算器

什么是拓扑排序？

此计算器使用的算法

Kahn 算法 (基于 BFS，1962年)

DFS 后序遍历 (Tarjan，1976年)

并行执行层

环检测

输入格式

边列表

邻接表

如何使用此计算器

实际应用

构建系统和编译器

任务调度

课程先修计划

电子表格重算

包管理器和插件加载器

符号解析和指令调度

计算拓扑排序的数量

复杂度与性能

常见问题

什么是拓扑排序？

此计算器使用哪种算法？

如果我的图中有环怎么办？

什么是字典序最小的拓扑排序？

什么是层级或水平视图？

一个图可以有多个有效的拓扑排序吗？

Kahn 算法和 DFS 后序遍历有什么区别？

该工具支持的最大图规模是多少？

延伸阅读

其他相关工具:

进阶数学计算:

常用工具: