algorithm - 寻找图是否具有唯一拓扑顺序的时间复杂度

Question

我有这个算法来查找有向图是否具有唯一的拓扑顺序

1. 初始化列表L
2. 在该图中找到作为汇点的顶点 V(汇点 = 从其出发的任何有序边都没有的顶点)
3. 从图中删除所有进入 V 的边，然后删除顶点 V
4. 将V加到L
5. 如果图中还有顶点，转到步骤 2

最后我得到了 L 中顶点的拓扑顺序。如果我可以在第 2 步中从多个顶点中进行选择，那么这个拓扑顺序不是唯一的。如果我在图为空之前卡在任何这些步骤中，则意味着该图根本没有拓扑顺序。

我假设该算法的时间复杂度为 O(n)，其中 n 是图中的顶点数，但显然这是不对的。

Answer 1

设m 为边数，n 为顶点数。您的算法的简单实现是 O(nm)。如果您通过遍历边集来实现第 2 步，这将是一个可以执行 n 次的循环中的 O(m) 迭代。

但是，您可以按如下方式在时间复杂度 O(n+m) 中完成。我假设顶点存储为整数，边存储为尾部和头部的一对整数。

步骤A

除了L，初始化如下

(a) 一个数组 A，每个顶点有一个槽。该数组应为每个顶点 i 存储指向 i 的所有顶点的列表。

(b) 堆栈 S 顶点是汇点(因此可以删除)。

(c) 一个数组 B，同样每个顶点都有一个槽。此数组应为每个顶点 i 存储 远离 i 的边的数量。当这个数字降为零时，相应的顶点必须是一个汇，因此可以添加到 S。

步骤 B

首先遍历边集。对于每条边 E: i -> j 将 B[i] 加一并将 E 添加到列表 A[j] 。此迭代是 O(m)。

步骤 C

遍历数组 B，如果 B[i] == 0，将 i 添加到堆栈 S。这是 O(m)。

步骤 D

步骤D是一个while循环

while (S is not empty) { 

从 S 中删除第一个接收器 i 并将其添加到 L。因为您有一个列表 A[i]，所以您知道所有指向 i 的边。对于这些边中的每一个，E: j-> i 通过从 B[j] 中减去 1 来移除边。如果 B[j] 的值已降为零，则将 j 添加到 S

}.

在步骤 D 结束时，所有汇都将被移除。步骤 D 是 O(n+m)，因为每个顶点最多被移除一次，而每个边最多被读取一次。