python - 广度优先搜索还是深度优先搜索？

Question

我正在实现一个由 100,000 多个节点组成的巨大有向图。我刚开始使用python，所以我只知道这两种搜索算法。如果我想找到任何两个节点之间的最短距离，哪一个会更有效？还有其他我不知道的方法会更好吗？

感谢您的时间

Answer 1

BFS 和 DFS 确实有其他几种替代方案。

一个足以计算最短路径的方法是：http ://en.wikipedia.org/wiki/Dijkstra 's_algorithm

Dijsktra 的算法基本上是对 BFS 算法的改编，如果你的图是加权的，它比搜索整个图更有效。

就像@ThomasH 所说，只有当你有一个加权图时，Djikstra 才有意义，如果每条边的权重相同，它基本上默认回到 BFS。

如果在 BFS 和 DFS 之间进行选择，那么 BFS 更适合于找到最短路径，因为您在移动到更远距离的节点之前完全探索了一个节点的附近。

这意味着，如果有一条大小为 3 的路径，它将在算法继续探索距离 4 处的节点之前进行探索。

使用 DFS，您没有这样的保证，因为您深入探索节点，您可以找到一条刚刚探索过的更长路径，您需要探索整个图以确保那是最短路径。

至于为什么你会被否决，大多数 SO 问题应该表明已经为寻找解决方案付出了一些努力，例如，有几个关于 DFS 与 BFS 的优缺点的相关问题。

下次尝试确保您已经进行了一些搜索，然后针对您的任何具体疑问提出问题。

Answer 2

看一下以下两种算法：

1. Dijkstra 算法- 单源最短路径
2. Floyd-Warshall 算法- 所有对最短路径

Answer 3

如果图上的边没有权重，则可以进行简单的广度优先搜索，您可以迭代地访问图中的节点并检查是否有任何新节点等于目标节点。如果边缘有权重，那么 DJikstra 算法和 Bellman-Ford 算法是您应该关注的东西，具体取决于您正在查看的预期时间和空间复杂性。

Answer 4

当你想找到最短路径时，你应该使用 BFS 而不是 DFS，因为 BFS 首先探索最近的节点，所以当你达到目标时，你肯定知道你使用了最短路径，你可以停止搜索。而 DFS 一次探索一个分支，因此当您达到目标时，您无法确定没有通过另一个更短的分支的另一条路径。

所以你应该使用 BFS。

如果您的图在其边缘上具有不同的权重，那么您应该使用 Dijkstra 算法，它是 BFS 对加权图的改编，但如果您没有权重，则不要使用它。

有些人可能会建议您使用 Floyd-Warshall 算法，但对于这么大的图来说，这是一个非常糟糕的主意。