Nee*_*raj 1 algorithm graph social-networking data-structures
我有一个包含数百万个节点的大图.我想检查节点'A'是否可以从节点'B'到达,少于4跳.如果可能的话,我想要最短的路径.哪个是解决此问题的最佳方法(或算法)？
请注意,如果图表未加权(正如您的问题中所示) - 简单而有效的BFS就足以找到从源到目标的最短路径.
此外,由于您只有一个源和一个目标 - 您可以应用双向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,第二个显然比第一个好得多.
(*)双向搜索的解释取自我发布的另一个答案