如何找到包含边e的从顶点x到顶点y的简单路径？
如何找到包含边e的从顶点x到顶点y的简单路径？
提问于 2022-01-03 21:21:35
所以我面对这个问题，我希望有人能帮助我。
给出了无向图G= (V，E)，两个顶点x，y和边e= (v，u)。
建议一种算法，以确定是否存在从x到y的包含边缘e的简单路径。
所以这里的重点是简单路径而不是规则路径，对于规则路径，使用BFS搜索从x到v的路径和从u到y的路径是一个简单的问题。
我知道这个问题可以用最大流的方法来解决，但是我不知道如何建立一个新的图来实现最大流算法，所以它能告诉我们是否达到了上述标准，我希望能得到帮助。
提前谢谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-01-03 21:37:58
不分边(边无关)
你可以在x和y处用+1源解最大流，在u和v处解-1汇。
移除边缘e，并将所有其他边缘设置为容量1。
一个简单的路径从x到y通过边e存在当且仅当你能在这个新的最大流问题中找到一个2的流。
不共享顶点(顶点无关，即简单路径)
将原始图中的每个顶点v[i]拆分为两个顶点，a[i]和b[i]。
对于原始的v[i]和v[j]之间的每个无向边，将有向边b[j]添加到a[i]，将b[i]添加到容量为1的a[j]。
此外，还为每个顶点a[i]添加一个容量为1的b[i]到b[i]的有向边缘。
其思想是流必须始终到达a[i]顶点，并在通过从a[i]到b[i]的容量1瓶颈之后从b[i]顶点离开。这确保每个顶点只能使用一次。
用这个新的图，继续处理与边无关的情况。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70571584
复制相关文章
相似问题
腾讯云开发者
