首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求一道关于QQ的算法?解决方法

2012-03-16 
求一道关于QQ的算法?查找自己N个qq好友都拥有的好友。试试这个。这道题有什么好的算法不,除了穷举,我的思想

求一道关于QQ的算法?
查找自己N个qq好友都拥有的好友。
试试这个。

这道题有什么好的算法不,除了穷举,我的思想是用图的算法来实现。。。

[解决办法]
遍历图的顶点,如果度为N及以上,再判断其邻接顶点是否自己的那N个好友。
[解决办法]
图的邻接矩阵,遍历自己N个好友的邻接向量,选择好友最少的,和其他的逐个比较,这样比较的次数应该比较少。如果N非常大,邻接矩阵用稀疏矩阵存储。
[解决办法]
若各个成员及其好友的信息均存放于数据库中,可利用SQL语句进行查询。
(在另外一个帖子里面看见一位大牛这么干的因此深受启发)
假设有以下的关联表存放好友信息
Create FriendShip (SourceQQ varchar(20), FriendQQ varchar(20)),
该表中的每一条记录都表示某个FriendQQ是SourceQQ的朋友

现在把所有的QQ朋友关系都填到这个表中,然后

==============================================================
指定某一个特定的QQ号码"A",要找出A的N个朋友共同的朋友(除了A自己外)
Select BaseFriend.SourceQQ as SourceQQ, FriendOfFriend.FriendQQ as IndirectFriendQQ 
From FriendShip BaseFriend
join FriendShip FriendOfFriend on FriendOfFriend.SourceQQ=BaseFriend.FriendQQ and FriendOfFriend.FriendQQ<>BaseFriend.SourceQQ
Where BaseFriend.SourceQQ="A"
group by BaseFriend.SourceQQ, FriendOfFriend.FriendQQ
having count(1)>=N

==============================================================
找出所有的"A B"组合,要求B为A的N个朋友共同拥有的朋友。
Select BaseFriend.SourceQQ as SourceQQ, FriendOfFriend.FriendQQ as IndirectFriendQQ 
From FriendShip BaseFriend
join FriendShip FriendOfFriend on FriendOfFriend.SourceQQ=BaseFriend.FriendQQ and FriendOfFriend.FriendQQ<>BaseFriend.SourceQQ
group by BaseFriend.SourceQQ, FriendOfFriend.FriendQQ
having count(1)>=N

==============================================================
大概的思路是这么个样子,没有装数据库所以没法调试,效率什么的完全取决与数据库性能。
[解决办法]
从自己这个定点进行BFS,首先是访问N个好友,然后访问N个好友的好友,对每个定点设个度,对其遍历一次加一。然后把这些点中度大于等于N的挑出来,当然这个图应该是稠密图,用邻接矩阵吧,一般来说。

热点排行