數據結構與算法——圖論基礎與圖存儲結構
1 前言
由於後續更新「面試專場」的好幾篇文章都涉及到 圖 這種數據結構，因此打算先普及一下 圖 的相關理論支持，如果後面的相關內容有些點不太容易理解，可以查閱此篇文章。本文不建議一口氣閱讀完畢，可以先瀏覽一遍，在後續有需要的時候進行查閱即可。
2 圖
圖是數據結構中重要內容。相比於線性表與樹，圖的結構更為複雜。在線性表的存儲結構中，數據直接按照前驅後繼的線性組織形式排列。在樹的結構中，數據節點以層的方式排列，節點與節點之間是一種層次關係。但是，在圖的結構中數據之間可以有任意關係，這就使得圖的數據結構相對複雜。
2.1 定義
定義：圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。
例如：圖 2.1 所示圖
圖 2.1
在圖 2.1 中，共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊。
注：
當線性表沒有數據節點時，線性表為空表。
樹中沒有節點時，樹為空樹。
但是，在圖中不允許沒有頂點，但是可以沒有邊。
2.2 無向邊
無向邊：若頂點 x 和 y 之間的邊沒有方向，則稱該邊為無向邊(x,y)，(x,y) 與 (y,x) 意義相同，表示 x 和 y 之間有連接。
圖 2.2 所示圖中的邊均為無向邊。
2.3 有向邊
有向邊：若頂點 x 和 y 之間的邊有方向，則稱該邊為有向邊，與表示的意義是不同的，表示從 x 連接到 y ，x 稱為尾，y 稱為頭。表示從 y 連接到 x ，y 稱為尾， x 稱為頭。
圖2.3所示圖中的邊為有向邊。
2.4 無向圖
無向圖：若圖中任意兩個頂點之間的邊均是無向邊，則稱該圖為無向圖。
圖2.2所示圖為無向圖。
2.5 有向圖
有向圖：若圖中任意兩個頂點之間的邊均是有向邊，則稱該圖為有向圖。
圖2.3所示的圖為有向圖。
2.6 頂點與頂點的度
頂點的度：
頂點 V 的度是和 V 相關聯的邊的數目，記為TD(V)。
圖 2.6 所示圖中，V0 頂點的度為 3 。
入度：
以頂點v為頭的邊的數目，記為ID(V)。
圖2.6所示圖中，V0的入度為1。
出度：
以頂點 v 為尾的邊的數目，記為 OD(V)。
圖2.6所示圖中，V0的出度為2。
頂點的度 = 入度 + 出度。
即 TD(V) = ID(V) + OD(V)。
2.7 鄰接
鄰接是兩個頂點之間的一種關係。如果圖包含（u,v），則稱頂點 v 與頂點 u 鄰接。在無向圖中，這也暗示了頂點 u 也與頂點 v 鄰接。換句話說，在無向圖中鄰接關係是對稱的。
2.8 路徑
路徑：在圖中，依次遍歷頂點序列之間的邊所形成的軌跡。
例如：在圖 2.8 中所示圖中依次訪問頂點 V0 、V3 和 V2 ，則構成一條路徑。
3 完全圖
完全圖：每個頂點都與其他頂點相鄰接的圖。
無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。（含有n個頂點的無向完全圖有(n×(n-1))/2條邊）
圖 3.1 所示的圖為無向完全圖。
有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條邊，則稱該圖為有向完全圖。（含有 n 個頂點的有向完全圖有 n×(n-1) 條邊）
圖3.2所示的圖為有向完全圖。
4 連通圖
在無向圖 G 中，如果從頂點 v 到頂點 v’ 有路徑，則稱 v 和 v’ 是連通的。 如果對於圖中任意兩個頂點 vi 、vj ∈E， vi，和vj都是連通的，則稱 G 是連通圖，否則圖為非連通圖。
例如：圖4.1所示圖，圖中頂點A、B、C、D是連通的，但是其中任一頂點與頂點E或者頂點F之間沒有路徑，因此圖4.1中所示的圖為非連通圖。
若添加頂點B與頂點F之間的鄰接邊，則圖變為連通圖，如圖4.2所示：
5 數組存儲
圖的數組存儲方式也稱為鄰接矩陣存儲。圖中的數據信息包括：頂點信息和描述頂點之間關係的邊的信息，將這兩種信息存儲在數組中即為圖的數組存儲。
首先，創建頂點數組，頂點數組中存儲的是圖的頂點信息，採用一維數組的方式即可存儲所有的頂點信息。存儲圖中邊的信息時，由於邊是描述頂點與頂點之間關係的信息，因此需要採用二維數組進行存儲。
定義：設圖 G 有 n 個頂點，則鄰接矩陣是一個n X n的方陣A，定義為：
其中，或者(Vi , Vj,)表示頂點 Vi 與頂點 Vj 鄰接。wi,j表示邊的權重值。
例如：下圖所示的無向圖，採用數組存儲形式如下。
注：圖中的數組存儲方式簡化了邊的權值為 1 。
無向圖的數組存儲主要有以下特性：
（1）頂點數組長度為圖的頂點數目n。邊數組為n X n的二維數組。
（2）邊數組中，Ai =1代表頂點i與頂點j鄰接，Ai = 0代表頂點i與頂點j不鄰接。
（3）在無向圖中。由於邊是無向邊，因此頂點的鄰接關係是對稱的，邊數組為對稱二維數組。
（4）頂點與自身之間並未鄰接關係，因此邊數組的對角線上的元素均為0。
（5）頂點的度即為頂點所在的行或者列1的數目。例如：頂點V2的度為3，則V2所在行和列中的1的數目為3。
當圖為有向圖時，圖的數組存儲方式要發生變化。
例如：圖5.2所示的有向圖，採用數組存儲形式如下。
有向圖的數組存儲主要有以下特性：
（1）頂點數組長度為圖的頂點數目n。邊數組為n X n的二維數組。
（2）邊數組中，數組元素為1，即Ai = 1,代表第i個頂點與第j個頂點鄰接，且i為尾，j為頭。 Ai = 0代表頂點與頂點不鄰接。
（3）在有向圖中，由於邊存在方向性，因此數組不一定為對稱數組。
（4）對角線上元素為0。
（5）第i行中，1的數目代表第i個頂點的出度。例如：頂點V1的出度為2，則頂點V1所在行的1的數目為2。
（6）第j列中，1的數目代表第j個頂點的入度。例如：V3的入度為1，則V3所在列中1的數目為1。
數組存儲方式優點：
數組存儲方式容易實現圖的操作。例如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。
數組存儲方式缺點：
採用數組存儲方式，圖若有n個頂點則需要n2個單元存儲邊(弧)，空間存儲效率為O(n2)。 當頂點數目較多，邊數目較少時，此時圖為稀疏圖，這時尤其浪費空間。
例如：圖5.3所示的圖，圖中有 9 個頂點，邊數為10，需要 9X9 的二維數組，而實際存儲邊信息空間只有10，造成空間浪費。
圖5.3所示無向圖的存儲數組：
6 鄰接表
當使用數組存儲時，主要有以下三個問題：
（1）對於一個圖，若圖中的頂點數目過大，則無法使用鄰接矩陣進行存儲。因為在分配數組內存時可能會導致內存分配失敗。
（2）對於某些稀疏圖（即頂點數目多，邊數目少），創建的數組大小很大，而真正存儲的有用信息又很少，這就造成了空間上的浪費。
（3）有時兩個點之間不止存在有一條邊，這是用鄰接矩陣就無法同時表示兩條以上的邊。
針對以上情況，提出了一種特殊的圖存儲方式，讓每個節點擁有的數組大小剛好就等於它所連接的邊數，由此建立一種鄰接表的存儲方式。
鄰接表存儲方法是一種數組存儲和鏈式存儲相結合的存儲方法。在鄰接表中，對圖中的每個頂點建立一個單鏈表，第 i 個單鏈表中的結點依附於頂點 Vi 的邊（對有向圖是以頂點Vi為尾的弧）。鏈表中的節點稱為表節點，共有 3個域，具體結構見下圖：
表結點由三個域組成，adjvex存儲與Vi鄰接的點在圖中的位置，nextarc存儲下一條邊或弧的結點，data存儲與邊或弧相關的信息如權值。
除表節點外，需要在數組中存儲頭節點，頭結點由兩個域組成，分別指向鏈表中第一個頂點和存儲Vi的名或其他信息。具體結構如下圖：
其中，data域中存儲頂點相關信息，firstarc指向鏈表的第一個節點。
無向圖採用鄰接表方式存儲
例如：圖6.1所示的無向圖採用鄰接表存儲。
採用鄰接表方式存儲圖 6.1 中的無向圖，繪圖過程中忽略邊節點的info信息，頭結點中的 data 域存儲頂點名稱。以V1頂點為例，V1頂點的鄰接頂點為V2、V3、V4，則可以創建3個表節點，表節點中adjvex分別存儲V2、V3、V4的索引1、2、3，按照此方式，得到的鄰接表為：
無向圖的鄰接表存儲特性：
（1）數組中頭節點的數目為圖的頂點數目。
（2）鏈表的長度即為頂點的度。例如：V1頂點的度為3，則以V1為頭節點的鏈表中表節點的數目為3。
有向圖採用鄰接表方式存儲
例如：圖 6.3 所示的有向圖採用鄰接表存儲。
採用鄰接表方式存儲圖6.3中的有向圖，繪圖過程中忽略邊節點的info信息，頭結點中的data域存儲頂點名稱。以V1頂點為例，V1頂點的鄰接頂點為V2、V3、V4，但是以V1頂點為尾的邊只有兩條，即和因此，創建2個表節點。表節點中adjvex分別存儲V3、V4的索引2、3，按照此方式，得到的鄰接表為：
有向圖的鄰接表存儲特性：
（1）數組中表節點的數目為圖的頂點數目。
（2）鏈表的長度即為頂點的出度。例如V1的出度為2，V1為頭節點的鏈表中，表節點的數目為2。
（3）頂點Vi的入度為鄰接表中所有adjvex值域為i的表結點數目。例如：頂點V3的入度為4，則鏈表中所有adjvex值域為2的表結點數目為4。
注：圖採用鄰接表的方式表示時，其表示方式是不唯一的。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的算法以及邊的輸入次序。
7 逆鄰接表
在鄰接表中，可以輕易的得出頂點的出度，但是想要得到頂點的入度，則需要遍歷整個鏈表。為了便於確定頂點的入度，可以建立有向圖的逆鄰接表。逆鄰接表的建立與鄰接表相反。
採用逆鄰接表的方式存儲圖3.2所示的無向圖。以V3頂點為例，V3頂點的鄰接頂點為V1、V2、V4、V5，以V3頂點為頭的邊有4條，即、、、因此，創建4個表節點。表節點中adjvex分別存儲V0、V1、V3、V4的索引0、1、3、4，按照此方式，得到的逆鄰接表為：
8 十字鏈表
對於有向圖而言，鄰接鏈表的缺陷是要查詢某個頂點的入度時需要遍歷整個鏈表，而逆鄰接鏈表在查詢某個頂點的出度時要遍歷整個鏈表。為了解決這些問題，十字鏈表將鄰接鏈表和逆鄰接鏈表綜合了起來，而得到的一種十字鏈表。在十字鏈表中，每一條邊對應一種邊節點，每一個頂點對應為頂點節點。
頂點節點
頂點節點即為頭節點，由3個域構成，具體形式如下：
其中，data域存儲與頂點相關的信息，firstin和firstout分別指向以此頂點為頭或尾的第一個邊節點。
邊節點
在邊節點為鏈表節點，共有 5 個域，具體形式如下：
其中，尾域tailvex和頭域headvex分別指向尾和頭的頂點在圖中的位置。鏈域hlink指向頭相同的下一條邊，鏈域tlink指向尾相同的下一條邊。info 存儲此條邊的相關信息。
例如：圖8.1所示的有向圖，採用十字鏈表存儲圖方式。
採用十字鏈表的方式存儲圖8.1中的有向圖，繪圖過程忽略邊節點中的info信息，表頭節點中的data域存儲頂點名稱。以V1頂點為例，頂點節點的data域存儲V1頂點名，firstin存儲以V1頂點為頭第一個邊節點，以V1頂點為頭邊為，firstout存儲以以V1頂點為尾第一個邊節點，對應邊為。按照此規則，得到的十字鏈表存儲為：
注：採用十字鏈表存儲時，表頭節點仍然使用數組存儲，採用下標索引方式獲取。
9 鄰接多重表
對於無向圖而言，其每條邊在鄰接鏈表中都需要兩個結點來表示，而鄰接多重表正是對其進行優化，讓同一條邊只用一個結點表示即可。鄰接多重表仿照了十字鏈表的思想，對鄰接鏈表的邊表結點進行了改進。
重新定義的邊結點結構如下圖：
其中，ivex和jvex是指某條邊依附的兩個頂點在頂點表中的下標。 ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊。info存儲邊的相關信息。
重新定義的頂點結構如下圖：
其中，data存儲頂點的相關信息，firstedge指向第一條依附於該頂點的邊。
例如：圖9.1所示的無向圖，採用鄰接多重表存儲圖。
圖 9.1 所示的無向圖，採用鄰接多重表存儲，以 V0 為例，頂點節點的data域存儲V0名稱，firstedge 指向(V0 , V1)邊，邊節點中的ilink指向依附V0頂點的下一條邊(V0 , V3)，jlink指向依附V1頂點的下一條邊(V1 , V2)，按照此方式建立鄰接多重表：
來源 | 五分鐘學算法
作者 | 程序員小吳