发现失联多年好友的功能是怎么实现？

作者 | Cooper Song

责编 | 伍杏玲

出品 | 程序人生（ID：coder_life）

近期晚上失眠比较多，偶然发现在微博里打开别人的关注/粉丝列表可以找到可能感兴趣的人，点进去一看还果然都是小学、初中、高中时期的同学，我就开始思索背后的算法是怎么实现的，于是便有了这篇文章。

 

关注粉丝信息用什么数据结构存储呢？

 

当然是用图啦！我单方面关注了你我就成为了你的粉丝，但是你还不是我的粉丝，因此关注/粉丝关系需要使用有向图（Directed Graph）来存储，注意不一定是有向无环图（Directed Acyclic Graph，简称DAG），因为可能出现下图所示的我关注了你，你关注了他，他又关注了我这样的三角关系。

确定使用有向图这种数据结构后，还需确定采用何种方式存储，图的主流存储方式就两种，邻接矩阵和邻接表。由于微博或其他社交网络任意用户相互之间产生关注关系的并不多，采用邻接矩阵存储会耗费大量的空间，因此我们采用邻接表来存储，可以将某用户关注的人放在一条链表里接到该用户上，粉丝也放在一条链表里接到该用户上，当然链表也可以改为具备自动扩容功能的动态数组。

//结构体定义

struct node

{

    vector follows;

    vector followers;

    vector unionSet;

};

//所有用户

node user[MAX_USER_NUM];

动态数组follows中存储的是某用户关注的人；followers存储的是某用户的粉丝；unionSet存储的是follows集和followers集的并集，表示与某用户有“认识”关系的人，可以在该用户关注/取消关注别人或者别人关注/取消关注该用户时自动插入/删除，也可以用到的时候利用follows集和followers集求交集。

如何表示“认识”这种关系？

 

这里我们认为，我的关注与我的粉丝，都与我存在“认识”或者”感兴趣“的关系。因此我们可以对关注的人follows与粉丝followers取一个并集放到一个新的关系人数组unionSet。

取并集算法有两种，一种的时间复杂度是O(m*n)，比较暴力也比较容易理解；另一种的时间复杂度是O(m+n)，利用了哈希算法。

取并集算法1（暴力）

vector getUnion(vector follows,vector followers)

{

    vector ret=followers;

    int len1=follows.size();

    int len2=followers.size();

    for(int i=0;i2->3->6->5
 
 
1->3->2->5
 
 
1->3->5
 
 
1->3->6->5
 
 
这表明我与用户5一定有着千丝万缕的联系。
 
 
然而这种算法的时间复杂度却决于全部顶点的度的大小以及两名用户之间经过的中间用户的个数，如果中间用户过多，则在递归的时候就有可能爆栈导致系统崩溃。
 
 
除了时间复杂度和爆栈的问题，如果看到问题的本质，其实该算法也摆脱不了六度空间的影响。比如我在用户5的好友列表中再加入一个用户7，用户7就只有用户5这一个好友，因此到达用户7的路径数与到达用户5的路径数一样，然而用户1到达用户7至少也要通过2个中间人，其关联已经不大了。
 
 
 
 
 
 
 
可行的方案一
 
 
 
 
 
从目前看来最可行的方案就是进行好友列表比对取交集，按照交集中元素的个数按照从大到小排序。在观察了多种情况后我发现，给我推荐的可能感兴趣的人下面都有一行提示某某某也关注了他/她，而某某某正是我的好友。原来微博的兴趣推荐算法并没有那么高大上，应该是与QQ的共同好友一样。与QQ唯一的区别就是，微博有两个集合，一个是关注的人，一个是粉丝。
 
 
求交集同样有两种算法，与求并集类似，一个暴力，时间复杂度是O(m*n)；另一个哈希，时间复杂度是O(m+n)。
 
 
取交集算法1（暴力）
 
 
vector getInterp(vector myFriends,vector yourFriends)

{

    int len1=myFriends.size();

    int len2=yourFriends.size();

    for(int i=0;i