1.8 圖
圖（Graph）是一種非線性的數據結構，圖在實際生活中有很多例子，比如交通運輸網、地鐵網絡，朋友關系等都可以抽象成圖結構。圖G是由V（G）和E（G）兩個集合組成的，記為G=（V,E），其中V（G）是頂點（vertexes）的非空有限集，E（G）是邊（edges）的有限集合。
圖的基本術語
頂點：圖中的每個節點就是頂點。
邊：圖中兩個頂點之間的線就叫作邊。
路徑：路徑就是從某個頂點到另一個頂點所要經過的頂點序列。
路徑長度：一條路徑上經過的邊的數量。
回路：一條路徑的起點和終點為同一個頂點。
度：在無向圖中，點的度是指與該點相連的邊的數量。在有向圖中，分為出度和入度，指向該點的邊數稱為入度；反之，則稱為出度。有向圖某點度的大小等于該點出度和入度之和。
1.8.1 圖的分類
圖的種類比較多，比如無向圖、有向圖、完全圖、加權圖等，下面我們來看一下。
1. 無向圖
如果一個圖結構中，所有的邊都沒有方向，那么這種圖稱為無向圖，無向圖類似于情侶關系，比如在情侶中A喜歡B，那么B也喜歡A。由于無向圖中的邊沒有方向，所以在表示邊的時候對兩個頂點的順序沒有要求，用小括號（?,?）表示邊。如圖1-62所示，頂點V2和頂點V4之間的邊，可以表示為（V2，V4），也可以表示為（V4，V2）。
?圖1-62
對應的頂點集合與邊集合如下：
2. 有向圖
如果一個圖結構中，所有的邊都有方向，那么這種圖稱為有向圖。有向圖類似于“單相思”，比如A喜歡B，但B不一定喜歡A。在有向圖中，與一個頂點相關聯的邊有出邊和入邊之分。由于有向圖的邊是有方向的，所以在表示邊的時候，對兩個頂點的順序就有要求。用尖括號＜?,?＞表示邊，如圖1-63所示，＜V1，V3＞表示從頂點V1到頂點V3，而＜V3，V1＞表示從頂點V3到頂點V1。
?圖1-63
對應的頂點集合與邊集合如下：
3. 完全圖
在完全圖中任意一對頂點之間都有邊相連。根據邊是否有方向，完全圖又可以分為無向完全圖與有向完全圖，在無向圖中如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖，同理在有向圖中如果任意兩個頂點之間都存在方向相反的兩條邊，則稱該圖為有向完全圖，如圖1-64所示。有向完全圖有n?(n-1)條邊，無向完全圖有n?(n-1)/2條邊。
?圖1-64
4. 混合圖
在一個圖中，邊既包括有方向，也包括無方向的圖稱為混合圖。
5. 稀疏圖
邊很少的圖稱為稀疏圖。
6. 稠密圖
邊相對比較多的圖稱為稠密圖。
7. 子圖
對于兩個圖G=(V,E)和G′=(V′,E′)，如果V′是V的子集并且E′也是E的子集，我們稱G′是G的子圖，如圖1-65所示。
?圖1-65
8. 簡單圖
在圖中如果任意兩頂點之間最多只有一條邊（在有向圖中為兩頂點之間每個方向最多只有一條邊），邊集中不存在環，這樣的圖稱為簡單圖。如圖1-66所示，都不屬于簡單圖。
?圖1-66
9. 加權圖
對圖G的每一條邊e來說，都對應于一個值v，我們把這個v稱為e的權，把這樣的圖G稱為加權圖，這個v可以表示兩點之間的距離、花費時間等。如果每條邊沒有對應的值，我們稱它為非加權圖，對于非加權圖兩點之間如果有邊用1表示，如果沒邊可以用0表示，如圖1-67所示。
?圖1-67
10. 有向無環圖
如果一個有向圖無法從某個頂點出發經過若干條邊回到該點，則這個圖是一個有向無環圖，如圖1-68所示。
?圖1-68
11. 連通圖
在無向圖中，對于每一對頂點V1和V2有路徑相連，則稱此圖是連通圖，如圖1-69所示。
?圖1-69
12. 強連通圖
在有向圖中，對于任意一對頂點V1和V2都存在從V1到V2和V2到V1的路徑，則稱此圖是強連通圖。
13. 弱連通圖
把有向圖的所有有向邊替換成無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則原圖就是弱連通圖。可以看到無論是強連通圖，還是弱連通圖，都是對于有向圖來說的。
1.8.2 圖的表示方式
圖的表示方式常見的有三種，分別是鄰接矩陣、鄰接表和邊集數組。鄰接矩陣是表示圖最直觀的一種方式，可以看到各頂點之間的關系，而鄰接表可以看到一個頂點指向其他頂點的數量，而邊集數組就是記錄每條邊的起點、終點和權值的數組。
1. 鄰接矩陣
鄰接矩陣就是使用一個n?n（n是圖的頂點個數）的矩陣A。對于無向圖來說，如果頂點i和頂點j之間相連，則把A[i][j]和A[j][i]標記為相同的值。如果是非加權圖，標記為1即可，如果是加權圖，標記為這條邊的權值。對于有向圖來說，如果是頂點i指向頂點j，只需要記錄A[i][j]的值即可，如圖1-70所示。
?圖1-70
我們看到對于簡單無向圖來說，它的鄰接矩陣是關于從左上角到右下角這條線對稱的，因為在無向圖中A[i][j]和A[j][i]的值是一樣的。對于有向圖來說，A[i][?]不為0的個數就是點i的出度個數，A[?][j]不為0的個數是點j的入度個數。
2. 鄰接表
對于稠密圖（邊相對比較多）來說，使用鄰接矩陣表示會更合適一些，如果是稀疏圖（邊相對比較少），使用鄰接矩陣就會造成矩陣中很多元素是0，從而導致存儲空間的浪費，這個時候可以考慮使用鄰接表。鄰接表是一種鏈式存儲結構，對于圖中的每一個頂點v都可以建一個單向鏈表，將頂點v相關的信息存儲在表頭，鏈表的其余節點用來存放和頂點v相連的頂點。如果是加權圖，需要在鏈表的節點中添加權值，否則可以不加，如圖1-71所示。
?圖1-71
鄰接表的特點：
?通過鄰接表方便找任一頂點的所有鄰接點。
?節約稀疏圖的存儲空間。
?方便計算無向圖的度，方便計算有向圖的出度。
對于有向圖的入度，使用鄰接表的方式就不太好算了，這時候還可以使用十字鏈表來表示圖，圖的十字鏈表和鄰接表類似，都是使用鏈表的方式，不過十字鏈表的頭節點會有兩個指針，分別指向兩個鏈表，一個是指向出度的鏈表，另一個是指向入度的鏈表，十字鏈表更方便查找一個頂點的出度和入度。
3. 邊集數組
邊集數組是使用一維數組來存儲邊，一維數組中每個元素由3個成員組成，分別是邊的起點、終點、權值，當然也可以寫成二維數組edges[m][3]，其中m是邊的數量，如圖1-72所示。
?圖1-72
1.8.3 圖的遍歷
圖的遍歷方法主要有深度優先搜索（DFS）和廣度（寬度）優先搜索（BFS），關于DFS和BFS我們在第9章也會介紹。
1. 深度優先搜索（DFS）
DFS的思想類似于樹的前序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，沿著一個方向一直訪問下去，當訪問到這個方向上最后一個頂點（這個頂點之后沒有下一個頂點了，或者和這個頂點相連的都被訪問完了）的時候，往回退一步，查看和上一個頂點相連的有沒有可訪問的，如果有就繼續重復上面的方式沿著另一個方向繼續訪問，如果沒有可訪問的，就再回到上一個頂點，重復同樣的步驟，如圖1-73所示。如果一個頂點被訪問之后，就不能再被訪問了，所以需要使用一個數組visited來記錄哪些頂點被訪問過。
?圖1-73
可以看一下代碼的大致結構，這里的圖使用的是鄰接表，假設從頂點u開始訪問。
這里只是從圖的一個頂點開始訪問，如果要遍歷整個圖，需要從圖的所有頂點開始，否則在有向圖中有些頂點是訪問不到的。我們來看一下圖的訪問過程，如圖1-74所示，這里選擇的是非加權有向圖。
?圖1-74
測試代碼如下：
打印結果：0,1,3,4,2,
2. 廣度優先搜索（BFS）
DFS是從一個點沿著一個方向一直走下去，而BFS是從一個點開始，先訪問和它相連的，然后訪問和它相連頂點的鄰接點，一圈一圈往外訪問，如圖1-75所示。
?圖1-75
訪問圖的時候需要標記哪些點被訪問過，防止出現重復訪問的情況，來看一下圖的BFS訪問過程，如圖1-76所示。
?圖1-76
結合上面的圖，我們來看一下它的大致模板。
1.8.4 迪杰斯特拉（Dijkstra）算法
迪杰斯特拉（Dijkstra）算法也叫作狄克斯特拉算法，它使用類似廣度優先搜索的方法解決從一個頂點到其他所有頂點的最短路徑算法，它解決的是加權圖（不能有負權）的最短路徑問題，采用的是貪心算法的思想。解題思路是，每次選擇一個沒被標記且距離起始點最近的頂點，把它標記一下，然后更新和它鄰接的頂點，重復上面的步驟，直到標記完所有的頂點為止。比如一個人現在在上海，老家在信陽，假設他回老家不想直接到家，只能通過南京、杭州、武漢、合肥這四個城市中的幾個中轉。如圖1-77所示，下面是中轉所需要的時間，有的坐飛機，有的開車，還有的可能會騎單車，所以邊表示的是時間而不是距離，問應該怎樣走，時間才會更短？
?圖1-77
我們從起始點開始，使用一個數組dis，數組中dis[j]的值表示從頂點j到起始點的時間，剛開始的時候，起始點到自己為0，到其他頂點為無窮大，如圖1-78所示。
?圖1-78
如果想要減少從起始點到j的時間，唯一的方式就是需要尋找一個中轉站k。從起始點到k的時間為dis[k]，從k到j的時間為g[k][j]，然后判斷中轉的總時間dis[k]+g[k][j]是否小于dis[j]，如果中轉時間小于dis[j]，就更新dis[j]。如圖1-77所示，從起始點到南京的時間是3小時，如果通過杭州中轉，時間就會變成2小時。核心代碼是下面這行。
計算過程如圖1-79所示。
?圖1-79
我們來看一下打印結果：0,1,2,4,3,7，也就是說從起始點到其他頂點的最短時間分別是1,2,4,3,7，和圖中分析的完全一樣。時間復雜度：O(n^2),n是頂點的個數。
1. 堆優化
我們看到代碼中外面的循環是遍歷頂點，里面的循環主要是查找最近的頂點，然后更新和它鄰接的頂點。如果這張是稀疏圖，且邊特別少，再一個個查找效率明顯不高，在這種情況下，可以使用最小堆來優化一下，注意使用堆優化的時候，圖要使用鄰接表的表示方式。每次與頂點v鄰接的計算完成后，直接把它加入到堆中，下次循環的時候直接彈出堆頂元素即可，它就是離起始點最近的，時間復雜度可以降為O((n+e)logn)，其中n是頂點的個數，e是邊的數量，因為出堆和入堆都會涉及堆的調整，堆調整的時間復雜度是O(logn)，大家可以嘗試寫一下代碼。
2. 不能處理帶有負權邊的圖
為什么通過上述的操作可以保證得到的dis值最??？因為這里的圖是沒有負權邊的，值只能越加越大，所以這里的最小值不可能再被更新了。我們不斷選擇最小值進行標記，然后更新和它鄰接的點，即貪心的思路，最終保證起始點到每個頂點的值都是最小的。如果有負權邊，再使用Dijkstra算法就行不通了，如圖1-80所示。
?圖1-80
最后的結果是起始點到頂點3的值是8，但實際上如果選擇0->1->2->3這條路徑的值是7，會更小，所以有負權邊并不適合Dijkstra算法。如果圖是有環的，可不可以使用Dijkstra算法呢？實際上只要沒有負權邊，無論有環還是無環，都是可以使用Dijkstra的。
1.8.5 貝爾曼-福特（Bellman-Ford）算法
上一節我們講到Dijkstra算法，它是求單源點的最短路徑，但是不能有負權邊，如果有負權邊該怎么辦呢？可以使用Bellman-Ford算法。Bellman-Ford算法可以解決有負權邊的問題，但不能有負權回路，它也可以檢測是否有負權回路問題。解題思路就是假設有一條邊{begin,end,value}，如果dis[begin]+value<dis[end]，可以更新dis[end]的值為dis[begin]+value，如圖1-81所示。
?圖1-81
所以只需要枚舉所有的邊即可，代碼如下。
如果只枚舉一遍，有可能只會更新和起始點鄰接的點（也就是起始點直接指向的點），與起始點沒有鄰接的點可能沒更新。也就是說如果枚舉一遍，可以更新從起始點通過一條邊到達的點，如果枚舉兩次，可以更新從起始點通過兩條邊到達的點。而在一個含有n個點的圖中，一個點最多只有n-1條邊和起始點相連。所以只需要枚舉n-1次，即可計算起始點到其他所有點的距離。Bellman-Ford算法雖然可以計算帶有負權邊的圖，但不能計算有負權回路的圖，因為在負權回路中，如果一直轉圈，值就會一直變小，如圖1-82所示。
?圖1-82
如果沒有負權回路，最多枚舉n-1次就可計算出起始點到其他所有點的最短路徑，最后枚舉一遍，所有的值不會再更新。如果有負權回路，最后枚舉一遍，有些值還是會更新。所以在計算完之后，還需要再枚舉一遍，判斷有沒有負權回路，代碼如下。
我們只需要看bellMan函數即可，上面的測試數據如圖1-83所示，打印結果是：0,9,2,7。也就是說如果有負權邊，但沒有負權回路，BellMan-Ford算法也是可以計算的。
?圖1-83
BellMan-Ford算法雖然可以計算含有負權邊的圖，但時間復雜度還是比較高的O(ne)，n是頂點的個數，e是邊的個數。其實還可以優化一下，如果在某一次枚舉的時候沒有頂點被更新，再枚舉下去也不會更新了，可以直接終止。
1.8.6 SPFA算法
SPFA（Shortest Path Faster Algorithm）即最短路徑快速算法，實際上它是對Bellman-Ford算法使用隊列的一種優化，也是求單源點最短路徑的，可以有負權邊，但不能有負權回路。我們再來回顧一下Bellman-Ford算法的原理，它是每次遍歷所有的邊，然后判斷是否能松弛。如圖1-84所示，假設第一步先計算<1,2>這條邊，因為頂點1的值還沒有更新，它到起始點的距離是無窮大，我們用它更新頂點2的值明顯是更新不了的，同理如果頂點2的值沒有更新，那么<2,3>這條邊計算頂點3的值也是更新不了的。也就是說使用Bellman-Ford算法會出現大量的無效計算。
?圖1-84
通過Bellman-Ford算法發現一個問題，就是在遍歷<x,y>這條邊的時候，如果頂點x的值沒有改變，那么通過這條邊計算y的值也不會改變。所以有一種解決方式就是如果某個頂點的值改變了，它不在隊列中，就把它添加到隊列中，因為它改變了，和它鄰接的頂點才有可能改變，所以這里只需要遍歷隊列中的頂點即可，如圖1-85所示。
我們先來看一下邊的類，只有兩個屬性，一個是指向另一個的頂點，一個是邊的權值，使用list集合存儲鄰接表，所以就不需要next指針了。
?圖1-85
這里要注意有負權回路的也是不能解決的，所以最后還需要判斷圖是否有負權回路。判斷方式比較簡單，因為如果有負權回路，為了獲取最小值，它會在負權回路上繞圈，在一個有n個頂點的圖中，一個點到起始點最多只能有n-1條邊，如果一個點入隊的次數超過n-1，就說明出現了負權回路，來看一下代碼。
我們仔細看一下上面的代碼和Dijkstra算法的堆優化有什么區別？Dijkstra堆優化使用的是堆，每次從堆中取出一個最小值，然后更新和它鄰接的點，一個點如果從堆中出來之后，它的值就已經被確定了，不可能再改變了，也不可能再入堆了，所以它只能處理沒有負權的圖。而SPFA算法使用的是隊列，每次頂點出隊之后，只要它的值被改變，還可以再次入隊的。
細心的讀者可能發現，使用隊列每次遍歷一個點相鄰的頂點，這不是和圖的BFS遍歷一樣嗎。提到BFS，大家可能也會想到DFS，也就是一個點被更新之后，和它鄰接的點可能會被更新，可以參考DFS的寫法，當一個點被更新之后，可以沿著這個點朝一個方向一直走下去，來更新這條路徑上的所有點，這里就不再過多介紹，有興趣的讀者可以試著寫一下。
1.8.7 弗洛伊德（Floyd）算法
前面介紹的幾個都是求單源點路徑的，其中Dijkstra算法是不能解決有負權值的圖。而Bellman-Ford算法和SPFA算法是可以解決有負權值，但不能有負權回路的圖。這節要介紹的Floyd算法是解決多源點路徑的，它可以解決圖中任何兩點之間的距離，圖中也是可以有負權值的，但不能有負權回路。大家可能會說前面剛講過求單源點路徑的算法，如果把每個點都當作起始點計算一次，不就可以計算出任意兩點之間的距離了嗎，這種方式也是可以的，但我們這里要講的是另一種解決方式——Floyd算法。
Floyd算法相比前面講的幾個求單源點的算法更簡單，也更容易理解。我們來思考這樣一個問題，如果知道A到B的距離是x，這個x可能是一個確定的值，也可能是無窮大，怎樣才能使x的值變小呢？唯一的解決方式就是找一個中轉站C，判斷A到C的距離加上C到B的距離是否小于A到B的距離，如果小于，就更新A到B的值，如果不小于，A到B的值就不變，如圖1-86所示。
我們只需要把所有的點作為中轉站枚舉一遍即可，很明顯這是一道動態規劃的問題，關于動態規劃在第11章會進行介紹。我們定義dp[k][i][j]表示經過前k個頂點從i到j的最短距離。
?圖1-86
?如果不經過第k個頂點中轉，那么dp[k][i][j]=dp[k-1][i][j]。
?如果經過第k個頂點中轉，那么dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k][j]。
只需要取它們的最小值即可，也就是：
這里要注意初始條件，以及最后距離的合并，來看一下代碼。
這里只需要看下面幾行代碼，它才是這道題的核心代碼。
我們看到dp是一個三維數組，計算的時候dp[k][?][?]只和dp[k-1][?][?]有關，所以可以把它壓縮成二維數組，這樣代碼就會更加簡潔。
時間復雜度是：O(n^3)，空間復雜度是O(1)，只需要一個變量n即可，因為我們是直接在矩陣數組中計算的，如果題中要求不能在矩陣數組中修改，還需要申請一個二維數組，空間復雜度就是O(n^2)。注意這三層for循環的嵌套順序，遍歷k的時候不能放到最里面一層，因為這是通過三維數組狀態壓縮出來的。Floyd算法使用的是動態規劃思想，更適合稠密圖，也可以處理負權邊，但不能處理有負權回路的圖。它更容易理解，三層循環，代碼比較簡潔，可以計算任意兩點之間的最短距離。缺點是時間復雜度比較高，不適合計算頂點比較多的圖。
1.8.8 普里姆（Prim）算法
Prim算法和下一小節要講的Kruskal算法都是實現最小生成樹的一種算法，Prim是通過點來實現的，而Kruskal是通過邊來實現的，這一小節先講Prim算法。對于一個有n個頂點的無向圖，如果只需要使用n-1條邊，即可把圖中的所有點連接起來，那么這n個頂點和這n-1條邊構成的圖就是生成樹，如圖1-87所示。
?圖1-87
一張圖的所有生成樹中權值總和最少的就是最小生成樹。Prim算法就是求最小生成樹的，它使用的是貪心算法。解題思路是需要把圖中的點分成兩部分，一部分是已經選擇的，我們用集合S記錄，一部分是還沒選擇的，我們用集合T記錄。剛開始的時候集合S為空，集合T中包含圖中的所有頂點，如圖1-88所示，步驟如下。
（1）第一步從集合T中任選一個頂點v，把頂點v放到集合S中。
（2）更新集合T中和v相鄰的頂點值。
（3）繼續從集合T中選擇離集合S最近的頂點v，把它加入到集合S中，更新集合T中和v相鄰的頂點值。
（4）一直重復下去，直到集合T為空。
?圖1-88
1.8.9 克魯斯卡爾（Kruskal）算法
Kruskal算法也是求最小生成樹的，它是通過選擇邊來實現的，它的實現原理是，首先需要對圖中的邊根據大小排序，然后每次選擇一個最小的邊，但要保證選的時候不能構成環路，一直選擇下去，直到不能選擇為止。判斷能不能構成環路可以使用并查集，就是判斷邊的兩個點是否在一個連通分量，如果在一個連通分量，這條邊就不能選，否則可以選，如圖1-89所示。
?圖1-89
實現步驟如圖1-90所示。
來看一下代碼，代碼會涉及并查集的知識，如果不熟悉也沒有關系，只需要知道find這個方法可以判斷是否是同一連通分量即可，關于并查集的知識，我們在第12章并查集中會進行介紹。
?圖1-90
看一下運行結果：
和上面的圖中分析得差不多，因為權值相同的時候先選擇哪個都是一樣的。
1.8.10 博魯夫卡（Boruvka）算法
Boruvka算法是最小生成樹最古老的一種算法，最早可以追溯到1926年，當時用于構建高效電力網絡。它的實現原理就是剛開始的時候把每一個頂點看作是一個連通分量，接著計算與每個連通分量距離最短的連通分量，然后把它們連接起來。如果還有沒連通的連通分量，繼續計算離它們最近的連通分量，繼續連接，直到都連通為止，如圖1-91所示。
?圖1-91
如圖1-92所示，離頂點1最近的頂點除了頂點0還有頂點2，連通的時候不能重復連接，比如連接了（0,1），就不能再連接（1,0）。連接之后只剩下兩個連通分量，我們找到它們之間最短的邊連接起來即可。
?圖1-92
來看一下打印結果：
打印順序和圖中分析的完全一樣。
總結：無論是求單源點路徑還是多源點路徑，圖中都不能有負權回路，因為負權回路每繞一圈，距離就會變小，如果有負權回路，永遠沒有最小值，我們來對上面幾種算法做一個簡單的總結。
Dijkstra：求單源點路徑，不能有負權值。
Bellman-Ford：求單源點路徑，可以有負權值，但不能有負權回路。
SPFA：是使用隊列對Bellman-Ford算法的一種優化，可以有負權值，但不能有負權回路。
Floyd：求多源點路徑，可以有負權值，但不能有負權回路。
Prim：通過查找最近的點，計算最小生成樹。
Kruskal：通過查找最小的邊，計算最小生成樹。
Boruvka：通過不停合并連通分量，計算最小生成樹。
1.8.11 拓撲排序
拓撲排序就是在一個有向無環圖中，對圖的頂點進行排序，排序的條件是對于任意一條有向邊<v1,v2>，排序的結果中頂點v1一定在頂點v2的前面。如圖1-93所示，對于<起床，刷牙>這條邊排序的結果中，起床一定在刷牙之前。
?圖1-93
拓撲排序的思路就是首先從圖中選擇入度為0的頂點，把它加入到隊列中，然后逐步輸出隊列中的元素v，其中v指向的頂點入度要減1，如果減1之后入度為0，也要加入到隊列中。重復這個步驟直到沒有入度為0的頂點為止。其實也很好理解，入度為0，說明在它前面沒有頂點了，我們直接輸出就行，如果入度不為0，說明在它前面還有頂點，需要先輸出它前面的頂點才能輸出它，如圖1-94所示。
?圖1-94
