拓扑排序计算器

拓扑排序计算器

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

什么是拓扑排序？

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

此计算器使用的算法

Kahn 算法 (基于 BFS，1962年)

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

DFS 后序遍历 (Tarjan，1976年)

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

并行执行层

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

环检测

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

输入格式

边列表

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

邻接表

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

如何使用此计算器

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

实际应用

构建系统和编译器

像 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ⁿ 增长。交互式可视化和算法动画可以在最大支持规模内平滑运行。

延伸阅读

• 拓扑排序 — 维基百科
• 有向无环图 — 维基百科
• 深度优先搜索 — 维基百科
• 关键路径法 — 维基百科
• 强连通分量 — 维基百科