圖的概念和存儲(chǔ)結(jié)構(gòu)

隨著學(xué)習(xí)的深入，我們的知識(shí)也在不斷的擴(kuò)展豐富。樹結(jié)構(gòu)有沒有讓大家蒙圈呢？相信我，學(xué)完圖以后你就會(huì)覺得二叉樹簡(jiǎn)直是簡(jiǎn)單得沒法說了。其實(shí)我們說所的樹，也是圖的一種特殊形式。

圖的概念

還記得我們學(xué)習(xí)樹的第一篇文章時(shí)看到的那張關(guān)于樹的圖片嗎？

在當(dāng)時(shí)，我們就說過，圖c 不是一顆樹，而是一個(gè)圖。為什么呢？從樹的定義我們可以看出，樹只能有一個(gè)根結(jié)點(diǎn)，平級(jí)之間不能有聯(lián)系，可以有多個(gè)子結(jié)點(diǎn)。而圖就不用遵守這些規(guī)則，圖的特點(diǎn)就是結(jié)點(diǎn)之間都可以互相有聯(lián)系。比如下圖這樣的都是圖。

在上面所畫的圖中，圖b 是的箭頭的，而 圖a 的連接線是沒有箭頭的，像這樣有明確的方向的指向的圖就叫做 有向圖 。而沒有箭頭的，也就是沒有方向指向的圖就叫作 無向圖 。

我們先將目光移到 圖a-1 ，其實(shí)它就是把 圖a 旋轉(zhuǎn)了一下。大家能看出來了嗎？如果忽略掉結(jié)點(diǎn) 4 和 1 之間的連線，那么它就是一顆樹。是不是和我們上面關(guān)于樹的圖中的 圖c 的概念一致了。

關(guān)于圖的比較正式的官方定義是：

圖（Graph）G 由兩個(gè)集合 V 和 E 組成，記為 G=(V, E) ，其中 V 是頂點(diǎn)的有窮非空集合，E 是 V 中頂點(diǎn)的有窮集合，這些頂點(diǎn)偶對(duì)稱為邊。

在 有向圖 中，連接兩點(diǎn)的那個(gè)線段，從開始的結(jié)點(diǎn)到指向的那個(gè)結(jié)點(diǎn)可以記為 <x, y> 。<x, y> 和 <y, x> 是兩個(gè)不同的邊，也可以叫作 弧 。根據(jù) 圖a ，我們可以看到這個(gè)圖中有 <1, 2> 、 <2, 1> 、 <1, 3> 、 <3, 1> 、 <1, 4> 、 <4, 1> 、 <3, 4> 、 <4, 3> 這幾條邊。而 圖b 中，因?yàn)樗怯邢驁D，所以它的邊只有 <1, 2> 、 <1, 3> 、 <3, 4> 、 <4, 1> 這四條。

是不是感覺在看上面的圖片的時(shí)候還比較清晰，一看這個(gè)定義就一臉懵逼了？像這種定義，如果你是需要考試的同學(xué)，那就還是要背下來的。如果只是像我一起想以學(xué)習(xí)應(yīng)用或者了解為主的話，就不用去死記硬背了。V 就是結(jié)點(diǎn)，E 就是這些這些結(jié)點(diǎn)之間的關(guān)系，兩個(gè)頂點(diǎn)之間的關(guān)系，也就是圖上的那些連接結(jié)點(diǎn)的線段就是邊。

OK，這三個(gè)最最基礎(chǔ)的概念搞明白了，我們就繼續(xù)學(xué)習(xí)其它的和圖有關(guān)的那一大車術(shù)語！

圖的相關(guān)術(shù)語

首先，我們用 n 來表示圖中頂點(diǎn)的數(shù)目，用 e 來表示邊的數(shù)目，記住這兩個(gè)代號(hào)。

• （1）子圖：假設(shè)有兩個(gè)圖 G=(V, E) 和 G^'=(V^', E^') 如果 V^' 包含于 V 且 E^' 包含于 E ，則稱G^' 為 G 的子圖

上圖中右邊的那些子圖都是屬于原圖的子圖，可以看出子圖可以產(chǎn)生非常多的形態(tài)，有向圖 也是相同的概念，不過相對(duì)于 無向圖 來說，有向圖能夠生成的子圖更少一些，因?yàn)樗倪吺怯蟹较虻摹?/p>

• (2) 無向完全圖和有向完全圖：對(duì)于無向圖，若具有 n(n-1)/2 條邊，就是無向完全圖。對(duì)于有向圖，若具有 n(n-1) 條孤，就稱為有向完全圖。（參考完全二叉樹）

其實(shí)完全圖的概念就是圖中所有相鄰的結(jié)點(diǎn)都有邊能夠連結(jié)在一起。

對(duì)于 有向圖 來說，雖說邊是有方向的，當(dāng)然我們也可以定義一個(gè)來回的方向，比如 <1, 2> 和 <2, 1> ，在有向圖中我們就要畫上兩個(gè)相反方向的箭頭表示可以從1到2也可以從2到1。而 無向圖 中則是用一個(gè)邊來代替這兩個(gè)邊的概念了，本身的那一條沒有箭頭方向的邊就是雙向的。

• (3) 稀疏圖和稠密圖：有很少條邊或孤（如e<nlog₂n）的圖稱為稀疏圖，反之稱為稠密圖

• (4) 權(quán)和網(wǎng)：在實(shí)際應(yīng)用中，每條邊或孤可以標(biāo)上具有某種意義的值，就像地圖上的距離一樣，這些數(shù)值就稱為權(quán)。帶權(quán)的圖就可以稱為網(wǎng)

最上方的的圖片上 圖a-2 和 圖b-1 的邊上的數(shù)字代表的就是權(quán)重。這兩張圖就可以稱為網(wǎng)圖。權(quán)重的概念我們后面在講相關(guān)的算法時(shí)會(huì)學(xué)習(xí)到，從這兩張圖中，我們其實(shí)就可以很明顯的看出，如果要從 結(jié)點(diǎn)1 走到 結(jié)點(diǎn)4 的話，并不是直接走 <1, 4> 這條邊，而是走 <1, 3> 、 <3, 4> 這條路線更快些。

• (5) 鄰接點(diǎn)：兩個(gè)有邊的結(jié)點(diǎn)就是鄰接點(diǎn)

• (6) 度、入度和出度：頂點(diǎn) v 的度就是指和 v 相關(guān)聯(lián)的邊的數(shù)目。對(duì)于有向圖來說，箭頭指向其它結(jié)點(diǎn)的就是出度，指向自己的就是入度

還是繼續(xù)來看 圖b 。結(jié)點(diǎn)1 有兩個(gè)出度，一個(gè)入度。這個(gè)貌似不用解釋太多了吧。

• (7) 路徑和路徑長(zhǎng)度：從某一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)過的所有頂點(diǎn)就是路徑。如果是有向圖，那么它的路徑就是按照箭頭的方向。路徑長(zhǎng)度就是一條路徑上經(jīng)過的邊或孤的數(shù)量

• (8) 回路或環(huán)：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)

• (9) 連通、連通圖和連通分量：如果某兩個(gè)結(jié)點(diǎn)之間是有路徑的，就稱這兩個(gè)結(jié)點(diǎn)是連通的。如果整個(gè)圖中所有的結(jié)點(diǎn)都可以是互相連通的，則這個(gè)圖就是連通圖。連通分量就是無向圖非連通圖中的極大連通子圖。

包括后面的三個(gè)概念也在這張圖中一并給出了。在 無向圖 中，連通分量就等于極大連通子圖，在這個(gè)圖中，我們有兩個(gè)連通分量。

• (10) 極大連通子圖：連通子圖所能含有的最大結(jié)點(diǎn)數(shù)，如果再增加一個(gè)結(jié)點(diǎn)那么這個(gè)子圖就不是連通圖了

• (11) 生成樹：一個(gè)極小連通子圖，它含有圖中全部的頂點(diǎn)，但只有足以構(gòu)成一顆樹的 n-1 條邊，這樣的連通子圖就是連通圖的生成樹

其實(shí)就是通過一條路徑，能夠讓圖中所有的結(jié)點(diǎn)串聯(lián)起來。在連通分量的圖中，我們就根據(jù)兩個(gè)連通分量生成了兩個(gè)最小生成樹。它們的 連通分量1 的生成樹的結(jié)點(diǎn)并不一定非要是這種結(jié)構(gòu)，我們可以讓 結(jié)點(diǎn)4 在 結(jié)點(diǎn)2 下，這取決于我們?nèi)绾伪闅v來生成這顆最小生成樹。

最上面我們的 圖a 的最小生成樹其實(shí)就可以是 圖a-1 去掉那條紅色虛線。當(dāng)然，也可以讓 結(jié)點(diǎn)4 也在 結(jié)點(diǎn)1 下面，同樣也是取決于我們的程序要如何遍歷圖來生成什么樣的樹。

• (12)生成森林：在非連通圖中，每一個(gè)連通分量都可以生成一個(gè)連通生成樹，這樣就構(gòu)成了整個(gè)非連通圖的生成森林

是不是看完之后暈頭轉(zhuǎn)向了？沒關(guān)系，這些術(shù)語我們?cè)诤竺娴膶W(xué)習(xí)中將會(huì)經(jīng)常用到，而且這還不是最全面的。大家可以根據(jù)參考書目和其它學(xué)習(xí)資料來對(duì)圖的相關(guān)術(shù)語進(jìn)行更加深入的學(xué)習(xí)和理解。

總結(jié)

圖的概念介紹得差不多了，大家可以消化消化再繼續(xù)學(xué)習(xí)后面的內(nèi)容。這只是個(gè)開始，不少同學(xué)會(huì)不會(huì)覺得這玩意對(duì)比 樹 結(jié)構(gòu)一下子又提升了好多。不用怕，在學(xué)習(xí)完后面的知識(shí)后，即使你暫時(shí)還沒有搞明白 圖 相關(guān)的內(nèi)容，但你一定對(duì) 樹 結(jié)構(gòu)的理解會(huì)更加深入了。為什么呢？樹 其實(shí)就是沒有回路的圖，它們的遍歷無外乎都是通過深度或者廣度來實(shí)現(xiàn)的，只是圖更復(fù)雜一點(diǎn)而已。這下是不是感覺未來還是有點(diǎn)希望的啦？學(xué)習(xí)，往往是一個(gè)漸進(jìn)的過程，當(dāng)前的知識(shí)和過去的知識(shí)總會(huì)有所關(guān)聯(lián)的，先不用想太多，一步一步的踏實(shí)走下去吧！

參考資料：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研