一：如何理解“圖”
1，圖和樹一樣都是非線性表數據結構，和樹不同的是圖是一種更加復雜的非線性表結構
2，樹中的元素稱之為節點，圖中的元素則稱之為頂點。
3，頂點可以與任意其他頂點建立關聯，這種建立的關系叫做邊，與頂點相連接的條數叫做頂點的度。
4，圖可以分為有向圖和無向圖兩種，有向圖的邊有方向。
5，在有向圖中，度可以分為入度和出度（Out-degree）
6，帶權圖：在帶權圖中，每條邊都有一個權重

二：鄰接矩陣存儲方法

1，圖最直觀的一種存儲方法是：鄰接矩陣（Adjacency Matrix），鄰接矩陣的底層依賴一個二維數組。

2，用鄰接矩陣來表示一個圖，雖然簡單，直觀，但是浪費存儲空間。
①：對于無向圖的二維數組中，如果將其對角線劃分為上下兩部分，那我們只需要利用上面或者下面這樣的一半的空間就足夠了，另一半白白浪費掉了。
②：若存儲的是稀疏圖（Sparse Matrix），即頂點很多，但每個頂點的邊并不多，那鄰接矩陣的存儲方法就更加浪費空間了。
3，用鄰接矩陣存儲的優點：
①：存儲方式簡單，直接，因為基于數組，所以在獲取兩個頂點的關系時，就非常高效。
②：其次是計算方便。因為，可以將很多圖的運算轉換成矩陣之間的運算。如求解最短路徑問題時會提到一個Floyd-Warshall算法，就是利用矩陣循環相乘若干次得到結果。
三：鄰接表存儲方法

1，鄰接表（Adjacency List）可以解決鄰接矩陣存儲方式比較浪費內存空間的問題
2，鄰接矩陣存儲起來比較浪費空間，但使用比較節省時間，鄰接表存儲與之相反。
如圖中，如果要確定是否存在從頂點2到頂點4的邊，就需要遍歷頂點2對應的鏈表，看那條鏈表中是否存在頂點4。但鏈表的存儲方式對緩存不友好。
3，我們可以將鄰接表中國的鏈表改成平衡二叉查找樹，實際開發中國還可選用紅黑樹。這樣可以快速查找兩個頂點之間是否存在邊了。

四：圖的應用
如何存儲微博，微信、QQ等社交網絡中的好友關系？

微博，微信是兩種“圖”，前者是有向圖，后者是無向圖。

QQ無向圖 權重親密度

數據結構是為算法服務的，所以具體選擇哪種存儲方法，與期望支持的操作有關系。針對微博的用戶關系，需要支持：
? 判斷用戶A是否關注了用戶B;
? 判斷用戶A是否是用戶B的粉絲
? 用戶A關注用戶B；
? 用戶A取消關注用戶B；
? 根據用戶名稱的首字母排序，分頁獲取用戶的粉絲列表；
? 根據用戶名稱的首字母排序，分頁獲取用戶的關注列表。

3 。因為社交網絡是一張稀疏圖，使用鄰接矩陣存儲比較浪費存儲空間，所以使用鄰接表來存儲。
4，但用一個鄰接表來存儲這種有向圖是不夠的，查找某個用戶關注了哪些用戶非常容易，但是如果想要知道某個用戶都被哪些用戶關注了，是非常困難的。因此，需要一個逆鄰接表。鄰接表中存儲了用戶的關注關系，逆鄰接表中存儲的是用戶的被關注關系。

對應到圖上，鄰接表中，每個頂點的鏈表中，存儲的就是這個頂點指向的頂點，逆鄰接表中，每個頂點的鏈表中，存儲的是指向這個頂點的頂點。

基礎的鄰接表不適合快速判斷兩個用戶之間是否是關注與被關注的關系。
因為我們需要按照用戶名稱的首字母排序，分頁來獲取用戶的粉絲列表或者關注列表，用跳表這種結構再合適不過了。這是因為，跳表插入、刪除、查找都非常高效，時間復雜度是 O(logn)，空間復雜度上稍高，是 O(n)。最重要的一點，跳表中存儲的數據本來就是有序的了，分頁獲取粉絲列表或關注列表，就非常高效。


1 內存中用鄰接表；
2 要持久化存儲就用數據庫
2 超大圖 并且涉及大量圖計算。用專業的圖數據庫

筆記整理來源： 王爭 數據結構與算法之美

總結

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

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