圖

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

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

圖 9-1   鏈表、樹、圖之間的關(guān)系

9.1.1   圖常見類型與術(shù)語(yǔ)

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

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

圖 9-2   有向圖與無(wú)向圖

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

• 對(duì)于連通圖，從某個(gè)頂點(diǎn)出發(fā)，可以到達(dá)其余任意頂點(diǎn)。
• 對(duì)于非連通圖，從某個(gè)頂點(diǎn)出發(fā)，至少有一個(gè)頂點(diǎn)無(wú)法到達(dá)。

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

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

圖 9-4   有權(quán)圖與無(wú)權(quán)圖

圖數(shù)據(jù)結(jié)構(gòu)包含以下常用術(shù)語(yǔ)。

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

9.1.2   圖的表示

圖的常用表示方式包括“鄰接矩陣”和“鄰接表”。以下使用無(wú)向圖進(jìn)行舉例。

1.   鄰接矩陣

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

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

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

鄰接矩陣具有以下特性。

• 頂點(diǎn)不能與自身相連，因此鄰接矩陣主對(duì)角線元素沒(méi)有意義。
• 對(duì)于無(wú)向圖，兩個(gè)方向的邊等價(jià)，此時(shí)鄰接矩陣關(guān)于主對(duì)角線對(duì)稱。
• 將鄰接矩陣的元素從 1 和 0 替換為權(quán)重，則可表示有權(quán)圖。

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

2.   鄰接表

「鄰接表 adjacency list」使用 n 個(gè)鏈表來(lái)表示圖，鏈表節(jié)點(diǎn)表示頂點(diǎn)。第 i 條鏈表對(duì)應(yīng)頂點(diǎn) i ，其中存儲(chǔ)了該頂點(diǎn)的所有鄰接頂點(diǎn)（即與該頂點(diǎn)相連的頂點(diǎn)）。圖 9-6 展示了一個(gè)使用鄰接表存儲(chǔ)的圖的示例。

圖 9-6   圖的鄰接表表示

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

觀察圖 9-6 ，鄰接表結(jié)構(gòu)與哈希表中的“鏈?zhǔn)降刂贰狈浅Ｏ嗨疲虼宋覀円部梢圆捎妙愃品椒▉?lái)優(yōu)化效率。比如當(dāng)鏈表較長(zhǎng)時(shí)，可以將鏈表轉(zhuǎn)化為 AVL 樹或紅黑樹，從而將時(shí)間效率從 O(n) 優(yōu)化至 O(log?n) ；還可以把鏈表轉(zhuǎn)換為哈希表，從而將時(shí)間復(fù)雜度降低至 O(1) 。

9.1.3   圖常見應(yīng)用

如表 9-1 所示，許多現(xiàn)實(shí)系統(tǒng)都可以用圖來(lái)建模，相應(yīng)的問(wèn)題也可以約化為圖計(jì)算問(wèn)題。

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