Aar*_*erg 11 language-agnostic algorithm graph breadth-first-search depth-first-search
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间,因为顶点之间可能存在指数个简单路径.但是,如果我们只对两个端点之间的至少一条简单路径上的顶点感兴趣呢？
那就是:给定一个无向图和两个不同的顶点,是否有一个多项式时间算法,它找到位于两个顶点之间的至少一条简单路径上的每个顶点？这与连接不同; 死胡同和死胡同被排除在外.但是,分支和连接路径是允许的.
我发现编写一个看起来像是解决了这个问题的算法非常容易,但在某些情况下要么失败,要么在病态情况下需要指数运行时间.
更一般地说:给定图中两个不相交的顶点集,是否存在多项式时间算法,该算法找到位于从一个集合中的顶点到另一个集合中的顶点的简单路径上的所有顶点？
(请原谅我,如果有一个非常明显的解决方案.当然感觉应该有.)
ben*_*nos 14
这是线性时间确定性解决方案.在两个末端顶点之间插入一条边(让我们称之为a和b),如果这样的边不存在,则将问题转化为找到最大的顶点集v的问题,该顶点集位于通过a和湾 你可以说服自己这样一个集合对应于包含a和b的最大子图,它不能通过删除任何节点(也称为双连通组件)来断开连接.本页描述了Hopcroft和Tarjan的概念和经典线性时间(基于DFS)算法,以识别所有双连通组件(您只需要包含a和b的组件).
关于两个集合之间的简单路径的第二个问题(让我们称之为A和B)可以通过创建一个新的顶点a,边缘到A中的所有顶点,以及一个顶点b,边缘到B中的所有顶点,可以简化为第一个问题.然后解决你的第一个问题a和b.