圖（Graph）是數(shù)據(jù)結(jié)構(gòu)中最復(fù)雜的一種結(jié)構(gòu)染簇，線性表描述的是一對(duì)一關(guān)系，樹(shù)描述的是一對(duì)多關(guān)系模燥，而圖描述的是多對(duì)多關(guān)系咖祭。無(wú)論是一對(duì)一還是一對(duì)多，都有一個(gè)明確的切入點(diǎn)蔫骂，而圖卻不具備這種簡(jiǎn)單的屬性么翰。正因?yàn)榇耍P(guān)于圖的基礎(chǔ)知識(shí)也是最多辽旋，下面我們就先對(duì)這些基礎(chǔ)知識(shí)進(jìn)行梳理浩嫌。

圖的概念

圖的定義

圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V, E)补胚，其中 G 表示一個(gè)圖码耐， V 是圖 G 中頂點(diǎn)的集合， E 是圖 G 中邊的集合溶其。頂點(diǎn)骚腥，就是圖中的數(shù)據(jù)元素，邊則用來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系瓶逃。頂點(diǎn)是有窮非空的束铭，邊則可以為空集廓块。

有向邊和無(wú)向邊

邊，根據(jù)是否有方向契沫，分為無(wú)向邊和有向邊带猴。無(wú)向邊指頂點(diǎn)v_i到v_j之間的邊沒(méi)有方向，用(v_i, v_j)表示懈万。有向邊指頂點(diǎn)v_i到v_j之間的邊有方向拴清，也稱作弧，用<v_i, v_j>表示钞速，其中v_i稱為弧尾或初始點(diǎn)贷掖，v_j稱為弧頭或終端點(diǎn)，也就是箭頭從v_i指向v_j渴语，順序不能交換。如下圖所示昆咽，左邊的圖都是無(wú)向邊驾凶，右邊的圖都是有向邊：

邊的分類(lèi)

左圖可以表示為G₁ = (V₁, {E₁})，其中頂點(diǎn)集合V₁={A, B, C, D}掷酗，邊集合E₁={(A, B), (B, C), (C, D), (D, A), (A, C)}调违。右圖可以表示為G₂ = (V₂, {E₂})，其中頂點(diǎn)集合V₂={A, B, C, D}泻轰，弧集合E₂={<A, B>, <B, C>, <C, A>, <A, D>}技肩。

有向圖和無(wú)向圖

如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖為無(wú)向圖浮声。在無(wú)向圖中虚婿，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖泳挥。含有 n 個(gè)頂點(diǎn)的無(wú)向完全圖有 n(n-1)/2 條邊然痊。

同樣地，如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊屉符，則稱該圖為有向圖剧浸。在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧矗钟，則稱該圖為有向完全圖唆香。含有 n 個(gè)頂點(diǎn)的有向完全圖有 n(n-1) 條邊。

如下所示吨艇，左圖為無(wú)向完全圖躬它，右側(cè)為有向完全圖：

有向圖和無(wú)向圖

簡(jiǎn)單圖

在圖中，若不存在頂點(diǎn)到其自身的邊秸应，且同一條邊不重復(fù)出現(xiàn)虑凛，則稱這樣的圖為簡(jiǎn)單圖碑宴。我們要研究的圖都是簡(jiǎn)單圖。如下所示桑谍，都不是簡(jiǎn)單圖延柠，不屬于我們學(xué)習(xí)的范疇。

非簡(jiǎn)單圖示例

稀疏圖和稠密圖

有很少條邊或弧的圖稱為稀疏圖锣披，反之稱為稠密圖贞间。這是一個(gè)相對(duì)的概念。

網(wǎng)

帶權(quán)的圖稱為網(wǎng)雹仿，權(quán)指的是在圖的邊或弧上的數(shù)字增热，例如下圖就是一張帶權(quán)的圖：

網(wǎng)

子圖

假設(shè)有兩個(gè)圖G=(V, {E})和G'=(V', {E'})，如果V'∈V且E'屬于E胧辽，則稱G'為G的子圖峻仇。簡(jiǎn)言之，就是部分與整體的關(guān)系邑商。

頂點(diǎn)與邊的關(guān)系

對(duì)于無(wú)向圖G=(V, {E})摄咆，如果邊(v, v')∈E，則稱頂點(diǎn) v 和 v' 互為鄰接點(diǎn)人断，即 v 和 v' 相鄰接吭从，邊(v, v')依附于頂點(diǎn) v 和 v'，或者說(shuō)(v, v')與頂點(diǎn) v 和 v' 相關(guān)聯(lián)恶迈。頂點(diǎn) v 的度是和 v 相關(guān)聯(lián)的邊的數(shù)目涩金，記為TD(v)。無(wú)向圖的邊的個(gè)數(shù)和頂點(diǎn)度數(shù)的關(guān)系如下：

無(wú)向圖邊和度

對(duì)于有向圖G=(V, {E})暇仲，如果弧<v, v'>∈E步做，則稱頂點(diǎn) v 鄰接到 v'，v' 鄰接自 v熔吗，弧<v, v'>和頂點(diǎn) v, v'相關(guān)聯(lián)辆床。以頂點(diǎn) v 為頭的弧的數(shù)目稱為 v 的入度，記為ID(v)桅狠，以 v 為尾的弧的數(shù)目稱為 v 的出度讼载，記為OD(v)，頂點(diǎn) v 的度為TD(v) = ID(v) + OD(v)中跌。有向圖的弧的個(gè)數(shù)和出度咨堤、入度的關(guān)系如下：

有向圖弧和度

路徑

無(wú)向圖G=(V, {E})中從頂點(diǎn) v 到 v' 的路徑是一個(gè)頂點(diǎn)序列(v=v_i,0,v_i,1,...,v_i,m=v')，其中(v_i,j-1,v_i,j)∈E漩符，1≤j≤m一喘。

如果是有向圖，則路徑也是有向的，頂點(diǎn)序列滿足<v_i,j-1, v_i,j>∈E凸克，1≤j≤m议蟆。

路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。

第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)萎战。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑咐容。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路蚂维，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)戳粒。

連通圖

在無(wú)向圖G中，如果從頂點(diǎn) v 到 v' 有路徑虫啥，則稱 v 和 v' 是連通的蔚约。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn) v_i,v_j∈V，v_i 和 v_j 都是連通的涂籽，則稱G是連通圖苹祟。無(wú)向圖中的極大連通子圖稱為連通分量。如下圖评雌，左圖不是連通圖苔咪，但它有兩個(gè)連通分量：

連通圖

在有向圖G中，如果對(duì)于每一對(duì)v_i,v_j∈V柳骄、v_i≠v_j，從 v_i 到 v_j 都存在路徑箕般，則稱G是強(qiáng)連通圖耐薯。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。如下圖所示丝里，雖然它不是強(qiáng)連通圖曲初，但它有兩個(gè)強(qiáng)連通分量：

強(qiáng)連通圖

生成樹(shù)和有向樹(shù)

連通圖的生成樹(shù)是一個(gè)極小的連通子圖，它含有圖中全部的 n 個(gè)頂點(diǎn)杯聚，但只有足以構(gòu)成一棵樹(shù)的 n-1 條邊臼婆。如下所示，圖1是一個(gè)連通圖幌绍，圖2和圖3都是它的生成樹(shù)：

生成樹(shù)

n個(gè)頂點(diǎn)和 n-1 條邊是構(gòu)成生成樹(shù)的必要條件颁褂，但是它并不充分，如下所示傀广，就不是一個(gè)生成樹(shù)：

非生成樹(shù)

如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0颁独，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)伪冰。一個(gè)有向圖的生成森林由若干棵有向樹(shù)組成誓酒，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧贮聂。如下圖所示靠柑，圖1就可以拆分成圖2和圖3兩棵有向樹(shù)寨辩。

生成森林

圖的存儲(chǔ)

線性表和圖都有一個(gè)明確的切入點(diǎn)，但是對(duì)圖而言歼冰，每個(gè)頂點(diǎn)都可以當(dāng)做是起點(diǎn)靡狞，而且每個(gè)頂點(diǎn)之間都可能有邏輯關(guān)系，也就是說(shuō)停巷，單純的使用數(shù)組或鏈表是無(wú)法完成圖的存儲(chǔ)的耍攘。圖的存儲(chǔ)當(dāng)前主要有以下五種方式：

1. 鄰接矩陣

圖的鄰接矩陣（Adjacency Matrix）存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)表示圖。一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息畔勤，一個(gè)二維數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中的邊或弧的信息蕾各。

設(shè)G有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣庆揪，定義為：

鄰接矩陣

下面式曲，我們就無(wú)向圖、有向圖和網(wǎng)分別演示鄰接矩陣的存儲(chǔ)方式缸榛。

無(wú)向圖

無(wú)向圖的鄰接矩陣

其中主對(duì)角線的值為0吝羞，表示頂點(diǎn)到其本身沒(méi)有邊。無(wú)向圖的鄰接矩陣一定是對(duì)稱的内颗，也就是以主對(duì)角線劃分的右上方和左下方對(duì)稱钧排。從矩陣中我們可以獲取以下信息：

• 判斷兩個(gè)頂點(diǎn)之間是否有邊
• 獲取某個(gè)頂點(diǎn)的度，只需要求第 i 行或第 i 列的和即可均澳。
• 獲取某個(gè)頂點(diǎn)的所有臨界點(diǎn)恨溜，只需要遍歷第 i 行即可。

有向圖

有向圖的表示和無(wú)向圖類(lèi)似找前，如下所示：

有向圖的鄰接矩陣

網(wǎng)

因?yàn)榫W(wǎng)的每條邊都有權(quán)值糟袁，所以對(duì)應(yīng)的公式稍有改變，如下所示：

網(wǎng)的鄰接矩陣

這里∞表示的是不可能出現(xiàn)的值躺盛。網(wǎng)的鄰接矩陣存儲(chǔ)示例如下：

網(wǎng)的鄰接矩陣

2. 鄰接表

數(shù)組的優(yōu)缺點(diǎn)我們都已經(jīng)熟知项戴，那么使用鄰接矩陣就一定會(huì)面臨空間浪費(fèi)的問(wèn)題，上述示例中0或者∞越多槽惫，對(duì)應(yīng)圖中邊數(shù)相對(duì)于頂點(diǎn)數(shù)而言較少時(shí)周叮，空間的使用率也就越低。鄰接表的思想和哈希表類(lèi)似躯枢，使用數(shù)組結(jié)合鏈表的方式來(lái)存儲(chǔ)圖则吟。

無(wú)向圖

鄰接表使用一個(gè)數(shù)組來(lái)存儲(chǔ)每個(gè)頂點(diǎn)，數(shù)組的每一位都包含一個(gè)鏈表锄蹂，用來(lái)存儲(chǔ)與此頂點(diǎn)相鄰的邊氓仲，示例如下：

無(wú)向圖的鄰接表

從鄰接表中，也可以輕易地獲取到頂點(diǎn)、邊和度的值敬扛。

有向圖

有向圖的鄰接表和無(wú)向圖類(lèi)似晰洒，但是它獲取出度容易，獲取入度卻比較困難啥箭，如下所示：

有向圖鄰接表

獲取一個(gè)頂點(diǎn)的出度只需要計(jì)算鏈表的長(zhǎng)度即可谍珊，但是入度卻沒(méi)有有效的獲取方式，所以通常還會(huì)建立一個(gè)逆鄰接表作為補(bǔ)充急侥，如下所示：

有向圖逆鄰接表

網(wǎng)

用鄰接表來(lái)存儲(chǔ)網(wǎng)的結(jié)構(gòu)只需要增加一個(gè)weight字段即可砌滞，這里不再演示。

3. 十字鏈表

鄰接表在表示有向圖時(shí)坏怪，需要鄰接表和逆鄰接表兩張表配合使用贝润，較為繁瑣，我們可以把鄰接表和逆鄰接表結(jié)合為一張表铝宵，這就是十字鏈表打掘。

十字鏈表也使用數(shù)組來(lái)存儲(chǔ)頂點(diǎn)，只是每一位數(shù)據(jù)除了頂點(diǎn)外鹏秋，還有兩個(gè)鏈表分別表示出邊表和入邊表尊蚁，數(shù)據(jù)的結(jié)構(gòu)如下所示：

頂點(diǎn)結(jié)構(gòu)定義

邊表的結(jié)構(gòu)也有所改變，結(jié)構(gòu)如下：

邊表結(jié)構(gòu)定義

其中侣夷，tailvex表示弧起點(diǎn)在頂點(diǎn)表的下標(biāo)横朋，headvex表示弧終點(diǎn)在頂點(diǎn)表的下標(biāo)，headlink是入邊表指針域百拓，指向下一個(gè)終點(diǎn)相同的邊叶撒，taillink是出邊表指針域，指向下一個(gè)起點(diǎn)相同的邊耐版。

接下來(lái)，我們以下圖為例压汪，演示十字鏈表的建立過(guò)程：

圖

首先粪牲，把全部頂點(diǎn)存儲(chǔ)起來(lái)，如下所示：

存儲(chǔ)頂點(diǎn)

然后止剖，我們建立頂點(diǎn)v₀的出邊表腺阳，可以發(fā)現(xiàn)只有<v₀, v₃>這一條邊，所以它的出邊表如下：

出邊表

同理穿香，其他頂點(diǎn)的出邊表如下：

出邊表完整表

現(xiàn)在亭引，我們來(lái)建立入邊表，對(duì)于頂點(diǎn)v₀皮获，它的入邊有兩條焙蚓，分別是<v₁, v₀>和<v₂, v₀>。可以看到购公，這兩個(gè)邊在出邊表中已經(jīng)存在了萌京，直接為其建立起關(guān)系即可，如下所示：

入邊表

同理建立起其他頂點(diǎn)的入邊表宏浩，結(jié)果如下：

入邊表完整表

可以看到知残，十字鏈表除了結(jié)構(gòu)較為復(fù)雜之外，不僅解決了鄰接表無(wú)法同時(shí)獲取入度和出度的問(wèn)題比庄，也沒(méi)有增加所需的時(shí)間復(fù)雜度等求妹，因此十分適合有向圖的存儲(chǔ)。

4. 鄰接多重表

十字鏈表是針對(duì)有向圖的優(yōu)化佳窑，而鄰接表在表示無(wú)向圖時(shí)也存在一定的問(wèn)題制恍。比如我們要把下圖的邊(v₂, v₀)刪除，在鄰接表中就要?jiǎng)h除兩個(gè)位置：

無(wú)向圖的鄰接表刪除數(shù)據(jù)

可以看到华嘹，這是因?yàn)閿?shù)據(jù)的重復(fù)造成的吧趣，所以我們可以仿照十字鏈表的方式構(gòu)造一個(gè)鄰接多重表，來(lái)解決以上問(wèn)題耙厚。為此强挫，需要重新定義邊表結(jié)構(gòu)，如下：

鄰接多重表的邊表結(jié)構(gòu)

其中薛躬，ivex和jvex是某條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表的下標(biāo)俯渤，ilink表示依附于頂點(diǎn)ivex的下一條邊，jlink表示依附于頂點(diǎn)jvex的的下一條邊型宝。

有了十字鏈表的經(jīng)驗(yàn)八匠，構(gòu)建一個(gè)鄰接多重表十分容易，我們以上圖為例趴酣，首先建立好頂點(diǎn)結(jié)點(diǎn)和邊表結(jié)點(diǎn)梨树，如下所示：

建立結(jié)點(diǎn)

這里需要注意的是，邊表的每個(gè)結(jié)點(diǎn)僅出現(xiàn)一次岖寞，接下來(lái)我們按照規(guī)定把這些結(jié)點(diǎn)間關(guān)系連接起來(lái)即可抡四，如下所示：

鄰接多重表

5. 邊集數(shù)組

如果我們僅關(guān)注邊的操作，還可以使用邊集數(shù)組仗谆，它由兩個(gè)一維數(shù)組組成指巡，一個(gè)數(shù)組用來(lái)存儲(chǔ)頂點(diǎn)的信息，另一個(gè)數(shù)組存儲(chǔ)邊的信息隶垮。邊的數(shù)組的每個(gè)元素都由一條邊的起點(diǎn)下標(biāo)藻雪、終點(diǎn)下標(biāo)和權(quán)組成。這個(gè)存儲(chǔ)方式主要用于尋找連通網(wǎng)的最小生成樹(shù)算法：克魯斯卡爾算法狸吞。

我是飛機(jī)醬勉耀，如果您喜歡我的文章指煎，可以關(guān)注我~

編程之路，道阻且長(zhǎng)瑰排。唯贯要，路漫漫其修遠(yuǎn)兮，吾將上下而求索椭住。