计算两个用户之间的社交距离

您如何编码一种有效的算法，该算法可以返回两个用户之间的社交“距离”。

例如，当您访问LinkedIn上的个人资料时，您可以看到您与用户之间的距离是多少。

->用户A是用户B的朋友-并且B是C的朋友。当A访问C时（距离为1）

该图非常庞大，所以我想知道它如何能够如此快速地执行。

我知道这个问题可能会结束，但是我真的认为这是一个编程/算法问题-因为我对这个概念感兴趣，所以我不会指定任何语言。

假设您没有到目标的距离的任何启发式函数，那么最佳的最佳解决方案是双向

BFS：

同时从源和目标进行BFS搜索：[BFS直到两者的深度均为1 ，直到两者的深度均为2，....]。

当找到位于两个BFS前端的顶点v时，该算法将结束。

：终止算法运行的顶点v将恰好在源和目标之间的中间。

在大多数情况下，此算法将产生比源BFS更好的结果（解释为什么比BFS更好），并且如果存在的话，肯定会提供答案。

假设源到目标的距离是k，分支因子是B[每个顶点都有B边]。

BFS将打开：1 + B + B^2 + ... + B^k顶点。

双向BFS将打开：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)顶点。

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

注意，该解决方案不需要将整个图形存储在内存中，它只需要实现一个函数：successor(v)该函数将返回一个顶点的所有后继者[从v开始的1步之内即可获得的所有顶点]。这样，仅2

+ 2B + ... +

2B^(k/2)应保存您打开的节点（如上所述）。为了进一步节省内存，您可以从一个方向使用迭代加深DFS而不是BFS，但是它将消耗更多时间。