1

给定facebook上的两个人X和Y，有没有办法（有效或不有效）找到这样定义的数字。如果 X 和 Y 是朋友，则 1. 否则，如果 X 有一个朋友是 Y 的朋友，则 2. 否则，如果 X 是朋友 Y 的朋友的朋友，则 3. 等等。

澄清：
执行此操作的程序将 facebook 上任意两个人的姓名 X 和 Y 作为输入。然后如果他们在彼此的好友列表中，程序输出 1。
如果不是，但他们都有一个共同的朋友，则输出 2。
如果他们不是朋友，也没有共同的朋友，但每个人都有一个朋友是朋友，那么输出 3.
如果不是，但是 X 有一个朋友 x，Y 有一个朋友 y，并且 x 和 y 有一个共同的朋友，那么输出 4. 等等...

如果好友之间没有联系，则输出0。

4

1 回答 1

5

你正在寻找一种叫做分离度的东西。

填写每个案例的唯一方法是列出尽可能多的朋友的朋友的朋友......基本上尽可能接近您的应用程序允许覆盖 Facebook 图表。然后，您将 Facebook 用户表示为图上的节点并计算从 A 到 B 的路径。因此，除非您拥有来自 Facebook 的所有数据，否则对于一个完整的工作应用程序来说实际上是不可能的。假设你这样做了，你可以只使用Dijkstra's algorithm。

对于淡化版本，您可以只检查您的朋友，用它制作图表并找到任何大于 1 的度数。

您将需要查询，例如

  • me/friends用于初始化图的构建

  • SELECT uid1, uid2 FROM friend WHERE uid1 = ' + uid1 + ' AND uid2 IN (SELECT uid2 FROM friend WHERE uid1=me())用于查找您的哪些朋友在网络中连接

如果您只需要它来显示当前用户的用户路径，JS SDK http://www.fbrell.com/saved/12bd86306fe69a2af6134fe2a9e645e3中有一个隐藏插件

<fb:degrees href="http://facebook.com/zuck">

分离度

于 2012-11-11T22:07:03.547 回答