判断是否存在从顶点u到w经过v的路径

Question

给定一个无向图 G = (V, E)，使得 u、v、w 是 G 中的一些边。

描述一个算法来判断是否

"如果有一条从u到w的路径经过v"

下面给出了使用 DFS 的简单算法：

bool checkFunction(){

  graph g; // containing u, w, v
  dfs(v);

  if(isVisited(u) && isVisited(w))
    return true;
  else
    return false;
   
}

对于上述算法，

时间复杂度：O(V+E)
space 复杂度：O(V)

但是我们可以降低时间复杂度吗？

Answer 1

一种简单的方法是找到从 u 到 w 的所有路径，然后查看 v 是否存在于其中一个集合中。

或者只看是否存在从u到v的路径以及是否存在从v到w的路径

Answer 2

从 u 开始进行 BFS。当你找到 v.

时停止它

现在，从 v 开始进行 BFS。当你找到 w 和 return true.

时停止它

如果在第一个BFS中找不到v或在第二个BFS中找不到w，则表示没有从u到w的路径通过通过 v 并且您可以停止 returning false.

复杂度：O(|V| + |E|)

Answer 3

没有更多的限制，没有任何不明显的可用优化。

路径存在当且仅当 u、v 和 w 在同一个连接中零件。这可以很容易地确定，方法是运行对任何一个进行 BFS 或 DFS，看看它是否找到另外两个。

对于某些图，当路径不存在并且其中一个顶点位于小型连接组件中时，有机会做得更好。你可以从最初的 3 个顶点做一个 BFS，当你发现一个新的顶点时，记住它来自哪个源。当您发现从 u 顶点到 v 顶点的冗余边时，您也会发现连接。如果在连接所有 3 个源之前，您运行从任何一个源的边缘出来，那么您可以停止，因为您知道该顶点是孤立的。

Answer 4

由于图是无向的，只需从w开始做一个BFS。

这确保如果找到路径 w->...->u 和 w->...->v，还有一条路径 v->...->w->...->u，这也是具有这些限制的最短路径

Answer 5

注意： 这个 post 没有提供问题的解决方案 posted，但它确实提供了一些关于常见错误的信息边解决此类问题边制作。

(这个post也假定路径不允许重复的顶点。如果你删除这个约束，这个问题可以很容易地解决，找到一条从u到v的路径，以及一条从v到w和只需连接这 2 条路径以获得从 u 到 w 通过 v 的 walk。这可以通过运行 BFS 一次从 u 一次从 v)

来实现

不正确。

编辑：
下面的反例是不正确的，请参阅史蒂夫的评论。在这个之后我又提供了一个反例。
考虑一个反例。
V = {u, v, w, x}
E = {{u,v}, {u,w}, {u,x}, {v,x}, {w,x}}
那么，路径 (u,v,x,w) 是有效路径。
现在假设我们在 w 上应用 BFS，我们从 w 到 u 和 w 到 v 的相应路径（不是唯一的）将是 (w,u) 和 (w, u, v)
现在，“路径”(v,u,w,u) 有一个重复的节点 u，所以它不是路径。

另一个反例：
考虑 V = {u,v,w,x,y,z} E = {{u,x}, {v,x}, {x,w}, {v,y}, {y,z}, { z,w}}
来自 w 的 BFS 树将具有边 {{w,x}, {w,z}, {x,u}, {x,v}}（我们将 u,v 视为汇）
这给出了无效的“路径”{u,x,w,x,v}

也不正确。

A path exists iff u, v, and w are in the same connected component.

考虑一个线图{w, u, v}，那么这3个都在同一个连通分量中，但是没有从u到w的路径经过v

这个问题（对于无向图）也有说明here（见问题 7），我认为这是一个有信誉的来源，所以我们可以安全地假设确实存在一个有效的算法。
This 还论证了解决方案的存在，并提供了算法。
对于有向图，这是 "hard" problem.

判断是否存在从顶点u到w经过v的路径

Determine whether there is a path from vertex u to w passing through v

algorithm

graph

path

ford-fulkerson