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

圖的概念

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

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

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

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

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

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

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

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

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

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

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

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

上圖中右邊的那些子圖都是屬于原圖的子圖，可以看出子圖可以產(chǎn)生非常多的形態(tài)，有向圖 也是相同的概念，不過相對于 無向圖 來說，有向圖能夠生成的子圖更少一些，因為它的邊是有方向的。

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

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

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

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

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

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

• (5) 鄰接點：兩個有邊的結(jié)點就是鄰接點

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

推薦：《2021年P(guān)HP面試題大匯總（收藏）》《php視頻教程》