algorithm - 使用强连接组件进行拓扑排序以找到循环（有向图）

Question

据我所知，如果你有一个现成的高效黑盒方法用于强连接组件，那么进行拓扑排序的一种方法是：

（假设 - 没有自循环）

1. 运行强连接组件
2. 如果您有一个或多个大小 > 1 的组件，则此图有循环。
3. 否则（图中只有 1 个大小的组件）它是 DAG，恭喜！
4. 如果是 DAG 运行拓扑排序，则抱怨你做不到。

不管效率如何，以上是不是“技术上正确”的拓扑排序方式？

我只是想确保我理解正确。

Answer 1

是的，它在技术上是正确的，因为没有自环的有向图是非循环的（即，拓扑可排序的）当且仅当所有强分量的大小为 1。不过，最常见的拓扑排序将循环检测作为一个简单的副产品。

Answer 2

扩展上面的答案：是的，您上面介绍的算法是正确的，并且会产生您想要的答案。拓扑排序仅适用于 DAG（有向无环图）。SCC 是一组顶点，其中每个顶点都可以到达每个其他顶点，并且本质上是循环的。因此，一个 DAG 应该有 V # 个大小为 1 的 SCC 组件。

但是，算法中有许多冗余，因为 SCC 算法通常使用 DFS 实现，运行时间为 O(V + E)，根据数据的存储方式和密度，可能接近 O(V^2)图的。生成所有 SCC 并查看所有顶点以检查它们是否存在于 SCC 大小 > 1 生成 O(2V + E)，实际上仍然只是 O(V + E)，但您最终需要额外存储 Θ( V) 为 SCC。

此外，拓扑排序还利用 DFS，它可以检测循环，因此可以发出拓扑排序是否可行的信号。这也在 O(V + E) 中运行。因此，您可以简单地运行拓扑排序，而不必使用 SCC 算法。虽然您的算法的整体大 O 与拓扑排序的运行时间相同，但无需运行 SCC，因为它不会为您提供任何额外有用的信息。