c++ - 如何查找给定图的每对顶点之间是否存在路径？

Question

为了查找有向图中每对顶点之间是否存在路径，我正在检查是否可以使用 DFS 从特定顶点访问所有顶点。问题是我必须执行 V DFS，其中 V 是顶点数。 (V 可以达到 10^5)。有没有更有效的方法来做到这一点？一些伪代码或实现将不胜感激。

考虑这个图:(1 -> 3), (2 -> 3), (3 -> 1)

没有从 1 到 2 的路径，但有一条从 2 到 1 的路径(2 -> 3 -> 1)。所以这意味着即使没有路径 (v -> u)，每对顶点 (u -> v) 都有路径。

Answer 1

看看 Tarjan 的强连通分量算法。如果只存在一个强连通分量，则意味着每对顶点之间都存在一条路径。

要解决这个问题，请对图进行拓扑排序，然后以反向伪拓扑顺序遍历它。如果您不需要“重新开始”遍历，这意味着每个可能的顶点之间都存在一条路径。