请教好友链的算法

大家都知道六度空间理论:通过六个人你就能够认识任何一个陌生人

现在有这么一个SNS网站,用户数量已经足够大,每个用户跟部分认识的人之间已经建立了好友关系,请问怎样计算出两两陌生人之间的好友链,比如A的好友里有B,B的好友里有C,C的好友里有D,则A跟D的好友链是A->B->C->D,

请高效的算法,并且使得到的好友链尽量短

评论 (0)链接2012-02-15 

每个人作为一个点存在,点与点之间进行连接,其实就是一个图,只是这个图是否是有向,是否是有权需要根据需要分析一下。
1: 如果两个人存在好友关系,且A好友里有B,B好友里有A,那就是无向的,否则就是有向的。
2: 熟识程度,A与B的关系是家庭关系,A与C是同学关系,那么可以认为A与B之间的熟悉程度高于A与C之间的熟悉程度。

简单点处理,不考虑熟识程度,关系只是归结于联系(好友),没有强弱之分,且认为这种联系是双向的(也就是无向的),那这个问题就归结为一个简单的无向无权图的最短路径问题,广度优先类的算法应该比较合适,例如经典的Dijkstra算法。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-02-16

有向图的最短路径方案。有现成的算法!

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-02-19

我比较好奇如何设计这种相关的存储结构,采用什么数据库能够满足如此大数据量的需求,还能高效的存取、计算出好友链,求解答,谢谢!

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2013-12-05
德问是一个专业的编程问答社区,请 登录注册 后再提交答案