判断顶点 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)
• 空间复杂度：O(V)

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

Answer 1

注意：这篇文章没有提供所发布问题的解决方案，但它确实提供了一些有关解决此类问题时可能犯的常见错误的信息。

（这篇文章还假定路径，不允许重复顶点。如果删除此约束，这个问题可以很容易地从u寻找到v的路径解决，从v到w和刚刚串联这两个路径获得的路径走从 u 到 w 通过 v。这可以通过从 u 运行一次 BFS 和从 v 运行一次来​​实现）

amit 给出的答案是不正确的。

编辑：
下面的反例不正确，请参阅史蒂夫的评论。在这之后，我提供了另一个反例。
考虑一个反例。
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 视为sinks)
这给出了无效的“路径”{u,x,w,x,v}

马特的回答也是不正确的。

当 u、v 和 w 在同一个连通分量中时，路径存在。

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

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