找到图的节点，它们之间至少有 2 条路径
Find the nodes of a graph with minimum 2 paths between them
我有一个强连通图，我想找到它们之间至少有 2 条路径的节点对。
你能给我一个算法的想法或者我可以使用的东西吗？谢谢。
首先想到的是按以下方式利用 DFS：
DFS 从某个顶点 v1 开始，"discovers" 个顶点一个一个。每个发现的顶点递归地启动它自己的 DFS 并在其递归 returns.
后得到 "processed"
假设从 v1 到 v2 有两条有向路径。在这种情况下，v2 将成为 "discovered"（通过从 v1 到 v2 的两条路径之一）并最终成为 "processed"。然而，v1 的递归还没有结束。 DFS 流将第二次到达 v2（这次使用从 v1 到 v2 的第二条路径），但是这次 v2 已经处于 "processed" 状态。
因此，每当我们遇到 "processed" 顶点时，就意味着有第二条路径可以到达它。
这种方法适用于各种有向图，它没有利用图是强连通的事实，所以可能这个事实可以用于更优化的解决方案。
另请注意，对于无向图，情况要轻松得多 - 我们只需要检测图中的所有环路，并且环路中的每对顶点之间都有两条路径。在有向图中，循环是单向的，因此我们不能假设循环成员之间存在双向路径。
我有一个强连通图，我想找到它们之间至少有 2 条路径的节点对。 你能给我一个算法的想法或者我可以使用的东西吗？谢谢。
首先想到的是按以下方式利用 DFS：
DFS 从某个顶点 v1 开始，"discovers" 个顶点一个一个。每个发现的顶点递归地启动它自己的 DFS 并在其递归 returns.
后得到 "processed"
假设从 v1 到 v2 有两条有向路径。在这种情况下，v2 将成为 "discovered"（通过从 v1 到 v2 的两条路径之一）并最终成为 "processed"。然而，v1 的递归还没有结束。 DFS 流将第二次到达 v2（这次使用从 v1 到 v2 的第二条路径），但是这次 v2 已经处于 "processed" 状态。
因此，每当我们遇到 "processed" 顶点时，就意味着有第二条路径可以到达它。
这种方法适用于各种有向图，它没有利用图是强连通的事实，所以可能这个事实可以用于更优化的解决方案。
另请注意，对于无向图，情况要轻松得多 - 我们只需要检测图中的所有环路，并且环路中的每对顶点之间都有两条路径。在有向图中，循环是单向的，因此我们不能假设循环成员之间存在双向路径。