分离度 [英] Degree of separation
问题描述
有没有办法(有效与否)在 facebook 上给定两个人 X 和 Y，找到这样定义的数字.如果 X 和 Y 是朋友，则 1.否则，如果 X 有一个朋友是 Y 的朋友，则 2.否则，如果 X 是朋友 Y 的朋友的朋友，则 3.以此类推.
Is there a way, (efficiently or not), to find, given two persons X and Y on facebook, the number defined like this. If X and Y are friends then 1. Else if X has a friend who is a friend of Y, then 2. Else if X is a friend of a friend of a friend Y, then 3. etc.
澄清:
执行此操作的程序将 facebook 上任意两个人的姓名 X 和 Y 作为输入.然后如果他们在彼此的好友列表中，程序输出 1.
如果不是，但他们都有一个共同的朋友，则输出 2.
如果他们不是朋友并且没有共同的朋友，但每个人都有一个朋友是朋友，则输出3.
如果不是，但 X 有一个朋友 x，Y 有一个朋友 y，并且 x 和 y 有一个共同的朋友，则输出 4.等等...
clarification:
A program that does this, takes as input the names X and Y of any two persons on facebook.
Then if they are on eachothers friendslist, the program outputs 1.
If not, but they each have a common friend, then output 2.
If they are not friends and dont have a common friend, but each have a friend who are friends, then output 3.
If not, but X have a friend x, and Y have a freind y, and x and y have a common friend, then output 4. etc...
如果好友之间没有连接，则输出0.
And if there is no connection between friends, output 0.
推荐答案
您正在寻找一种叫做 分离度.
You are looking for something called the degree of separation.
填写每个案例的唯一方法是列出朋友的朋友的朋友的朋友......基本上是您的应用程序允许覆盖Facebook图表的数量.然后您将 Facebook 用户表示为图表上的节点并计算从 A 到 B 的路径.因此，除非您拥有 Facebook 的所有数据，否则不可能真正实现完整的工作应用程序.假设你这样做了，你可以只使用 Dijkstra 算法.
The only way to fill each case would be to list as many friends of friends of friends ... basically as close as your application allows to cover the Facebook graph. Then you represent the Facebook users as nodes on a graph and calculate the path from A to B. So it's not really possible for a complete working application unless you had all the data from Facebook. Assuming you did, you can just use Dijkstra's algorithm.
对于一个淡化的版本，你只能检查你的朋友，用它制作一个图表并找出任何大于 1 的度数.
For a watered down version, you can check only your friends, make a graph out of it and find any degrees greater than 1.
您将需要诸如
me/friends用于初始化图的构建
SELECT uid1, uid2 FROM friend WHERE uid1 = ' + uid1 + ' AND uid2 IN (SELECT uid2 FROM friend WHERE uid1=me()) 用于查找您的哪些朋友已连接内网
SELECT uid1, uid2 FROM friend WHERE uid1 = ' + uid1 + ' AND uid2 IN (SELECT uid2 FROM friend WHERE uid1=me()) for finding which of your friends are connected within the network
如果你只是需要这个来显示当前用户到用户的路径，JS SDK 中有一个隐藏的插件 http://www.fbrell.com/saved/12bd86306fe69a2af6134fe2a9e645e3
If you just need this to display a path to a user from the current user, there is a hidden plugin within the JS SDK http://www.fbrell.com/saved/12bd86306fe69a2af6134fe2a9e645e3
<fb:degrees href="http://facebook.com/zuck">
这篇关于分离度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
