我有一个强连通图，我想找到它们之间至少有 2 条路径的节点对。你能给我一个算法或我可以使用的东西的想法吗？谢谢。
1 回答
1
首先想到的是，以下列方式利用 DFS：
DFS 从某个顶点 v1 开始，并逐个“发现”顶点。每个发现的顶点递归地启动它自己的 DFS 并在其递归返回后得到“处理”。
假设从 v1 到 v2 有两条有向路径。在这种情况下，v2 将被“发现”（通过从 v1 到 v2 的两条路径之一）并最终“处理”。但是，v1 的递归还没有结束。DFS 流将第二次到达 v2（这次使用从 v1 到 v2 的第二条路径），但是这一次，v2 已经处于“已处理”状态。
因此，每当我们遇到“已处理”的顶点时，就意味着有第二条路径可以到达它。
这种方法适用于各种有向图，它没有利用图是强连接的事实，因此可能这个事实可以用于更优化的解决方案。
还要注意，对于无向图，情况要轻松得多——我们只需要检测图中的所有循环，循环中的每一对顶点之间都有两条路径。在有向图中，循环是单向的，因此我们不能假设循环成员之间存在双路径。
于 2018-05-13T13:44:35.403 回答