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

如何编写一个有效的算法来返回两个用户之间的社交“距离”。

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

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

该图很大，所以我想知道它如何执行得如此快。

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

假设你没有启发式函数 http://en.wikipedia.org/wiki/Heuristic_function关于到目标的距离，有效的最佳解决方案是双向 http://en.wikipedia.org/wiki/Bidirectional_search BFS http://en.wikipedia.org/wiki/Breadth-first_search:
算法思路：同时从源和目标进行 BFS 搜索：[BFS 直到两者的深度 1，直到两者的深度 2，....]。
当找到一个位于两个 BFS 前面的顶点 v 时，算法结束。

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

为什么从源头看它比 BFS 更好？
假设源到目标之间的距离是k，分支因子为B[每个顶点都有B边]。
BFS 将开放：1 + B + B^2 + ... + B^k顶点。
双向 BFS 将打开：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)顶点。

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

EDIT:
注意，该解决方案不需要将整个图存储在内存中，它只需要实现一个函数：successor(v)它返回一个顶点的所有后继[你可以到达的所有顶点，距离 v 1 步以内]。这样，只有您打开的节点[2 + 2B + ... + 2B^(k/2)如上所述]应存储。为了进一步节省内存，您可以使用迭代深化DFS http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search从一个方向，代替BFS，但会消耗更多的时间。