-21

给定一个无向图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)

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

4

5 回答 5

14

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

（这篇文章还假设路径不允许重复顶点。如果删除此约束，则可以通过找到从 u 到 v 的路径和从 v 到 w 的路径并连接这两条路径来轻松解决问题从 u 到 w 通过 v。这可以通过从 u 和 v 运行一次 BFS 来实现）

阿米特给出的答案是不正确的。

编辑：
下面的反例不正确，请参阅史蒂夫的评论。在此之后，我提供了另一个反例。
考虑一个反例。
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），我认为这是一个有信誉的来源，所以我们可以安全地假设确实存在一个有效的算法。
这也证明了解决方案的存在，并提供了一种算法。
对于有向图，这是一个“难题”。

于 2020-11-20T13:11:13.940 回答
2

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

如果u、v和w在同一个连通分量中，则存在路径。这可以通过从任何一个运行 BFS 或 DFS 来查看它是否找到其他两个来轻松确定。

对于某些图，当路径不存在并且其中一个顶点位于一个小的连通分量中时，就有机会做得更好。您可以从最初的 3 个顶点执行单个 BFS，当您发现一个新顶点时，请记住它来自哪个源。例如，当您发现从u顶点到v顶点的冗余边时，您也会找到连接。如果在所有 3 个连接之前，任何一个源的边都用完了，那么您可以停止，因为您知道该顶点是孤立的。

于 2020-07-05T17:27:36.317 回答
1

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

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

于 2020-07-05T17:09:56.940 回答
1

从u. 当你发现时停止它v。

现在，从v. 当你找到w并返回时停止它true。

如果v在第一个 BFS 或w第二个 BFS 中都没有找到，则表示没有从u到w经过的路径v，您可以停止程序返回false。

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

于 2020-07-05T17:16:14.903 回答
1

由于图是无向的，只需从w.

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

于 2020-07-05T17:29:51.210 回答