2

我在 SO 和其他地方看到过文章，其中引用了以下方法来确定图中两个节点之间是否存在路径。我想知道是否有人比另一个更好？

  1. 广度优先搜索 -O(V + E)

  2. 深度优先搜索 -O(V + E)

  3. 使用不相交集- O(n log n)（不确定是否是O(n log n)）

所有这些方法是否适用于有向图和无向图、循环图和非循环图？

对其中一个有什么偏好吗？

4

2 回答 2

2

好吧，我绝对可以回答线性时间算法 - BFS、DFS 应该适用于所有类型的图（有向/无向、循环/非循环）。
想一想：从给定节点开始，它们将访问每个边和每个节点最大值一次，因此它们不受循环的影响。
他们将以不同的方式进行操作，BFS - “逐级”，DFS - 以一种贪婪的迷宫逃逸方式，但它们要么在某个点终止（路径存在），要么在遍历所有边缘和访问每个节点，它们将以否定结果终止。
“方向性”仅影响可到达的节点从给定的节点 A，但算法的实现（bfs 和 dfs）不知道图是否有向。

我不确定联合查找结构（您的最后一项具有不相交集的项目）是否会在有向图的情况下对您有所帮助。
Afaik，如果它们是相互可达的，Union-find则将（合并）节点a和b在一个集合中，即两者都有一条路径，a反之亦然b。
如果你在 and 之间有边，a -> b并且没有其他路径从to ，在这种情况下，根据Union-find数据结构将无法将它们不在一组中。，但显然 path ->存在。abba
ab

于 2013-11-18T22:27:38.477 回答
1

BFS 比 DFS 更好，因为它可以找到最短路径 [因此您可以更快地停止算法]。

对不相交集了解不多（很快就会读到），可能会更新我的答案。[根据我的阅读，它似乎比 BFS 更复杂，因为它用于查找图形的所有组件]。

您未提及的选项之一是考虑双向 BFS - 因此同时从开始和结束运行 BFS，并在两个搜索相遇时停止。但是，如果很可能不存在路径，并且 - 在循环图的情况下 - 只有当您保留对传入和传出边的引用时，它才会效率低下。

可以肯定：BFS 和 DFS 在无向、有向、循环和非循环上工作。

如果你愿意，你可以在这里和他们一起玩。

于 2013-11-18T22:15:23.480 回答