分离度 [英] Degree of separation

问题描述

有没有办法（有效或不高效）找到给定两个人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有一个freind 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.

推荐答案

您正在寻找一种名为分离度的内容。

填写每个案例的唯一方法是列出朋友的朋友的朋友的基本上与您的应用程序可以覆盖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.

您将需要查询，例如

• 我/朋友建立图表

SELECT uid1，uid2 FROM friend WHERE uid1 ='+ uid1 +'AND uid2 IN（SELECT uid2 FROM friend

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屋！