求一道关于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的挑出来,当然这个图应该是稠密图,用邻接矩阵吧,一般来说。