文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

1 基本概念

頂點、邊
微信：A和B是好朋友，B也和A是好朋友，A和B之間有條邊。
入度：每個頂點鏈接的邊的個數=每個人好朋友的個數。
微博：A關注B，B不用關注A。從A到B有條邊，邊是有方向的。這樣的圖是有向圖。入度：有多條邊指向這個節點。出度：從這個頂點出發，有幾條邊。
QQ親密度：兩個人經常聊天，那親密度高。這就是帶權重的邊。

2 圖的存儲方式

2.1 鄰接矩陣

用二維數組存儲圖。
優點：表示簡單；存取速度快；便于做矩陣運算。
缺點：在無向圖中，只需要一半的空間即可，浪費空間。在稀疏圖中，節點數量很多，每個節點的邊的數量卻很少，造成空間浪費。

2.2 鄰接表

鄰接表很像一張哈希表。鏈表的部分可以使用高效的動態數據結構：紅黑樹、跳表、散列表、有序動態數組（數據有序排列的動態數組）。

3 微信如何存儲關系數據

我們先考慮一下微信用戶關系，我們希望有的操作是：
1 判斷用戶A是否是用戶B的好朋友。
2 能夠按照首字母排序用戶A的好朋友，且分頁獲取。
3 用戶A刪除用戶B為好友，同時B的好友列表中也沒有Ａ。

首先用鄰接表存儲微信用戶關系。因為這是一個稀疏圖。微信用戶幾億，每個人的好友最多也就500。
　　用戶A：用戶B->用戶C->用戶X
　　用戶B：用戶A->用戶H->用戶Z
　　…
判斷用戶A是不是用戶B的好朋友，只需要在用戶A的好友列表查找一下即可。好友列表可以用跳表存儲。因為跳表可以按照首字母排序。排序好的好友列表也可以提高查詢速度。第2個要求滿足了。

用戶A刪除好友用戶B，需要同時在用戶A的好友列表刪除B、用戶B的好友鏈表刪除A。跳表刪除操作時間復雜度O(logn)。

對于數據量小的情況可以存儲在內存。當用戶量多的時候，一臺機器就解決不了。可以使用哈希計算，將用戶好友列表分別存儲在不同的服務器。也可以使用外部存儲（關系型數據庫）存儲數據。

4 BFS and DFS

廣度優先搜索BFS和深度優先搜索DFS是最基本的搜索算法。
BFS是以起始點為圓心，一層一層由近及遠的訪問節點，形狀像波紋。

DFS是以起始點開始，一頭道走到目的地，然后再返回上一層選擇另外一條路，形狀像折線，像迷宮。

總結

以上是生活随笔為你收集整理的数据结构七——图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。