在微網誌中，兩個人可以互相關注，在微信中，兩個可以互相加好友。那麼微網誌微信是如何存儲這些好友關系呢？
這就要用到資料結構：圖。實際上，涉及圖的算法有很多，也非常雜，比如圖的搜尋、最短路徑、最小生成樹、二分圖等等。
如何了解"圖"？
前面我講過樹的非線性的表資料結構，圖和樹比起來，這是一種更加複雜的非線性表結構。
我們知道，樹中的元素我們成位節點，圖中的的元素我們就叫做頂點（vertex）。從下面圖中可以看出來，圖中的一個頂點可以與任意其他頂點建立連結關系。我們把這種建立的關系叫作邊。
拿微信做為例子，我們可以把每個使用者看作一個頂點。如果兩個使用者互相加好友，那麼就在兩者之間建立一條邊。是以整個微信的好友關系就可以用一張圖來表示。其中每個使用者有多少好友，對應到圖中，就叫做頂點的度（degree），就是跟頂點相連接配接邊的條數。
實際上，微網誌跟微信的社交關系還有點不一樣，微網誌是單向關注的，也可以互相關注，也就是說使用者A關注了B,但B可以不關注A。那我們如何用圖表示這種關系呢？
我們可以把剛剛講的圖結構稍微改造一下，引入邊的"方向"，的概念。
如果使用者 A 關注了使用者 B，我們就在圖中畫一條從 A 到 B 的帶箭頭的邊，來表示邊的方向。如果使用者 A 和使用者 B 互相關注了，那我們就畫一條從 A 指向 B 的邊，再畫一條從 B 指向 A 的邊。我們把這種邊有方向的圖叫作“有向圖”。以此類推，我們把邊沒有方向的圖就叫作“無向圖”。
我們剛剛講過，無向圖中有“度”這個概念，表示一個頂點有多少條邊。在有向圖中，我們把度分為入度（In-degree）和出度（out-degree）
頂點的入度，表示有多少條邊指向這個頂點；頂點的出度，表示從該頂點出發有多少條邊指向其他頂點。對應到微網誌的例子中就是：入度表示有多少 粉絲，出度表示關注了多少人。
前面講到了微信、微網誌、無向圖、有向圖，現在我們再來看另一種社交軟體：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的鄰接表。逆鄰接表的處理方式也一樣。當要查詢頂點與頂點關系的時候，我們就利用同樣的雜湊演算法，先定位頂點所在的機器，然後再在相應的機器上查找。
除此之外，我們還有另外一種解決思路，就是利用外部存儲（比如硬碟），因為外部存儲的存儲空間要比記憶體會寬裕很多。資料庫是我們經常用來持久化存儲關系資料的，是以我這裡介紹一種資料庫的存儲方式。
我用下面這張表來存儲這樣一個圖。為了高效地支援前面定義的操作，我們可以在表上建立多個索引，比如第一列、第二列，給這兩列都建立索引。