1 前言

由于后續(xù)更新「面試專場」的好幾篇文章都涉及到圖這種數(shù)據(jù)結構，因此打算先普及一下 圖 的相關理論支持，如果后面的相關內容有些點不太容易理解，可以查閱此篇文章。本文不建議一口氣閱讀完畢，可以先瀏覽一遍，在后續(xù)有需要的時候進行查閱即可。

2 圖

圖是數(shù)據(jù)結構中重要內容。相比于線性表與樹，圖的結構更為復雜。在線性表的存儲結構中，數(shù)據(jù)直接按照前驅后繼的線性組織形式排列。在樹的結構中，數(shù)據(jù)節(jié)點以層的方式排列，節(jié)點與節(jié)點之間是一種層次關系。但是，在圖的結構中數(shù)據(jù)之間可以有任意關系，這就使得圖的數(shù)據(jù)結構相對復雜。

2.1 定義

定義：圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。

例如：圖 2.1 所示圖

圖2.1

在圖 2.1 中，共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊。

注：

當線性表沒有數(shù)據(jù)節(jié)點時，線性表為空表。樹中沒有節(jié)點時，樹為空樹。但是，在圖中不允許沒有頂點，但是可以沒有邊。

2.2 無向邊

無向邊：若頂點 x 和 y 之間的邊沒有方向，則稱該邊為無向邊(x,y)，(x,y) 與 (y,x) 意義相同，表示 x 和 y 之間有連接。??圖 2.2 所示圖中的邊均為無向邊。

圖2.2

2.3 有向邊

有向邊：若頂點 x 和 y 之間的邊有方向，則稱該邊為有向邊，與表示的意義是不同的，表示從 x 連接到 y ，x 稱為尾，y 稱為頭。表示從 y 連接到 x ，y 稱為尾， x 稱為頭。??圖2.3所示圖中的邊為有向邊。

圖2.3

2.4 無向圖

無向圖：若圖中任意兩個頂點之間的邊均是無向邊，則稱該圖為無向圖。圖2.2所示圖為無向圖。

2.5 有向圖

有向圖：若圖中任意兩個頂點之間的邊均是有向邊，則稱該圖為有向圖。圖2.3所示的圖為有向圖。

2.6 頂點與頂點的度

圖2.6

頂點的度：

頂點 V 的度是和 V 相關聯(lián)的邊的數(shù)目，記為TD(V)。

圖 2.6 所示圖中，V0 頂點的度為 3 。

入度：

以頂點v為頭的邊的數(shù)目，記為ID(V)。

圖2.6所示圖中，V0的入度為1。

出度：

以頂點 v 為尾的邊的數(shù)目，記為 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 ，則構成一條路徑。

圖 2.8

3 完全圖

完全圖：每個頂點都與其他頂點相鄰接的圖。

無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。（含有n個頂點的無向完全圖有(n×(n-1))/2條邊）圖 3.1 所示的圖為無向完全圖。

圖3.1

有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條邊，則稱該圖為有向完全圖。（含有 n 個頂點的有向完全圖有 n×(n-1) 條邊）

圖3.2所示的圖為有向完全圖。

圖3.2

4 連通圖

在無向圖 G 中，如果從頂點 v 到頂點 v' 有路徑，則稱 v 和 v' 是連通的。 如果對于圖中任意兩個頂點 vi 、vj ∈E， vi，和vj都是連通的，則稱 G 是連通圖，否則圖為非連通圖。??例如：圖4.1所示圖，圖中頂點A、B、C、D是連通的，但是其中任一頂點與頂點E或者頂點F之間沒有路徑，因此圖4.1中所示的圖為非連通圖。

圖4.1

若添加頂點B與頂點F之間的鄰接邊，則圖變?yōu)檫B通圖，如圖4.2所示：

圖4.2

5 數(shù)組存儲

圖的數(shù)組存儲方式也稱為鄰接矩陣存儲。圖中的數(shù)據(jù)信息包括：頂點信息和描述頂點之間關系的邊的信息，將這兩種信息存儲在數(shù)組中即為圖的數(shù)組存儲。??首先，創(chuàng)建頂點數(shù)組，頂點數(shù)組中存儲的是圖的頂點信息，采用一維數(shù)組的方式即可存儲所有的頂點信息。存儲圖中邊的信息時，由于邊是描述頂點與頂點之間關系的信息，因此需要采用二維數(shù)組進行存儲。

定義：設圖 G 有 n 個頂點，則鄰接矩陣是一個n X n的方陣A，定義為：

圖 5 其中，或者(Vi , Vj,)表示頂點 Vi 與頂點 Vj 鄰接。wi,j表示邊的權重值。

例如：下圖所示的無向圖，采用數(shù)組存儲形式如下。

圖5.1

注：圖中的數(shù)組存儲方式簡化了邊的權值為 1 。

無向圖的數(shù)組存儲主要有以下特性：

（1）頂點數(shù)組長度為圖的頂點數(shù)目n。邊數(shù)組為n X n的二維數(shù)組。（2）邊數(shù)組中，A[i][j] =1代表頂點i與頂點j鄰接，A[i][j] = 0代表頂點i與頂點j不鄰接。（3）在無向圖中。由于邊是無向邊，因此頂點的鄰接關系是對稱的，邊數(shù)組為對稱二維數(shù)組。（4）頂點與自身之間并未鄰接關系，因此邊數(shù)組的對角線上的元素均為0。（5）頂點的度即為頂點所在的行或者列1的數(shù)目。例如：頂點V2的度為3，則V2所在行和列中的1的數(shù)目為3。

當圖為有向圖時，圖的數(shù)組存儲方式要發(fā)生變化。例如：圖5.2所示的有向圖，采用數(shù)組存儲形式如下。

圖5.2

有向圖的數(shù)組存儲主要有以下特性：

（1）頂點數(shù)組長度為圖的頂點數(shù)目n。邊數(shù)組為n X n的二維數(shù)組。（2）邊數(shù)組中，數(shù)組元素為1，即A[i][j] = 1,代表第i個頂點與第j個頂點鄰接，且i為尾，j為頭。 A[i][j] = 0代表頂點與頂點不鄰接。（3）在有向圖中，由于邊存在方向性，因此數(shù)組不一定為對稱數(shù)組。（4）對角線上元素為0。（5）第i行中，1的數(shù)目代表第i個頂點的出度。例如：頂點V1的出度為2，則頂點V1所在行的1的數(shù)目為2。（6）第j列中，1的數(shù)目代表第j個頂點的入度。例如：V3的入度為1，則V3所在列中1的數(shù)目為1。

數(shù)組存儲方式優(yōu)點：??數(shù)組存儲方式容易實現(xiàn)圖的操作。例如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。數(shù)組存儲方式缺點：??采用數(shù)組存儲方式，圖若有n個頂點則需要n2個單元存儲邊(弧)，空間存儲效率為O(n2)。 當頂點數(shù)目較多，邊數(shù)目較少時，此時圖為稀疏圖，這時尤其浪費空間。??例如：圖5.3所示的圖，圖中有 9 個頂點，邊數(shù)為10，需要 9X9 的二維數(shù)組，而實際存儲邊信息空間只有10，造成空間浪費。

圖5.3

圖5.3所示無向圖的存儲數(shù)組：

6 鄰接表

當使用數(shù)組存儲時，主要有以下三個問題：

（1）對于一個圖，若圖中的頂點數(shù)目過大，則無法使用鄰接矩陣進行存儲。因為在分配數(shù)組內存時可能會導致內存分配失敗。（2）對于某些稀疏圖（即頂點數(shù)目多，邊數(shù)目少），創(chuàng)建的數(shù)組大小很大，而真正存儲的有用信息又很少，這就造成了空間上的浪費。 （3）有時兩個點之間不止存在有一條邊，這是用鄰接矩陣就無法同時表示兩條以上的邊。

針對以上情況，提出了一種特殊的圖存儲方式，讓每個節(jié)點擁有的數(shù)組大小剛好就等于它所連接的邊數(shù)，由此建立一種鄰接表的存儲方式。

鄰接表存儲方法是一種數(shù)組存儲和鏈式存儲相結合的存儲方法。在鄰接表中，對圖中的每個頂點建立一個單鏈表，第 i 個單鏈表中的結點依附于頂點 Vi 的邊（對有向圖是以頂點Vi為尾的?。?。鏈表中的節(jié)點稱為表節(jié)點，共有 3個域，具體結構見下圖：

圖 6表結點由三個域組成，adjvex存儲與Vi鄰接的點在圖中的位置，nextarc存儲下一條邊或弧的結點，data存儲與邊或弧相關的信息如權值。

除表節(jié)點外，需要在數(shù)組中存儲頭節(jié)點，頭結點由兩個域組成，分別指向鏈表中第一個頂點和存儲Vi的名或其他信息。具體結構如下圖：

圖 6.0

其中，data域中存儲頂點相關信息，firstarc指向鏈表的第一個節(jié)點。無向圖采用鄰接表方式存儲例如：圖6.1所示的無向圖采用鄰接表存儲。

圖6.1 無向圖

采用鄰接表方式存儲圖 6.1 中的無向圖，繪圖過程中忽略邊節(jié)點的info信息，頭結點中的 data 域存儲頂點名稱。以V1頂點為例，V1頂點的鄰接頂點為V2、V3、V4，則可以創(chuàng)建3個表節(jié)點，表節(jié)點中adjvex分別存儲V2、V3、V4的索引1、2、3，按照此方式，得到的鄰接表為：

圖 6.2

無向圖的鄰接表存儲特性：

（1）數(shù)組中頭節(jié)點的數(shù)目為圖的頂點數(shù)目。（2）鏈表的長度即為頂點的度。例如：V1頂點的度為3，則以V1為頭節(jié)點的鏈表中表節(jié)點的數(shù)目為3。

有向圖采用鄰接表方式存儲例如：圖 6.3 所示的有向圖采用鄰接表存儲。

圖 6.3

采用鄰接表方式存儲圖6.3中的有向圖，繪圖過程中忽略邊節(jié)點的info信息，頭結點中的data域存儲頂點名稱。以V1頂點為例，V1頂點的鄰接頂點為V2、V3、V4，但是以V1頂點為尾的邊只有兩條，即和因此，創(chuàng)建2個表節(jié)點。表節(jié)點中adjvex分別存儲V3、V4的索引2、3，按照此方式，得到的鄰接表為：

圖 6.4有向圖的鄰接表存儲特性：

（1）數(shù)組中表節(jié)點的數(shù)目為圖的頂點數(shù)目。（2）鏈表的長度即為頂點的出度。例如V1的出度為2，V1為頭節(jié)點的鏈表中，表節(jié)點的數(shù)目為2。（3）頂點Vi的入度為鄰接表中所有adjvex值域為i的表結點數(shù)目。例如：頂點V3的入度為4，則鏈表中所有adjvex值域為2的表結點數(shù)目為4。

注：圖采用鄰接表的方式表示時，其表示方式是不唯一的。這是因為在每個頂點對應的單鏈表中，各邊節(jié)點的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序。

7 逆鄰接表

在鄰接表中，可以輕易的得出頂點的出度，但是想要得到頂點的入度，則需要遍歷整個鏈表。為了便于確定頂點的入度，可以建立有向圖的逆鄰接表。逆鄰接表的建立與鄰接表相反。??采用逆鄰接表的方式存儲圖3.2所示的無向圖。以V3頂點為例，V3頂點的鄰接頂點為V1、V2、V4、V5，以V3頂點為頭的邊有4條，即、、、因此，創(chuàng)建4個表節(jié)點。表節(jié)點中adjvex分別存儲V0、V1、V3、V4的索引0、1、3、4，按照此方式，得到的逆鄰接表為：

圖 7

8 十字鏈表

對于有向圖而言，鄰接鏈表的缺陷是要查詢某個頂點的入度時需要遍歷整個鏈表，而逆鄰接鏈表在查詢某個頂點的出度時要遍歷整個鏈表。為了解決這些問題，十字鏈表將鄰接鏈表和逆鄰接鏈表綜合了起來，而得到的一種十字鏈表。在十字鏈表中，每一條邊對應一種邊節(jié)點，每一個頂點對應為頂點節(jié)點。

頂點節(jié)點頂點節(jié)點即為頭節(jié)點，由3個域構成，具體形式如下：

圖 8 其中，data域存儲與頂點相關的信息，firstin和firstout分別指向以此頂點為頭或尾的第一個邊節(jié)點。邊節(jié)點在邊節(jié)點為鏈表節(jié)點，共有 5 個域，具體形式如下：

img 其中，尾域tailvex和頭域headvex分別指向尾和頭的頂點在圖中的位置。鏈域hlink指向頭相同的下一條邊，鏈域tlink指向尾相同的下一條邊。info 存儲此條邊的相關信息。例如：圖8.1所示的有向圖，采用十字鏈表存儲圖方式。

圖8.1 有向圖

采用十字鏈表的方式存儲圖8.1中的有向圖，繪圖過程忽略邊節(jié)點中的info信息，表頭節(jié)點中的data域存儲頂點名稱。以V1頂點為例，頂點節(jié)點的data域存儲V1頂點名，firstin存儲以V1頂點為頭第一個邊節(jié)點，以V1頂點為頭邊為，firstout存儲以以V1頂點為尾第一個邊節(jié)點，對應邊為。按照此規(guī)則，得到的十字鏈表存儲為：

img注：采用十字鏈表存儲時，表頭節(jié)點仍然使用數(shù)組存儲，采用下標索引方式獲取。

9 鄰接多重表

對于無向圖而言，其每條邊在鄰接鏈表中都需要兩個結點來表示，而鄰接多重表正是對其進行優(yōu)化，讓同一條邊只用一個結點表示即可。鄰接多重表仿照了十字鏈表的思想，對鄰接鏈表的邊表結點進行了改進。

重新定義的邊結點結構如下圖：

img 其中，ivex和jvex是指某條邊依附的兩個頂點在頂點表中的下標。 ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊。info存儲邊的相關信息。

重新定義的頂點結構如下圖：

圖 9 其中，data存儲頂點的相關信息，firstedge指向第一條依附于該頂點的邊。例如：圖9.1所示的無向圖，采用鄰接多重表存儲圖。

圖9.1 無向圖

圖 9.1 所示的無向圖，采用鄰接多重表存儲，以 V0 為例，頂點節(jié)點的data域存儲V0名稱，firstedge 指向(V0 , V1)邊，邊節(jié)點中的ilink指向依附V0頂點的下一條邊(V0 , V3)，jlink指向依附V1頂點的下一條邊(V1 , V2)，按照此方式建立鄰接多重表：