聯(lián) 系 人：王 總
電 話：13903470418
固 定 電 話：0357-4523660
地 址：山西省臨汾市曲沃縣晉韓東路50米
郵 箱：13903470418@163.com
辦公室郵箱：bangongshi@sxclny.com
由于后續(xù)更新「面試專場(chǎng)」的好幾篇文章都涉及到 圖 這種數(shù)據(jù)結(jié)構(gòu)，因此打算先普及一下 圖 的相關(guān)理論支持，如果后面的相關(guān)內(nèi)容有些點(diǎn)不太容易理解，可以查閱此篇文章。本文不建議一口氣閱讀完畢，可以先瀏覽一遍，在后續(xù)有需要的時(shí)候進(jìn)行查閱即可。
圖是數(shù)據(jù)結(jié)構(gòu)中重要內(nèi)容。相比于線性表與樹(shù)，圖的結(jié)構(gòu)更為復(fù)雜。在線性表的存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)直接按照前驅(qū)后繼的線性組織形式排列。在樹(shù)的結(jié)構(gòu)中，數(shù)據(jù)節(jié)點(diǎn)以層的方式排列，節(jié)點(diǎn)與節(jié)點(diǎn)之間是一種層次關(guān)系。但是，在圖的結(jié)構(gòu)中數(shù)據(jù)之間可以有任意關(guān)系，這就使得圖的數(shù)據(jù)結(jié)構(gòu)相對(duì)復(fù)雜。
定義：圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個(gè)圖，V 是圖 G 中頂點(diǎn)的集合，E 是圖 G 中邊的集合。
例如：圖 2.1 所示圖
在圖 2.1 中，共有 V0，V1，V2，V3 這 4 個(gè)頂點(diǎn)，4 個(gè)頂點(diǎn)之間共有 5 條邊。
注：
當(dāng)線性表沒(méi)有數(shù)據(jù)節(jié)點(diǎn)時(shí)，線性表為空表。樹(shù)中沒(méi)有節(jié)點(diǎn)時(shí)，樹(shù)為空樹(shù)。但是，在圖中不允許沒(méi)有頂點(diǎn)，但是可以沒(méi)有邊。
頂點(diǎn)的度：
頂點(diǎn) V 的度是和 V 相關(guān)聯(lián)的邊的數(shù)目，記為T(mén)D(V)。
圖 2.6 所示圖中，V0 頂點(diǎn)的度為 3 。
入度：
以頂點(diǎn)v為頭的邊的數(shù)目，記為ID(V)。
圖2.6所示圖中，V0的入度為1。
出度：
以頂點(diǎn) v 為尾的邊的數(shù)目，記為 OD(V)。
圖2.6所示圖中，V0的出度為2。
頂點(diǎn)的度 = 入度 + 出度。
即 TD(V) = ID(V) + OD(V)。
鄰接是兩個(gè)頂點(diǎn)之間的一種關(guān)系。如果圖包含（u,v），則稱頂點(diǎn) v 與頂點(diǎn) u 鄰接。在無(wú)向圖中，這也暗示了頂點(diǎn) u 也與頂點(diǎn) v 鄰接。換句話說(shuō)，在無(wú)向圖中鄰接關(guān)系是對(duì)稱的。
完全圖：每個(gè)頂點(diǎn)都與其他頂點(diǎn)相鄰接的圖。
有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條邊，則稱該圖為有向完全圖。（含有 n 個(gè)頂點(diǎn)的有向完全圖有 n×(n-1) 條邊）
圖3.2所示的圖為有向完全圖。
若添加頂點(diǎn)B與頂點(diǎn)F之間的鄰接邊，則圖變?yōu)檫B通圖，如圖4.2所示：
定義：設(shè)圖 G 有 n 個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n X n的方陣A，定義為：
其中，或者(Vi , Vj,)表示頂點(diǎn) Vi 與頂點(diǎn) Vj 鄰接。wi,j表示邊的權(quán)重值。
例如：下圖所示的無(wú)向圖，采用數(shù)組存儲(chǔ)形式如下。
注：圖中的數(shù)組存儲(chǔ)方式簡(jiǎn)化了邊的權(quán)值為 1 。
無(wú)向圖的數(shù)組存儲(chǔ)主要有以下特性：
（1）頂點(diǎn)數(shù)組長(zhǎng)度為圖的頂點(diǎn)數(shù)目n。邊數(shù)組為n X n的二維數(shù)組。（2）邊數(shù)組中，A[i][j] =1代表頂點(diǎn)i與頂點(diǎn)j鄰接，A[i][j] = 0代表頂點(diǎn)i與頂點(diǎn)j不鄰接。（3）在無(wú)向圖中。由于邊是無(wú)向邊，因此頂點(diǎn)的鄰接關(guān)系是對(duì)稱的，邊數(shù)組為對(duì)稱二維數(shù)組。（4）頂點(diǎn)與自身之間并未鄰接關(guān)系，因此邊數(shù)組的對(duì)角線上的元素均為0。（5）頂點(diǎn)的度即為頂點(diǎn)所在的行或者列1的數(shù)目。例如：頂點(diǎn)V2的度為3，則V2所在行和列中的1的數(shù)目為3。
有向圖的數(shù)組存儲(chǔ)主要有以下特性：
（1）頂點(diǎn)數(shù)組長(zhǎng)度為圖的頂點(diǎn)數(shù)目n。邊數(shù)組為n X n的二維數(shù)組。（2）邊數(shù)組中，數(shù)組元素為1，即A[i][j] = 1,代表第i個(gè)頂點(diǎn)與第j個(gè)頂點(diǎn)鄰接，且i為尾，j為頭。 A[i][j] = 0代表頂點(diǎn)與頂點(diǎn)不鄰接。（3）在有向圖中，由于邊存在方向性，因此數(shù)組不一定為對(duì)稱數(shù)組。（4）對(duì)角線上元素為0。（5）第i行中，1的數(shù)目代表第i個(gè)頂點(diǎn)的出度。例如：頂點(diǎn)V1的出度為2，則頂點(diǎn)V1所在行的1的數(shù)目為2。（6）第j列中，1的數(shù)目代表第j個(gè)頂點(diǎn)的入度。例如：V3的入度為1，則V3所在列中1的數(shù)目為1。
圖5.3所示無(wú)向圖的存儲(chǔ)數(shù)組：
當(dāng)使用數(shù)組存儲(chǔ)時(shí)，主要有以下三個(gè)問(wèn)題：
（1）對(duì)于一個(gè)圖，若圖中的頂點(diǎn)數(shù)目過(guò)大，則無(wú)法使用鄰接矩陣進(jìn)行存儲(chǔ)。因?yàn)樵诜峙鋽?shù)組內(nèi)存時(shí)可能會(huì)導(dǎo)致內(nèi)存分配失敗。（2）對(duì)于某些稀疏圖（即頂點(diǎn)數(shù)目多，邊數(shù)目少），創(chuàng)建的數(shù)組大小很大，而真正存儲(chǔ)的有用信息又很少，這就造成了空間上的浪費(fèi)。（3）有時(shí)兩個(gè)點(diǎn)之間不止存在有一條邊，這是用鄰接矩陣就無(wú)法同時(shí)表示兩條以上的邊。
針對(duì)以上情況，提出了一種特殊的圖存儲(chǔ)方式，讓每個(gè)節(jié)點(diǎn)擁有的數(shù)組大小剛好就等于它所連接的邊數(shù)，由此建立一種鄰接表的存儲(chǔ)方式。
鄰接表存儲(chǔ)方法是一種數(shù)組存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第 i 個(gè)單鏈表中的結(jié)點(diǎn)依附于頂點(diǎn) Vi 的邊（對(duì)有向圖是以頂點(diǎn)Vi為尾的?。?。鏈表中的節(jié)點(diǎn)稱為表節(jié)點(diǎn)，共有 3個(gè)域，具體結(jié)構(gòu)見(jiàn)下圖：
表結(jié)點(diǎn)由三個(gè)域組成，adjvex存儲(chǔ)與Vi鄰接的點(diǎn)在圖中的位置，nextarc存儲(chǔ)下一條邊或弧的結(jié)點(diǎn)，data存儲(chǔ)與邊或弧相關(guān)的信息如權(quán)值。
除表節(jié)點(diǎn)外，需要在數(shù)組中存儲(chǔ)頭節(jié)點(diǎn)，頭結(jié)點(diǎn)由兩個(gè)域組成，分別指向鏈表中******個(gè)頂點(diǎn)和存儲(chǔ)Vi的名或其他信息。具體結(jié)構(gòu)如下圖：
采用鄰接表方式存儲(chǔ)圖 6.1 中的無(wú)向圖，繪圖過(guò)程中忽略邊節(jié)點(diǎn)的info信息，頭結(jié)點(diǎn)中的 data 域存儲(chǔ)頂點(diǎn)名稱。以V1頂點(diǎn)為例，V1頂點(diǎn)的鄰接頂點(diǎn)為V2、V3、V4，則可以創(chuàng)建3個(gè)表節(jié)點(diǎn)，表節(jié)點(diǎn)中adjvex分別存儲(chǔ)V2、V3、V4的索引1、2、3，按照此方式，得到的鄰接表為：
無(wú)向圖的鄰接表存儲(chǔ)特性：
（1）數(shù)組中頭節(jié)點(diǎn)的數(shù)目為圖的頂點(diǎn)數(shù)目。（2）鏈表的長(zhǎng)度即為頂點(diǎn)的度。例如：V1頂點(diǎn)的度為3，則以V1為頭節(jié)點(diǎn)的鏈表中表節(jié)點(diǎn)的數(shù)目為3。
例如：圖 6.3 所示的有向圖采用鄰接表存儲(chǔ)。
采用鄰接表方式存儲(chǔ)圖6.3中的有向圖，繪圖過(guò)程中忽略邊節(jié)點(diǎn)的info信息，頭結(jié)點(diǎn)中的data域存儲(chǔ)頂點(diǎn)名稱。以V1頂點(diǎn)為例，V1頂點(diǎn)的鄰接頂點(diǎn)為V2、V3、V4，但是以V1頂點(diǎn)為尾的邊只有兩條，即和因此，創(chuàng)建2個(gè)表節(jié)點(diǎn)。表節(jié)點(diǎn)中adjvex分別存儲(chǔ)V3、V4的索引2、3，按照此方式，得到的鄰接表為：
有向圖的鄰接表存儲(chǔ)特性：
（1）數(shù)組中表節(jié)點(diǎn)的數(shù)目為圖的頂點(diǎn)數(shù)目。（2）鏈表的長(zhǎng)度即為頂點(diǎn)的出度。例如V1的出度為2，V1為頭節(jié)點(diǎn)的鏈表中，表節(jié)點(diǎn)的數(shù)目為2。（3）頂點(diǎn)Vi的入度為鄰接表中所有adjvex值域?yàn)閕的表結(jié)點(diǎn)數(shù)目。例如：頂點(diǎn)V3的入度為4，則鏈表中所有adjvex值域?yàn)?的表結(jié)點(diǎn)數(shù)目為4。
注：圖采用鄰接表的方式表示時(shí)，其表示方式是不******的。這是因?yàn)樵诿總€(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中，各邊節(jié)點(diǎn)的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序。
對(duì)于有向圖而言，鄰接鏈表的缺陷是要查詢某個(gè)頂點(diǎn)的入度時(shí)需要遍歷整個(gè)鏈表，而逆鄰接鏈表在查詢某個(gè)頂點(diǎn)的出度時(shí)要遍歷整個(gè)鏈表。為了解決這些問(wèn)題，十字鏈表將鄰接鏈表和逆鄰接鏈表綜合了起來(lái)，而得到的一種十字鏈表。在十字鏈表中，每一條邊對(duì)應(yīng)一種邊節(jié)點(diǎn)，每一個(gè)頂點(diǎn)對(duì)應(yīng)為頂點(diǎn)節(jié)點(diǎn)。
注：采用十字鏈表存儲(chǔ)時(shí)，表頭節(jié)點(diǎn)仍然使用數(shù)組存儲(chǔ)，采用下標(biāo)索引方式獲取。
對(duì)于無(wú)向圖而言，其每條邊在鄰接鏈表中都需要兩個(gè)結(jié)點(diǎn)來(lái)表示，而鄰接多重表正是對(duì)其進(jìn)行優(yōu)化，讓同一條邊只用一個(gè)結(jié)點(diǎn)表示即可。鄰接多重表仿照了十字鏈表的思想，對(duì)鄰接鏈表的邊表結(jié)點(diǎn)進(jìn)行了改進(jìn)。
重新定義的邊結(jié)點(diǎn)結(jié)構(gòu)如下圖：
其中，ivex和jvex是指某條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表中的下標(biāo)。 ilink指向依附頂點(diǎn)ivex的下一條邊，jlink指向依附頂點(diǎn)jvex的下一條邊。info存儲(chǔ)邊的相關(guān)信息。
重新定義的頂點(diǎn)結(jié)構(gòu)如下圖：
圖 9.1 所示的無(wú)向圖，采用鄰接多重表存儲(chǔ)，以 V0 為例，頂點(diǎn)節(jié)點(diǎn)的data域存儲(chǔ)V0名稱，firstedge 指向(V0 , V1)邊，邊節(jié)點(diǎn)中的ilink指向依附V0頂點(diǎn)的下一條邊(V0 , V3)，jlink指向依附V1頂點(diǎn)的下一條邊(V1 , V2)，按照此方式建立鄰接多重表：
