在无向图中查找两个顶点之间所有简单路径上的所有顶点。

Question

在无向图中查找两个顶点之间所有简单路径上的所有顶点。

algorithmlanguage-agnosticgraphdepth-first-searchbreadth-first-search

15

枚举两个顶点之间所有简单路径在一般情况下需要指数级的时间，因为在这些顶点之间可能存在指数级数量的简单路径。但是，如果我们只关心那些出现在两个端点间至少一个简单路径上的顶点呢？

也就是说：给定一个无向图和两个不同的顶点，是否存在一个多项式时间算法来找到连接它们之间至少一个简单路径的每个顶点？ 这并不是连通性；死胡同和盲路是被排除在外的，但支路和汇流路径可以被考虑。

我发现编写一个看起来能解决此问题的算法非常容易，但在某些情况下会失败或者在病态情况下需要指数运行时间。

更一般地说：在一个图中给定两个不相交的顶点集，是否存在一个多项式时间算法来找到所有从第一个集合中的一个顶点到第二个集合中的一个顶点之间的简单路径上的顶点？

（如果有一个非常明显的解决方案，请原谅我的孤陋寡闻。这当然应该存在。）

- Aaron Rotenberg

你可以尝试修改 Floyd-Warshall 算法来解决第一个问题。它的时间复杂度是 n^3。在遍历过程中，记录下所有经过的顶点，然后查看哪些其他顶点同时与目标和源点之间存在路径。 - Jan Gorzny

你应该考虑将这种问题发布到新的计算机科学 StackExchange 网站上。 - hugomg

@JanGorzny- 那种方法的问题在于，这只会告诉你是否存在一个通过这些节点的子图中的*最短路径。我可能有一个节点在某个子图中的非最短路径上，而被跳过。 - templatetypedef

@templatetypedef 但是你可以遍历所有节点（假设你有一个列表，在节点大小的线性时间内），并检查每个节点是否存在到两个指定节点的某些最短路径（你可以排除至少其中一条路径使用这两个指定节点的情况，尽管这需要存储大量信息）。最终我承认这不是完美的，但我认为这可能是一个起点！ - Jan Gorzny

当然，任何多项式时间解决两端问题的方法都意味着可以多项式时间解决N端问题，因为您只需将两个集合中所有顶点对的结果合并即可。我的问题只要求多项式时间，而不是渐近最优。虽然可能存在更快的N端算法。 - Aaron Rotenberg

2个回答

1

您介意使用概率解决方案吗？也就是说，它不能保证找到所有的顶点，但通常第一次尝试就能找到大部分，而在2或3次尝试后几乎肯定能找到。

如果您可以接受这个方案，请随机分配每条边的电阻，并求解每个节点的电压，如果将源设置为1的电压，汇设置为0的电压。任何两个连接节点电压不同的边显然都在简单路径上（路径很容易构造，只需从一端开始按升序遍历电压，从另一端开始按降序遍历）。两个连接节点电压相同的边极不可能在简单路径上，尽管理论上可能会发生。

多次使用随机分配的电阻集合重复此过程，您几乎肯定会找到所有在简单路径上的边。（您没有证明这个答案，但错误的概率非常小。）

当然，一旦您知道了所有在简单路径上的边，获取所有在简单路径上的顶点就非常容易了。

更新

我相信以下内容是正确的，但没有证据。假设我们取一组电阻并计算电压。对于每条在简单路径中的边，都有另一条边（可能是同一条边），只要改变那条边的电阻就会导致第一条边上的电压发生变化。如果是这样，那么可以在多项式时间内识别简单路径中的每条边。

直观上来看，这对我来说是有道理的，但我不知道如何证明它。

- btilly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bennos · Accepted Answer

这里提供了一种线性时间的确定性解决方案。如果两个端点（我们称其为a和b）之间不存在边，则插入一条边可以将问题转化为查找任何简单环穿过a和b的最大顶点集的问题。您可以自己验证，这样的集合对应于包含a和b的最大子图，不能通过删除任何节点来断开连接（也称为双联通分量）。此页面介绍了概念和Hopcroft和Tarjan的经典线性时间（基于DFS的）算法来识别所有双联通分量（您只需要包含a和b的那个）。

针对您关于两个集合之间简单路径的第二个问题，您可以创建一个新的顶点a，它与A中的所有顶点都有边，以及一个顶点b，它与B中的所有顶点都有边，然后解决您针对a和b的第一个问题即可。