挑战，如何实现六度分离算法？

挑战，如何实现六度分离算法？

用图形表示此用户列表

• 每个用户都是一个节点
• 彼此认识的两个用户之间都有优势

1. 计算从UserX到UserY的路径
2. 对于UserX，请计算距离不超过3步的所有用户。
   
   

这些问题密切相关，以至于同一算法实际上可以解决这两个问题。您可以将其称为 “所有边的权重为1的Dijkstra算法” 或 “宽度优先搜索”。

本质上，从第一个节点开始，拜访其所有亲戚；然后将它们标记为已访问，记录到它们的最短路径（到它们的最短路径+刚经过的边缘），并对每个重复。在到达问题1的目的地后停止，然后在问题2的最短路径>
3之后停止。

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

用于六度分离的最快O（n）算法 可能是找到距离 UserX 和 UserY 1步的所有用户的集合，并找到这两个集合的交集。如果不存在，则从
UserX 添加用户两步并相交；然后从 UserY 添加用户 两步 并相交；等等，最多3。

如果每个人都有一个平均的100个朋友，这可能需要寻找高达约 2020200的用户 ，而不是在 1010十亿
的Dijkstra算法。实际上，这些数字会小得多，因为您经常有两个朋友也是彼此的朋友。

这是解决六度分离 （到目前为止已提到 的分离度 ）的 唯一可行的方法。