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

Question

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

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

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

Answer 1

未指定数据结构，但如果选择得当，运行时间将为 O(m + n)，其中 m 是边数，n 是顶点数。对于一个dense graph，可能是m >> n，所以O(n)的时间是不够读取整个图的。反之，如果图是不连通的，那么可能是n >> m，所以大O里面的两项都是必须的。

Answer 2

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

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

步骤 A

除L外，初始化以下

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

的所有顶点的列表

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

(c) 一个数组 B，同样每个顶点有一个槽。该数组应为每个顶点 i 存储指向 i 条边。当这个数字降为零时，相应的顶点必须是一个汇点，所以可以添加到 S.

步骤 B

首先遍历边集。对于每条边 E: i -> j 将 B[i] 递增 1，并将 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) 仅仅是因为每个顶点最多被删除一次，并且每个边最多被读取一次。

Time complexity of finding whether graph has a unique topological order