圖

「圖 graph」是一種非線性數(shù)據(jù)結構，由「頂點 vertex」和「邊 edge」組成。我們可以將圖 G 抽象地表示為一組頂點 V 和一組邊 E 的集合。以下示例展示了一個包含 5 個頂點和 7 條邊的圖。

如果將頂點看作節(jié)點，將邊看作連接各個節(jié)點的引用（指針），我們就可以將圖看作是一種從鏈表拓展而來的數(shù)據(jù)結構。如圖 9-1 所示，相較于線性關系（鏈表）和分治關系（樹），網(wǎng)絡關系（圖）的自由度更高，從而更為復雜。

圖 9-1   鏈表、樹、圖之間的關系

9.1.1   圖常見類型與術語

根據(jù)邊是否具有方向，可分為圖 9-2 所示的「無向圖 undirected graph」和「有向圖 directed graph」。

• 在無向圖中，邊表示兩頂點之間的“雙向”連接關系，例如微信或 QQ 中的“好友關系”。
• 在有向圖中，邊具有方向性，即 A→B 和 A←B 兩個方向的邊是相互獨立的，例如微博或抖音上的“關注”與“被關注”關系。

圖 9-2   有向圖與無向圖

根據(jù)所有頂點是否連通，可分為圖 9-3 所示的「連通圖 connected graph」和「非連通圖 disconnected graph」。

• 對于連通圖，從某個頂點出發(fā)，可以到達其余任意頂點。
• 對于非連通圖，從某個頂點出發(fā)，至少有一個頂點無法到達。

圖 9-3   連通圖與非連通圖

我們還可以為邊添加“權重”變量，從而得到圖 9-4 所示的「有權圖 weighted graph」。例如在王者榮耀等手游中，系統(tǒng)會根據(jù)共同游戲時間來計算玩家之間的“親密度”，這種親密度網(wǎng)絡就可以用有權圖來表示。

圖 9-4   有權圖與無權圖

圖數(shù)據(jù)結構包含以下常用術語。

• 「鄰接 adjacency」：當兩頂點之間存在邊相連時，稱這兩頂點“鄰接”。在圖 9-4 中，頂點 1 的鄰接頂點為頂點 2、3、5。
• 「路徑 path」：從頂點 A 到頂點 B 經(jīng)過的邊構成的序列被稱為從 A 到 B 的“路徑”。在圖 9-4 中，邊序列 1-5-2-4 是頂點 1 到頂點 4 的一條路徑。
• 「度 degree」：一個頂點擁有的邊數(shù)。對于有向圖，「入度 In-Degree」表示有多少條邊指向該頂點，「出度 Out-Degree」表示有多少條邊從該頂點指出。

9.1.2   圖的表示

圖的常用表示方式包括“鄰接矩陣”和“鄰接表”。以下使用無向圖進行舉例。

1.   鄰接矩陣

設圖的頂點數(shù)量為 n ，「鄰接矩陣 adjacency matrix」使用一個 n×n 大小的矩陣來表示圖，每一行（列）代表一個頂點，矩陣元素代表邊，用 1 或 0 表示兩個頂點之間是否存在邊。

如圖 9-5 所示，設鄰接矩陣為 M、頂點列表為 V ，那么矩陣元素 M[i,j]=1 表示頂點 V[i] 到頂點 V[j] 之間存在邊，反之 M[i,j]=0 表示兩頂點之間無邊。

圖 9-5   圖的鄰接矩陣表示

鄰接矩陣具有以下特性。

• 頂點不能與自身相連，因此鄰接矩陣主對角線元素沒有意義。
• 對于無向圖，兩個方向的邊等價，此時鄰接矩陣關于主對角線對稱。
• 將鄰接矩陣的元素從 1 和 0 替換為權重，則可表示有權圖。

使用鄰接矩陣表示圖時，我們可以直接訪問矩陣元素以獲取邊，因此增刪查操作的效率很高，時間復雜度均為 O(1) 。然而，矩陣的空間復雜度為 O(n2) ，內存占用較多。

2.   鄰接表

「鄰接表 adjacency list」使用 n 個鏈表來表示圖，鏈表節(jié)點表示頂點。第 i 條鏈表對應頂點 i ，其中存儲了該頂點的所有鄰接頂點（即與該頂點相連的頂點）。圖 9-6 展示了一個使用鄰接表存儲的圖的示例。

圖 9-6   圖的鄰接表表示

鄰接表僅存儲實際存在的邊，而邊的總數(shù)通常遠小于 n2 ，因此它更加節(jié)省空間。然而，在鄰接表中需要通過遍歷鏈表來查找邊，因此其時間效率不如鄰接矩陣。

觀察圖 9-6 ，鄰接表結構與哈希表中的“鏈式地址”非常相似，因此我們也可以采用類似方法來優(yōu)化效率。比如當鏈表較長時，可以將鏈表轉化為 AVL 樹或紅黑樹，從而將時間效率從 O(n) 優(yōu)化至 O(log?n) ；還可以把鏈表轉換為哈希表，從而將時間復雜度降低至 O(1) 。

9.1.3   圖常見應用

如表 9-1 所示，許多現(xiàn)實系統(tǒng)都可以用圖來建模，相應的問題也可以約化為圖計算問題。

表 9-1   現(xiàn)實生活中常見的圖