如何查找给定图的每对顶点之间是否存在路径？
How to find if there's a path between every pair of vertices of a given graph?
为了查找有向图中每对顶点之间是否存在路径，我正在检查是否可以使用 DFS 从特定顶点访问所有顶点。问题是我必须执行 V DFS，其中 V 是顶点数。 （V 可以达到 10^5）。有没有更有效的方法来做到这一点？一些伪代码或实现将不胜感激。
考虑此图：(1 -> 3)、(2 -> 3)、(3 -> 1)
没有从 1 到 2 的路径，但有从 2 到 1 的路径（2 -> 3 -> 1）。所以这意味着即使没有路径 (v -> u)，每对顶点 (u -> v) 都有路径。
看看 Tarjan 的强连通分量算法。如果只有一个强连通分量存在，这意味着每对顶点之间都存在一条路径。
要解决这个问题，请对图进行拓扑排序，然后以反向伪拓扑顺序遍历它。如果您不需要 'restart' 遍历这意味着，这意味着每个可能的顶点之间都存在一条路径。
查找是否有一条路径访问有向图的所有顶点（可以多次访问顶点和边）则：
- 找到图表的 strongly connected components [SCC]。
- 缩小图表，用单个 "pseudo-vertex" 替换每个 SCC，并包括连接 SCC 的边。
- 该图现在将不包含任何循环（因为每个循环都是 SCC 的一部分）因此将是一个根 graph/tree 并且必须有：
- 一个或多个根伪顶点（没有入站边）；
- 一个或多个叶子伪顶点（没有出边；可以同时是叶子和根顶点）；和
- 作为分支一部分的零个或多个伪顶点（具有入站和出站边）。
- 平凡地，每个叶子和分支的一部分都可以从祖先伪顶点到达（因为它们有入站边）但是不可能从另一个平行分支到达一个分支所以我们只需要考虑是否结果图是一条没有分支的简单路径。
- 计算根顶点的个数：
- 如果存在单个根伪顶点 (SCC)，则该 SCC 中包含的任何顶点都可以到达图中的所有其他顶点；
- 如果有超过 1 个根伪顶点，则没有顶点具有到所有其他顶点的路径（因为您无法从不同的根到达一个根）。
- 如果奇异的根伪顶点和每个后续的后代伪顶点只有一条出站边（即没有分支）直到到达叶子，则结果图包含一条可以到达所有顶点的路径.
例子:
如果图形的形式为以下形式，则将 SCC 减少为伪顶点后：
(1) -> (2) -> ... (n-1) -> (n)
那么有一条路径可以访问所有的顶点
如果是以下形式：
(1_a) --\
+--> (2) -> ... (n-1) -> (n)
(1_b) --/
然后顶点 (1_a) 无法从 (1_b) 到达，反之亦然，因此没有路径可以到达所有顶点。
同样：
/-> (n_a)
(1) -> (2) -> ... -+
\-> n_b
那么顶点 (n_a) 无法从 (n_b) 到达，反之亦然，因此没有路径可以到达所有顶点。
最后，如果是这样的形式：
/-> (x_a) -\
(1) -> (2) -> ... -+ +-> ... (n-1) -> (n)
\-> (x_b) -/
那么就没有可以同时到达(x_a)和(x_b)的路径了。
我不知道为什么有些答案看起来如此复杂。其实可以直接用图的拓扑排序，检查每个节点和它的后续节点之间是否有边连接。
为了查找有向图中每对顶点之间是否存在路径，我正在检查是否可以使用 DFS 从特定顶点访问所有顶点。问题是我必须执行 V DFS，其中 V 是顶点数。 （V 可以达到 10^5）。有没有更有效的方法来做到这一点？一些伪代码或实现将不胜感激。
考虑此图：(1 -> 3)、(2 -> 3)、(3 -> 1)
没有从 1 到 2 的路径，但有从 2 到 1 的路径（2 -> 3 -> 1）。所以这意味着即使没有路径 (v -> u)，每对顶点 (u -> v) 都有路径。
看看 Tarjan 的强连通分量算法。如果只有一个强连通分量存在，这意味着每对顶点之间都存在一条路径。
要解决这个问题，请对图进行拓扑排序，然后以反向伪拓扑顺序遍历它。如果您不需要 'restart' 遍历这意味着，这意味着每个可能的顶点之间都存在一条路径。
查找是否有一条路径访问有向图的所有顶点（可以多次访问顶点和边）则：
- 找到图表的 strongly connected components [SCC]。
- 缩小图表，用单个 "pseudo-vertex" 替换每个 SCC，并包括连接 SCC 的边。
- 该图现在将不包含任何循环（因为每个循环都是 SCC 的一部分）因此将是一个根 graph/tree 并且必须有：
- 一个或多个根伪顶点（没有入站边）；
- 一个或多个叶子伪顶点（没有出边；可以同时是叶子和根顶点）；和
- 作为分支一部分的零个或多个伪顶点（具有入站和出站边）。
- 平凡地，每个叶子和分支的一部分都可以从祖先伪顶点到达（因为它们有入站边）但是不可能从另一个平行分支到达一个分支所以我们只需要考虑是否结果图是一条没有分支的简单路径。
- 计算根顶点的个数：
- 如果存在单个根伪顶点 (SCC)，则该 SCC 中包含的任何顶点都可以到达图中的所有其他顶点；
- 如果有超过 1 个根伪顶点，则没有顶点具有到所有其他顶点的路径（因为您无法从不同的根到达一个根）。
- 如果奇异的根伪顶点和每个后续的后代伪顶点只有一条出站边（即没有分支）直到到达叶子，则结果图包含一条可以到达所有顶点的路径.
例子:
如果图形的形式为以下形式，则将 SCC 减少为伪顶点后：
(1) -> (2) -> ... (n-1) -> (n)
那么有一条路径可以访问所有的顶点
如果是以下形式：
(1_a) --\
+--> (2) -> ... (n-1) -> (n)
(1_b) --/
然后顶点 (1_a) 无法从 (1_b) 到达，反之亦然，因此没有路径可以到达所有顶点。
同样：
/-> (n_a)
(1) -> (2) -> ... -+
\-> n_b
那么顶点 (n_a) 无法从 (n_b) 到达，反之亦然，因此没有路径可以到达所有顶点。
最后，如果是这样的形式：
/-> (x_a) -\
(1) -> (2) -> ... -+ +-> ... (n-1) -> (n)
\-> (x_b) -/
那么就没有可以同时到达(x_a)和(x_b)的路径了。
我不知道为什么有些答案看起来如此复杂。其实可以直接用图的拓扑排序，检查每个节点和它的后续节点之间是否有边连接。