Kahn 算法 vs DFS 方法：比较分析

有向无环图 (DAG) 在许多领域都是重要的功能性数据结构，例如调度、数据处理工作流和网络分析。DAG 的一个基本操作是拓扑排序，它将图的节点线性排列以保留边的方向。拓扑排序在指令调度、电子表格中公式单元格求值的排序以及项目时间线的绘制中都有应用。

有两种著名的算法可以对 DAG 实现拓扑排序：Kahn 算法和深度优先搜索 (DFS)。两者都能生成有效的拓扑排序，但具有略微不同的属性和用例。本文对 Kahn 算法与 DFS 方法进行拓扑排序进行对比分析。我们将讨论每种算法的步骤、时间和空间复杂度，以及这两种方法的相对优缺点。目标是根据实现复杂性、DAG 的连通性以及是否需要检测环等因素，强调何时可能更倾向于一种方法。讨论将为在调度、数据处理和网络建模等领域应用拓扑排序的工程师和研究人员提供有益的见解。

Kahn 算法

Kahn 算法以 Arthur Kahn 的名字命名，他于 1962 年描述了该算法。它的工作原理是反复查找没有传入边的节点，将它们从图中移除，并将它们添加到线性排序中。这利用了 DAG 必须始终至少有一个入度为 0 的节点的关键属性。该算法重复这个过程，即查找入度为 0 的节点、移除它们并将它们追加到排序中，直到所有节点都被处理完毕。

步骤 Kahn 算法涉及的步骤是：

1. 初始化一个列表 L，其中将包含拓扑排序的节点。它最初为空。
2. 初始化一个集合 S，其中包含图中的所有节点。
3. 在 S 中查找所有入度为 0 的节点。这些节点没有传入边，可以开始拓扑排序。
4. 将步骤 3 中找到的入度为 0 的节点按任意顺序添加到 L 中，并从 S 中移除它们。
5. 上一步添加到 L 中的节点现在具有指向 S 中其他节点的出边。将所有邻居的入度减 1，以表示移除了边。
6. 重复步骤 3-5，查找新的入度为 0 的节点，将它们添加到 L 中，并减去邻居的入度，直到 S 为空。
7. 一旦 S 为空，L 就包含了拓扑排序的节点。

正确性证明 关键在于，一个非空的 DAG 在所有节点都被移除之前，必须始终至少有一个节点的入度为 0。这使得节点可以通过反复查找这些入度为 0 的节点来逐步添加到 L 中。

为了证明正确性，我们使用数学归纳法。

基本情况：根据 DAG 的定义，至少有一个节点最初的入度为 0。因此，算法对于第一个节点是有效的。

归纳假设：假设算法对于添加到 L 的前 k 个节点是正确的。

归纳步骤：添加第 (k+1) 个节点时，将现有节点的入度减 1，因为移除边不会创建入度为负的节点。因此，必须至少有一个新的入度为 0 的节点可以接下来添加。

因此，根据数学归纳法，算法将导致节点按拓扑顺序添加到 L 中。

时间和空间复杂度 该算法的运行时间为 O(V+E)，其中 V 是节点数，E 是边数。通过扫描所有节点，可以在 O(V) 时间内实现步骤 3。通过检查当前节点的邻居，步骤 4 需要 O(E) 时间。步骤 3-5 总共重复 V 次，每个节点一次。

空间复杂度为 O(V)，用于存储列表 L 和集合 S。

输出

Topological Sort: ['a', 'b', 'd', 'e', 'c']

以下是实现 Kahn 算法进行拓扑排序的 Python 程序解释：

该程序首先创建一些辅助数据结构：

1. in_degree：一个字典，用于跟踪每个节点的入度（传入边的数量）。
2. Queue：一个双端队列，包含已准备好添加到结果中的入度为 0 的节点。
3. Result：一个列表，将包含拓扑排序的节点。
   • 然后，它通过遍历所有边来计算每个节点的入度：
   • 每条边 u → v 都会使 v 的 in_degree 增加 1。
   • 接下来，它初始化队列，其中包含所有入度为 0 的节点：
   • 如果每个节点的 in_degree 为 0，则将其添加到队列中。
   • 现在，Kahn 算法的关键步骤：

当队列不为空时

1. 从队列的左侧弹出一个节点 - 该节点现在已添加到结果的拓扑排序中。
2. 对于弹出节点的每个邻居，将其 in_degree 减 1。
3. 如果邻居的 in_degree 变为 0，则将其添加到队列中。

最后，它检查添加到结果中的节点数是否与总节点数匹配。如果不匹配，则存在一个环。否则，结果包含拓扑排序。

该示例演示了如何通过传递表示为邻接表的示例图来调用 topological_sort 方法。它会打印最终的拓扑排序或检测到环。

深度优先搜索 (DFS) 方法

深度优先搜索 (DFS) 是一种算法技术，它通过在回溯和探索其他选项之前，将图的路径深入探索到未访问的顶点。深度优先遍历的关键特征是，它会在回溯和尝试不同路径之前，尽可能深入地探索一条特定的路径。当应用于有向无环图 (DAG) 的拓扑排序时，DFS 遍历可以通过跟踪顶点的完成时间和按反序打印它们来有效地计算有效的拓扑排序。具体来说，DFS 从一个顶点开始探索图，在回溯和尝试不同分支之前，完全递归地进入一个出边路径。任何路径中最后完成的顶点保证没有进一步未探索的邻居。通过将完成时间存储在堆栈中并在反序弹出顶点，可以自然地获得适当排序的拓扑排序。在深入遍历图的每个分支直到耗尽后再进行宽度搜索的内置机制，使得 DFS 成为计算拓扑排序的简单而优雅的选择。DFS 的时间和复杂度 O(V+E) 与其他方法相同，使其成为拓扑排序在实际应用中的最佳算法。其实现简单和执行期间检测环的能力，使其成为依赖于有向无环图元素正确排序的领域的通用选项。

算法

高级步骤是：

1. 对给定的 DAG 进行 DFS 遍历。
2. 将顶点的完成时间存储在堆栈中。
3. 从堆栈中弹出元素以打印拓扑排序。

DFS 遍历具有额外的簿记：

1. 标记每个顶点的访问状态（未访问、已访问、正在访问）。
2. 看到一个顶点时，递归地调用其所有未访问的邻居。
3. 在递归调用完成后，将顶点标记为“已访问”并将其推入堆栈。

递归调用将继续进行，直到找到一个没有未访问邻居的顶点。

堆栈中的顶点 关键在于，递归堆栈顶部的顶点或 DFS 期间最后打印的顶点始终是叶子顶点（或局部汇点）。因此，通过按完成时间的逆序打印顶点，我们可以得到拓扑排序。

例如，考虑图

A → B → C → D

DFS 可能按 A B D C 的顺序访问顶点，但堆栈打印顺序将是：C D B A

这是拓扑排序后的结果。

处理环 如果在遍历期间遇到已访问的顶点，DFS 也可以轻松检测到环。我们可以相应地打印一条消息。

复杂度：时间复杂度为 O(V+E)，用于访问所有顶点和边。如果图是线性链，则在最坏情况下，堆栈的空间复杂度为 O(V)。

输出

Topological Sort: ['a', 'b', 'd', 'e', 'c']

说明

1. 定义一个 dfs(node) 递归函数，该函数将从一个节点开始进行深度优先遍历。
2. 在 dfs() 内部：
   1. 将当前节点标记为已访问。
   2. 对每个未访问的邻居节点递归调用 dfs。
   3. 递归遍历完邻居后，将当前节点追加到全局结果列表。
3. 初始化一个 visited 集合来跟踪已访问的节点。
4. 初始化 result 列表来存储最终拓扑排序的节点。
5. 从图中的每个未访问节点开始调用 dfs 遍历。
6. 从所有节点调用 dfs 之后，反转 result。
7. 返回反转后的结果。

它是如何工作的？

• 它将 DFS 作为起点，从每个未访问的节点开始。
• 每个节点只有在其邻居被遍历后才会被追加到结果中。
• 因此，result 列表按完成时间的逆序包含节点。
• 通过反转结果，我们得到拓扑排序。

关键在于，DFS 在回溯并探索其他路径之前会一直探索路径直到其完成。因此，任何路径中的最后一个节点都会在其依赖项之后添加到结果中。

最后，如果未检测到环，我们将打印返回的拓扑排序。

Kahn 算法与 DFS 的区别

访问顶点的顺序

Kahn's

• 基于最小入度启发式显式选择下一个顶点。
• 如果多个节点入度为 0，则可以按任意顺序选择顶点（集合/队列实现）。
• 从依赖项较少的节点到依赖项较多的节点，逐层访问顶点。

DFS

• 遵循基于递归树的隐式访问顺序。
• 在回溯之前，总是尽可能深入地访问当前节点的邻居。
• 这可能导致基于起始顶点的不同顺序。
• 与 Kahn 的分层方法相比，以更线性的方式遵循边的访问顺序。

处理不连通图

Kahn's

• 即使图不连通，也能正常工作。
• 每个组件的入度计算都是有效的。
• 为每个组件生成正确的拓扑排序。

DFS

• 必须为每个组件提供一个起始顶点才能完全遍历。
• 无法访问从起始节点无法到达的顶点。
• 无法直接对不连通图进行拓扑排序。

复杂度分析

渐进复杂度

• 对于邻接表表示，两者均为 Θ(V+E)。
• O(V+E) 或简单地说，与顶点和边的数量成线性关系。

常数因子差异

• DFS 由于递归需要更多的函数调用。
• Kahn 的更直接的迭代入度更新可能更快。

实际性能取决于：

• 图的连通性和结构。
• 开销占主导地位的输入大小阈值。

因此，对于庞大且稀疏的图，Kahn 的算法可能比 DFS 稍微快一点。

易于实现

Kahn 算法

• 概念上简单，基于入度的直接处理。
• 迭代算法，没有递归栈。

DFS

• 由于递归、调用栈和回溯而更加复杂。
• 与迭代的 Kahn 方法相比，调试更困难。
• 简单的递归编码错误可能会破坏逻辑。

因此，Kahn 算法通常更容易正确编写。