<分区>
我正在实现一个由 100,000 多个节点组成的巨大有向图。我刚开始学 python，所以我只知道这两种搜索算法。如果我想找到任意两个节点之间的最短距离，哪一个会更有效率？还有其他我不知道的方法会更好吗？
谢谢你的时间
<分区>
我正在实现一个由 100,000 多个节点组成的巨大有向图。我刚开始学 python，所以我只知道这两种搜索算法。如果我想找到任意两个节点之间的最短距离，哪一个会更有效率？还有其他我不知道的方法会更好吗？
谢谢你的时间
最佳答案
BFS 和 DFS 确实还有其他几种替代方法。
一个足以计算最短路径的是:http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
Dijsktra 算法基本上是 BFS 算法的改编版，如果您的图是加权的，它比搜索整个图更有效。
就像@ThomasH 所说的那样，Djikstra 只在你有一个加权图时才有意义，如果每条边的权重都相同，它基本上默认回到 BFS。
如果在 BFS 和 DFS 之间做出选择，那么 BFS 更适合寻找最短路径，因为您在移动到更远距离的节点之前完全探索了节点的紧邻区域。
这意味着如果有一条大小为 3 的路径，它将在算法继续探索例如距离为 4 的节点之前进行探索。
使用 DFS 时，您没有这样的保证，因为您深入探索节点，您可以找到一条更长的路径，而该路径恰好较早地被探索过，并且您需要探索整个图以确保这是最短路径。
至于为什么你会被否决，大多数 SO 问题应该表明已经付出了一些努力来寻找解决方案，例如，有几个关于 DFS 与 BFS 的优缺点的相关问题。
下次尝试确保您已经进行了一些搜索，然后针对您的任何具体疑问提出问题。
关于python - 广度优先搜索还是深度优先搜索？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16710374/