计算两个用户之间的社交距离
你将如何编码一个有效的algorithm，可以返回两个用户之间的社交“距离”。
例如，当您访问LinkedIn上的个人资料时，您可以看到您和用户之间的距离。
– >用户A是用户B的朋友 – 而B是C的朋友，当A将访问C（距离为1）
图表是巨大的，所以我想知道如何执行如此之快。
我知道这个问题可能会被closures，但我真的认为这是一个编程/algorithm问题 – 我不会指定任何语言，因为我对这个概念感兴趣。
假设您没有任何关于到目标的距离的启发式function ，那么有效的最佳解决scheme是双向 BFS ：
algorithm思想：从源和目标同时做一个BFSsearch：[BFS直到深度1在两个，直到深度2在两个，….]。
当find两个BFS的顶点v时，algorithm将结束。
algorithm行为 ：终止algorithm运行的顶点v恰好位于源和目标之间的中间。
在大多数情况下，这个algorithm在源自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来说，第二个显然比第一个好很多。
编辑：
注意，这个解决scheme并不需要将整个图存储在内存中，它只需要实现一个函数： successor(v)返回一个顶点的所有后继[你可以得到的所有顶点，从1开始]。 这样，只有你打开的节点[ 2 + 2B + ... + 2B^(k/2) ，如上所述]应该被存储。 为了进一步节省内存，您可以从一个方向使用迭代深化DFS ，而不是使用BFS，但会占用更多的时间。
我会假定这可以通过应用最短pathalgorithm来完成，比如将宽度优先search应用于graphics数据库 。 但是他们似乎把整个graphics存储在内存中，至less按照这个方式 。
我相信algorithm最终归结为graphics结构（节点和边）上某种forms的最短path。
编辑：改变algorithm按照评论。
首先图需要填充。 我不能说你如何从链接中获取graphics，可能会创build节点的BFS或DFS，发现graphics并build立链接。 要find任何两个最好的距离，就是从源节点创buildBFS，并在find目标时停止。 链接没有权重，我想，如果你不暗示其他的东西。
在这种情况下，当源节点不同时，您需要应用BFS来查找每对之间的距离。 否则，您可以实现Floyd Warshallalgorithm来获取所有源的所有目的地最短path，并且因为每个链路具有相同的权重，它将得到你想要的。 在这种情况下，一旦build成结构，对于任何来源和目的地，可以find最短的距离。 一个问题是networking总是在变化，因此需要重新处理。 所以BFS我认为会很好。
为了使处理速度更快，可以实现BFS并行运行。 查看非确定性并行广度优先searchalgorithm的devise和分析
