使用强连接组件进行拓扑排序以查找循环（有向图）
Doing topological sort using strongly connected components to find cycles (digraph)
据我所知，如果您有针对强连通分量的现成高效黑盒方法，一种进行拓扑排序的方法是：
（假设 - 没有自循环）
- 运行 强连通分量
- 如果您有一个或多个大小 > 1 的组件，则此图有循环。
- 否则（图中只有 1 个大小的组件）这是一个 DAG，恭喜！
- 如果是DAG运行拓扑排序，else就抱怨你做不到。
不管效率如何，以上是"technically correct"拓扑排序的方式吗？
我只是想确保我理解正确。
是的，这在技术上是正确的，因为没有自环的有向图是非循环的（即，拓扑可排序）当且仅当所有强分量的大小都是 1。不过，最常见的拓扑排序将循环检测作为一个简单的副产品。
扩展上面的答案：是的，你上面给出的算法是正确的，会产生你想要的答案。拓扑排序仅适用于 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) 中的 运行s。因此，您可以简单地 运行 进行拓扑排序，而不必同时使用 SCC 算法。虽然您算法的整体大 O 与拓扑排序的 运行ning 时间相同，但无需 运行 SCC，因为它不会为您提供任何额外的有用信息。
据我所知，如果您有针对强连通分量的现成高效黑盒方法，一种进行拓扑排序的方法是：
（假设 - 没有自循环）
- 运行 强连通分量
- 如果您有一个或多个大小 > 1 的组件，则此图有循环。
- 否则（图中只有 1 个大小的组件）这是一个 DAG，恭喜！
- 如果是DAG运行拓扑排序，else就抱怨你做不到。
不管效率如何，以上是"technically correct"拓扑排序的方式吗？
我只是想确保我理解正确。
是的，这在技术上是正确的，因为没有自环的有向图是非循环的（即，拓扑可排序）当且仅当所有强分量的大小都是 1。不过，最常见的拓扑排序将循环检测作为一个简单的副产品。
扩展上面的答案：是的，你上面给出的算法是正确的，会产生你想要的答案。拓扑排序仅适用于 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) 中的 运行s。因此，您可以简单地 运行 进行拓扑排序，而不必同时使用 SCC 算法。虽然您算法的整体大 O 与拓扑排序的 运行ning 时间相同，但无需 运行 SCC，因为它不会为您提供任何额外的有用信息。