加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
微博、微信、LinkedIn 這些社交軟件我想你肯定都玩過吧。在微博中，兩個人可以互相關注；在微信中，兩個人可以互加好友。那你知道，如何存儲微博、微信等這些社交網絡的好友關係嗎？
這就要用到我們今天要講的這種數據結構：圖。實際上，涉及圖的算法有很多，也非常複雜，比如圖的搜索、最短路徑、最小生成樹、二分圖等等。我們今天聚焦在圖存儲這一方面，後面會分好幾節來依次講解圖相關的算法。
如何理解“圖”？
我們前面講過了樹這種非線性表數據結構，今天我們要講另一種非線性表數據結構，圖（Graph）。和樹比起來，這是一種更加複雜的非線性表結構。
我們知道，樹中的元素我們稱為節點，圖中的元素我們就叫作頂點（vertex）。從我畫的圖中可以看出來，圖中的一個頂點可以與任意其他頂點建立連接關係。我們把這種建立的關係叫作
邊（edge）。 我們生活中就有很多符合圖這種結構的例子。比如，開篇問題中講到的社交網絡，就是一個非常典型的圖結構。
我們就拿微信舉例子吧。我們可以把每個用戶看作一個頂點。如果兩個用戶之間互加好友，那就在兩者之間建立一條邊。所以，整個微信的好友關係就可以用一張圖來表示。其中，每個用戶有多少個好友，對應到圖中，就叫作頂點的度（degree），就是跟頂點相連接的邊的條數。
實際上，微博的社交關係跟微信還有點不一樣，或者說更加複雜一點。微博允許單向關注，也就是說，用戶 A 關注了用戶 B，但用戶 B 可以不關注用戶 A。那我們如何用圖來表示這種單向的社交關係呢？
我們可以把剛剛講的圖結構稍微改造一下，引入邊的“方向”的概念。
如果用戶 A 關注了用戶 B，我們就在圖中畫一條從 A 到 B 的帶箭頭的邊，來表示邊的方向。如果用戶 A 和用戶 B 互相關注了，那我們就畫一條從 A 指向 B 的邊，再畫一條從 B 指向 A 的邊。我們把這種邊有方向的圖叫作“有向圖”。以此類推，我們把邊沒有方向的圖就叫作“無向圖”。
我們剛剛講過，無向圖中有“度”這個概念，表示一個頂點有多少條邊。在有向圖中，我們把度分為入度（In-degree）和出度（Out-degree）。
頂點的入度，表示有多少條邊指向這個頂點；頂點的出度，表示有多少條邊是以這個頂點為起點指向其他頂點。對應到微博的例子，入度就表示有多少粉絲，出度就表示關注了多少人。
前面講到了微信、微博、無向圖、有向圖，現在我們再來看另一種社交軟件：QQ。
QQ 中的社交關係要更復雜的一點。不知道你有沒有留意過 QQ 親密度這樣一個功能。QQ 不僅記錄了用戶之間的好友關係，還記錄了兩個用戶之間的親密度，如果兩個用戶經常往來，那親密度就比較高；如果不經常往來，親密度就比較低。如何在圖中記錄這種好友關係的親密度呢？
這裡就要用到另一種圖，帶權圖（weighted graph）。在帶權圖中，每條邊都有一個權重（weight），我們可以通過這個權重來表示 QQ 好友間的親密度。
關於圖的概念比較多，我今天也只是介紹了幾個常用的，理解起來都不復雜，不知道你都掌握了沒有？掌握了圖的概念之後，我們再來看下，如何在內存中存儲圖這種數據結構呢？
鄰接矩陣存儲方法
圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix）。
鄰接矩陣的底層依賴一個二維數組。對於無向圖來說，如果頂點 i 與頂點 j 之間有邊，我們就將 A[i][j] 和 A[j][i] 標記為 1；對於有向圖來說，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就將 A[i][j] 標記為 1。同理，如果有一條箭頭從頂點 j 指向頂點 i 的邊，我們就將 A[j][i] 標記為 1。對於帶權圖，數組中就存儲相應的權重。
用鄰接矩陣來表示一個圖，雖然簡單、直觀，但是比較浪費存儲空間。為什麼這麼說呢？
對於無向圖來說，如果 A[i][j] 等於 1，那 A[j][i] 也肯定等於 1。實際上，我們只需要存儲一個就可以了。也就是說，無向圖的二維數組中，如果我們將其用對角線劃分為上下兩部分，那我們只需要利用上面或者下面這樣一半的空間就足夠了，另外一半白白浪費掉了。
還有，如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊並不多，那鄰接矩陣的存儲方法就更加浪費空間了。比如微信有好幾億的用戶，對應到圖上就是好幾億的頂點。但是每個用戶的好友並不會很多，一般也就三五百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的存儲空間都被浪費了。
但這也並不是說，鄰接矩陣的存儲方法就完全沒有優點。首先，鄰接矩陣的存儲方式簡單、直接，因為基於數組，所以在獲取兩個頂點的關係時，就非常高效。其次，用鄰接矩陣存儲圖的另外一個好處是方便計算。這是因為，用鄰接矩陣的方式存儲圖，可以將很多圖的運算轉換成矩陣之間的運算。比如求解最短路徑問題時會提到一個Floyd-Warshall 算法，就是利用矩陣循環相乘若干次得到結果。
鄰接表存儲方法
針對上面鄰接矩陣比較浪費內存空間的問題，我們來看另外一種圖的存儲方法，鄰接表（Adjacency List）。
我畫了一張鄰接表的圖，你可以先看下。乍一看，鄰接表是不是有點像散列表？每個頂點對應一條鏈表，鏈表中存儲的是與這個頂點相連接的其他頂點。另外我需要說明一下，圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鏈表裡面，存儲的是指向的頂點。對於無向圖來說，也是類似的，不過，每個頂點的鏈表中存儲的，是跟這個頂點有邊相連的頂點，你可以自己畫下。
還記得我們之前講過的時間、空間複雜度互換的設計思想嗎？鄰接矩陣存儲起來比較浪費空間，但是使用起來比較節省時間。相反，鄰接表存儲起來比較節省空間，但是使用起來就比較耗時間。
就像圖中的例子，如果我們要確定，是否存在一條從頂點 2 到頂點 4 的邊，那我們就要遍歷頂點 2 對應的那條鏈表，看鏈表中是否存在頂點 4。而且，我們前面也講過，鏈表的存儲方式對緩存不友好。所以，比起鄰接矩陣的存儲方式，在鄰接表中查詢兩個頂點之間的關係就沒那麼高效了。
在散列表那幾節裡，我講到，在基於鏈表法解決衝突的散列表中，如果鏈過長，為了提高查找效率，我們可以將鏈表換成其他更加高效的數據結構，比如平衡二叉查找樹等。我們剛剛也講到，鄰接表長得很像散列。所以，我們也可以將鄰接表同散列表一樣進行“改進升級”。
我們可以將鄰接表中的鏈表改成平衡二叉查找樹。實際開發中，我們可以選擇用紅黑樹。這樣，我們就可以更加快速地查找兩個頂點之間是否存在邊了。當然，這裡的二叉查找樹可以換成其他動態數據結構，比如跳錶、散列表等。除此之外，我們還可以將鏈表改成有序動態數組，可以通過二分查找的方法來快速定位兩個頂點之間否是存在邊。
解答開篇
有了前面講的理論知識，現在我們回過頭來看開篇的問題，如何存儲微博、微信等社交網絡中的好友關係？
前面我們分析了，微博、微信是兩種“圖”，前者是有向圖，後者是無向圖。在這個問題上，兩者的解決思路差不多，所以我只拿微博來講解。
數據結構是為算法服務的，所以具體選擇哪種存儲方法，與期望支持的操作有關係。針對微博用戶關係，假設我們需要支持下面這樣幾個操作：
- 判斷用戶 A 是否關注了用戶 B；
- 判斷用戶 A 是否是用戶 B 的粉絲；
- 用戶 A 關注用戶 B；
- 用戶 A 取消關注用戶 B；
- 根據用戶名稱的首字母排序，分頁獲取用戶的粉絲列表；
- 根據用戶名稱的首字母排序，分頁獲取用戶的關注列表。
關於如何存儲一個圖，前面我們講到兩種主要的存儲方法，鄰接矩陣和鄰接表。因為社交網絡是一張稀疏圖，使用鄰接矩陣存儲比較浪費存儲空間。所以，這裡我們採用鄰接表來存儲。
不過，用一個鄰接表來存儲這種有向圖是不夠的。我們去查找某個用戶關注了哪些用戶非常容易，但是如果要想知道某個用戶都被哪些用戶關注了，也就是用戶的粉絲列表，是非常困難的。
基於此，我們需要一個逆鄰接表。鄰接表中存儲了用戶的關注關係，逆鄰接表中存儲的是用戶的被關注關係。對應到圖上，鄰接表中，每個頂點的鏈表中，存儲的就是這個頂點指向的頂點，逆鄰接表中，每個頂點的鏈表中，存儲的是指向這個頂點的頂點。如果要查找某個用戶關注了哪些用戶，我們可以在鄰接表中查找；如果要查找某個用戶被哪些用戶關注了，我們從逆鄰接表中查找。
基礎的鄰接表不適合快速判斷兩個用戶之間是否是關注與被關注的關係，所以我們選擇改進版本，將鄰接表中的鏈表改為支持快速查找的動態數據結構。選擇哪種動態數據結構呢？紅黑樹、跳錶、有序動態數組還是散列表呢？
因為我們需要按照用戶名稱的首字母排序，分頁來獲取用戶的粉絲列表或者關注列表，用跳錶這種結構再合適不過了。這是因為，跳錶插入、刪除、查找都非常高效，時間複雜度是 O(logn)，空間複雜度上稍高，是 O(n)。最重要的一點，跳錶中存儲的數據本來就是有序的了，分頁獲取粉絲列表或關注列表，就非常高效。
如果對於小規模的數據，比如社交網絡中只有幾萬、幾十萬個用戶，我們可以將整個社交關係存儲在內存中，上面的解決思路是沒有問題的。但是如果像微博那樣有上億的用戶，數據規模太大，我們就無法全部存儲在內存中了。這個時候該怎麼辦呢？
我們可以通過哈希算法等數據分片方式，將鄰接表存儲在不同的機器上。你可以看下面這幅圖，我們在機器 1 上存儲頂點 1，2，3 的鄰接表，在機器 2 上，存儲頂點 4，5 的鄰接表。逆鄰接表的處理方式也一樣。當要查詢頂點與頂點關係的時候，我們就利用同樣的哈希算法，先定位頂點所在的機器，然後再在相應的機器上查找。
除此之外，我們還有另外一種解決思路，就是利用外部存儲（比如硬盤），因為外部存儲的存儲空間要比內存會寬裕很多。數據庫是我們經常用來持久化存儲關係數據的，所以我這裡介紹一種數據庫的存儲方式。
我用下面這張表來存儲這樣一個圖。為了高效地支持前面定義的操作，我們可以在表上建立多個索引，比如第一列、第二列，給這兩列都建立索引。
內容小結
今天我們學習了圖這種非線性表數據結構，關於圖，你需要理解這樣幾個概念：無向圖、有向圖、帶權圖、頂點、邊、度、入度、出度。除此之外，我們還學習了圖的兩個主要的存儲方式：鄰接矩陣和鄰接表。
鄰接矩陣存儲方法的缺點是比較浪費空間，但是優點是查詢效率高，而且方便矩陣運算。鄰接表存儲方法中每個頂點都對應一個鏈表，存儲與其相連接的其他頂點。儘管鄰接表的存儲方式比較節省存儲空間，但鏈表不方便查找，所以查詢效率沒有鄰接矩陣存儲方式高。針對這個問題，鄰接表還有改進升級版，即將鏈表換成更加高效的動態數據結構，比如平衡二叉查找樹、跳錶、散列表等。
閱讀更多 xiuxiuing 的文章
