查找一个节点是否可以从另一个节点到达的算法

Question

我有一个包含数百万个节点的大图。我想检查是否可以从节点“B”以少于 4 跳的方式访问节点“A”。如果可能的话，我想要最短的路径。解决此问题的最佳方法(或算法)是什么？

Answer 1

请注意，如果图表未加权(如您的问题所示)- 一个简单高效的 BFS将足以找到从源到目标的最短路径。

此外，由于您只有一个来源和一个单一目标 - 您可以应用 bi-directional BFS ，比 BFS 更高效。

算法思想:同时从源和目标进行 BFS 搜索:[BFS 直到深度为 1，直到深度为 2，....]。
当你找到一个顶点 v 时，算法将结束，它在两个 BFS 的前面。

算法行为:终止算法运行的顶点 v 将恰好位于源和目标之间的中间。
在大多数情况下，该算法将产生比来自源的 BFS 更好的结果 [解释为什么它比 BFS 更好]，并且肯定会提供答案，如果存在的话。

为什么它从源头上比 BFS 更好？
假设源到目标的距离为k，分支因子为B【每个顶点都有B条边】。
BFS 将打开:1 + B + B^2 + ... + B^k 个顶点。
双向 BFS 将打开:2 + 2B^2 + 2B^3 + .. + 2B^(k/2) 个顶点。

对于大的 B 和 k，第二个显然比第一个好得多。

---

(*) 双向搜索的解释摘自another answer I posted