作者 | 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;i
{
//用來標記關注的人是不是已經出現在粉絲中
bool found=false;
for(int j=0;j
{
if(follows[i]==followers[j])
{
//關注的人已經出現在粉絲中了
flag=true;
break;
}
}
if(!flag)
{
//關注的人沒有出現在粉絲中
ret.push_back(follows[i]);
}
}
return ret;
}
先將follows集（關注的人）全部放入並集中，再遍歷followers集（粉絲），對每一個粉絲檢查是否在follows集中出現過，如果沒有出現過，就將該粉絲加入並集。
取並集算法2（哈希算法）
vector getUnion(vector follows,vector followers)
{
vector ret;
int len1=follows.size;
int len2=followers.size;
//哈希表
unordered_map mp;
for(int i=0;i
{
mp[follows[i]]=true;
ret.push_back(follows[i]);
}
for(int i=0;i
{
if(!mp[followers[i]])
{
ret.push_back(followers[i]);
}
}
return ret;
}
先遍歷follows集（關注的人），將follows集中的所有元素都放入並集中，並用哈希表標記其是否已經存在於並集unionSet，再遍歷followers集（粉絲），對每一個粉絲檢查哈希值是否為true，若為true則表明該元素已經存在於並集unionSet，若為false說明目前並集unionSet中還沒有該元素，就將該元素加入並集，最後返回該並集。
並查集是否可行？
假如一共有MAX_USER_NUM個用戶，我們開一個數組f[MAX_USER_NUM]，將第i個元素的值初始化為i。
int f[MAX_USER_NUM];
for(int i=0;i
{
f[i]=i;
}
如果用戶a關注了用戶b或者用戶b關注了用戶a，則做如下操作。
f[findFather(a)]=findFather(b);
上述代碼的含義是將a的父結點的父結點設為b的父結點，所謂findFather函數，是一個返回父結點的函數。
findFather(int x)
{
if(x==f[x])
{
return x;
}
return f[x]=findFather(f[x]);
}
在並查集中，父結點與子結點是沒有層次關係的，如果a的父結點的父結點變成了b的父結點，那麼在調用findFather(a)查找a的父結點時其父結點也變成了b的父結點，即此時用戶a、用戶b、用戶c的父結點一致了。
要判斷所有用戶中任意兩名用戶是否可以通過他們的朋友認識，只需要做如下判斷。
bool haveConnection(int a,int b)
{
bool result;
if(findFather(a)==findFather(b))
{
result=true;
}
else
{
result=false;
}
return result;
}
這樣拉取我當前觀察用戶的關注的人與粉絲的並集unionSet中調用以上函數返回true的用戶，就得到了我可能感興趣的人的列表。
vector getInterestedList(vector unionSet,int myId)
{
vector ret;
int len=unionSet.size;
for(int i=0;i
{
if(haveConnection(myId,unionSet[i])
{
ret.push_back(unionSet[i]);
}
}
return ret;
}
並查集的本質是連通關係，連通圖的概念是一個圖的任意兩個頂點之間都能從一個頂點出發到達另一個頂點，因此當並查集中所有頂點的父節點都是同一個頂點時，該圖就是連通圖，只擁有一個連通分量；而如果所有頂點的父節點不只一個，則該圖不是連通圖，存在多個連通分量，父節點有幾個，連通分量就是幾。對並查集算法和圖論感興趣的朋友可以自行查資料瞭解。
並查集的確能夠準確得出兩個用戶之間是否存在關聯，但是我們必須面對的現實是一個非常有名的社交網絡領域的數學猜想——六度空間理論，也被叫做六度分割理論。其內容是你和任何一個陌生人之間所間隔的人不會超過6個。
舉個例子，你只需要6箇中間人，就可以與美國總統認識，這聽起來有些荒謬，卻也有幾分道理。例如，我有認識的親戚朋友在國外做生意，因為做生意認識了外國駐華大使，而外國駐華大使的上司就有可能與總統的下屬握過手或通過電話，而總統的下屬必然認識總統。因此如果我、我的親戚朋友、親戚朋友認識的外國駐華大使、總統的下屬與總統註冊了同一個社交網絡，雖然我沒有與總統直接建立關注與被關注的關係，通過並查集算法也可得知我與總統之間存在關係。
路徑統計法
如果配合並查集使用，先調用並查集的findFather函數可知兩個用戶之間是否存在通路，若存在通路，可以用深度優先搜索+迭代的算法統計出從一個用戶出發到另一個用戶的路徑數，路徑數越多則代表兩名用戶之間越存在著千絲萬縷的聯繫。
如上圖所示，我是用戶1，我正在查看用戶6的好友列表，用戶6有好友3和好友5，好友3已經是我的好友了，我聯繫上好友5共有6條路徑，分別是：
1->2->5
1->2->3->5
1->2->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 getIntersection(vector myFriends,vector yourFriends)
{
int len1=myFriends.size;
int len2=yourFriends.size;
for(int i=0;i
{
bool flag=false;
for(int j=0;j
{
if(myFriends[i]==yourFriends[j])
{
flag=true;
break;
}
}
if(flag)
{
ret.push_back(myFriends[i]);
}
}
return ret;
}
取交集算法2（哈希算法）
vector getIntersection(vector myFriends,vector yourFriends)
{
vector ret;
int len1=myFriends.size;
int len2=yourFriends.size;
unordered_map mp;
for(int i=0;i
{
mp[myFriends[i]]=true;
}
for(int i=0;i
{
if(mp[yourFriends[i]])
{
ret.push_back(yourFriends[i]);
}
}
return ret;
}
拉取可能感興趣的人
vector getInterestedList(vector myFriends,vector yourFriends)
{
vector ret;
int len=yourFriends.size;
for(int i=0;i
{
vector temp=getIntersection(user[yourFriends[i]].unionSet,myFriends);
if(temp.size>0)
{
ret.push_back(yourFriends[i]);
}
}
return ret;
}
可行的方案二
遍歷我所有好友的好友，用哈希表統計他們出現的次數，按出現次數從大到小排序後再剔除已經是我好友的用戶，就找到了我“可能認識的人”，並能得到我們之間有多少個共同好友。
//判斷某個id是不是我的好友
bool isFriend(int id,vector myFriends)
{
int len=myFriends.size;
for(int i=0;i
{
if(id==myFriends[i])
{
return true;
}
}
return false;
}
//獲取可能認識的人
vector getPossibleFriends(vector myFriends)
{
vector ret;
int len1=myFriends.size;
map mp;
//遍歷我所有的朋友
for(int i=0;i
{
//遍歷朋友的朋友
int len2=user[myFriends[i]].unionSet.size;
for(int j=0;j
{
mp[user[myFriends[i]].unionSet[j]]++;
}
}
//剔除我的好友
for(map::iterator it=mp.end-1;it>=mp.begin;it--)
{
pair temp=*it;
if(!check(temp.second,myFriends))
{
ret.push_back(temp.first);
}
}
return ret;
}
實際上，世間萬物皆有關係，皆為連接。連接並不是互聯網時代的產物，只是社交網絡的出現讓我們的連接更為密切了。若有錯誤之處還望大家多多包涵和指出，筆者也很想聽聽微博程序員到底是如何實現“可能感興趣的人”的功能的。
最近也是金三銀四面試季，面試中還是很喜歡問這種問題的，因為比較能體現候選人分析問題、解決問題、實現具體需求的能力。在日常軟件使用上，看到有趣的功能，多去思考其實現是一定沒有壞處的，縱使猜想的實現與實際的實現可能存在出入。
☞那個分分鐘處理10億節點圖計算的Plato，現在怎麼樣了？
☞每一節網課背後，硬核黑科技大曝光
☞數據庫激盪40年，深入解析PostgreSQL、NewSQL演進歷程
☞黑客用上機器學習你慌不慌？這7種竊取數據的新手段快來認識一下！
☞超詳細！一文告訴你SparkStreaming如何整合Kafka！附代碼可實踐
☞Libra的Move語言初探，10行代碼實現你第一個智能合約
