圖(Graph)是由頂點和連接頂點的邊構(gòu)成的離散結(jié)構(gòu)。在計算機科學(xué)中，圖是最靈活的數(shù)據(jù)結(jié)構(gòu)之一，很多問題都可以使用圖模型進行建模求解。

圖(Graph)通常會放在樹(Tree)后面介紹，樹可以說是圖的特例。

一、圖的基礎(chǔ)概念

圖的結(jié)構(gòu)很簡單，就是由頂點 V 集和邊 E 集構(gòu)成，因此圖可以表示成 G=(V, E) 。

上圖就是無向圖，我們可以說這張圖中，有點集 V=\{1, 2, 3, 4, 5, 6\} ，邊集 E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\} 。在無向圖中，邊 (u, v) 和邊 (v, u) 是一樣的，簡而言之，對稱。

有向圖也很好理解，就是加上了方向性，頂點 (u, v) 之間的關(guān)系和頂點 (v,u) 之間的關(guān)系不同，后者或許不存在。例如，地圖應(yīng)用中必須存儲單行道的信息，避免給出錯誤的方向。

加權(quán)圖：與加權(quán)圖對應(yīng)的就是無權(quán)圖，也叫等權(quán)圖。如果一張圖不含權(quán)重信息，我們就認為邊與邊之間沒有差別。不過，具體建模的時候，很多時候都需要有權(quán)重。

還有很多細化的概念，比如：無向圖中，任意兩個頂點間都有邊，稱為無向完全圖；加權(quán)圖起一個新名字，叫網(wǎng)(network)……等。

兩個重要關(guān)系：

（1）鄰接(adjacency)：鄰接是兩個頂點之間的一種關(guān)系。如果圖包含 (u,v) ，則稱頂點 v 與頂點 u 鄰接。當(dāng)然，在無向圖中，這也意味著頂點 u 與頂點 v 鄰接。

（2）關(guān)聯(lián)(incidence)：關(guān)聯(lián)是邊和頂點之間的關(guān)系。在有向圖中，邊 (u,v) 從頂點 u 開始關(guān)聯(lián)到 v ，或者相反，從 v 關(guān)聯(lián)到 u 。注意，有向圖中，邊不一定是對稱的，有去無回是完全有可能的。細化這個概念，就有了頂點的入度(in-degree)和出度(out-degree)。無向圖中，頂點的度就是與頂點相關(guān)聯(lián)的邊的數(shù)目，沒有入度和出度。在有向圖中，頂點10有2個入度， 3\rightarrow10 ， 11\rightarrow10 ，但是沒有從10指向其它頂點的邊，因此頂點10的出度為0。

路徑(path)：依次遍歷頂點序列之間的邊所形成的軌跡。注意，依次就意味著有序，先1后2和先2后1不一樣。

簡單路徑：沒有重復(fù)頂點的路徑稱為簡單路徑。也就是沒有環(huán)。

環(huán)：包含相同的頂點兩次或者兩次以上。圖1-3中的頂點序列 <1,2,4,3,1> ，1出現(xiàn)了兩次，當(dāng)然還有其它的環(huán)，比如 <1,4,3,1> 。

無環(huán)圖：沒有環(huán)的圖，其中，有向無環(huán)圖有特殊的名稱，叫做DAG(Directed Acyline Graph)（記住，DAG具有一些很好性質(zhì)，比如很多動態(tài)規(guī)劃的問題都可以轉(zhuǎn)化成DAG中的最長路徑、最短路徑或者路徑計數(shù)的問題）。

下面這個概念很重要：

連通的：無向圖中每一對不同的頂點之間都有路徑。如果這個條件在有向圖里也成立，那么就是強連通的。圖1-4中的圖不是連通的，我絲毫沒有侮辱你智商的意思，我只是想和你說，這圖是我畫的，頂點標(biāo)簽有點小，應(yīng)該看到a和d之間沒有通路。

（1）連通分支：不連通的圖是由2個或者2個以上的連通分支的并。這些不相交的連通子圖稱為圖的連通分支。

（2）有向圖的連通分支：將有向圖的方向忽略后，任何兩個頂點之間總是存在路徑，則該有向圖是弱連通的。有向圖的子圖是強連通的，且不包含在更大的連通子圖中，則可以稱為圖的強連通分支。圖1-5中，a、e沒有到\{b,c,d\}中的頂點的路徑，所以各自是獨立的連通分支。因此，圖1-5中的圖有三個強連通分支，用集合寫出來就是：\{\{a\}, \{e\}, \{b, c, d\}\}（已經(jīng)用不同顏色標(biāo)出）。

關(guān)節(jié)點(割點)：某些特定的頂點對于保持圖或連通分支的連通性有特殊的重要意義。如果移除某個頂點將使圖或者分支失去連通性，則稱該頂點為關(guān)節(jié)點。如圖中的c。

雙連通圖：不含任何關(guān)節(jié)點的圖。

關(guān)節(jié)點的重要性不言而喻。如果你想要破壞互聯(lián)網(wǎng)，你就應(yīng)該找到它的關(guān)節(jié)點。同樣，要防范敵人的攻擊，首要保護的也應(yīng)該是關(guān)節(jié)點。在資源總量有限的前提下，找出關(guān)節(jié)點并給予特別保障，是提高系統(tǒng)整體穩(wěn)定性和魯棒性的基本策略。

橋(割邊)：和關(guān)節(jié)點類似，刪除一條邊，就產(chǎn)生比原圖更多的連通分支的子圖，這條邊就稱為割邊或者橋。