用户a-用户B用户C-UserD-UserF

-

由连接用户知道对方

。

和我需要一个算法，这2个任务：

计算到UserY从UserX路径 有关UserX，计算出不超过3步之遥的所有用户。

有没有一种有效的解决方案？

修改

我的目的不是为了证明是正确的还是错误的，但计算结果实时在必要时。

另外，我觉得最前pressive方法是code，甚至假的。

再次编辑

我已经决定，这种工作必须内部数据库中进行，因此它必须是一个SQL的解决方案！

解决方案

再present用户该列表中的图

在每个用户都是一个节点 在没有任何两个用户，谁知道对方之间的边缘      计算到UserY从UserX路径   有关UserX，计算出不超过3步之遥的所有用户。   

这些问题都密切相关，相同的算法实际上是解决了他们两个。你可以把它的Dijkstra算法具有权重为1，所有的边或广度优先搜索。的

从本质上讲，从第一个节点，请访问其所有的亲戚;然后标记它们所访问，记录的最短路径的每个（最短路径，它们+你刚刚走过的边缘），并重复他们每个人。停止你到达目的地的问题＃1日后，停止在最短路径后> 3问题＃2。

这将在O（n）的时间运行。没有，有没有更快的方法。

最快的O（n）的算法六分离度可能会被发现的所有用户的设置1步距的 UserX 和 UserY 的，并发现这两个集合的交集。如果没有，那么从的 UserX 的添加的用户2步和相交;然后将用户添加2步距离的 UserY 的和交叉的;等多达3。

如果每个人平均有100个朋友，这可能需要寻找达到约 2020200用户，而不是在 1010十亿作为Dijkstra算法。在实践中，这些数字会小很多，因为往往两个朋友也是朋友与对方。

这是解决六程度的分离 （那些至今提到的）的，将在实际工作中。

UserA-UserB-UserC-UserD-UserF

Users connected by '-' know each other.

And I need an algorithm for these 2 tasks:

Calculate the path from UserX to UserY For UserX,calculate all users that is no more than 3 steps away.

Is there an efficient solution?

EDIT

My purpose is not to prove it right or wrong,but to calculate the result real time when necessary.

Plus,I think the most expressive way is code,even pseudo ones.

EDIT AGAIN

I've decided that this kind of job must be done inside database,so it must be a sql solution!

解决方案

Represent this list of users by a graph

Each user is a node There is an edge between any two users who know each other

Calculate the path from UserX to UserY For UserX,calculate all users that is no more than 3 steps away.

These questions are so closely related that the same algorithm actually solves both of them. You can call it "Dijkstra's algorithm with all edges having weight 1," or "breadth-first search."

Essentially, starting at the first node, visit all its relatives; then mark them all as visited, record the shortest path to each (the shortest path to them + the edge you just traversed), and repeat for each of them. Stop after you've reached your destination for Problem #1, stop after the shortest path is > 3 for Problem #2.

This will run in O(n) time. No, there is no faster way.

The fastest O(n) algorithm for six-degrees of separation would probably be finding the sets of all users 1-step away from UserX and UserY, and finding the intersection of those two sets. If none, then add the users 2-steps from UserX and intersect; then add users 2-steps from UserY and intersect; etc. up to 3.

If each person has an average of 100 friends, this could require looking at up to about 2,020,200 users, as opposed to the 1,010 billion for Dijkstra's algorithm. In practice, these numbers would be much smaller, since often two of your friends are also friends with each other.

This is the only method of solving six-degrees of separation (of those mentioned so far) that will work in practice.