數據結構與演算法 - 圖論

這篇文章是我當時在上數據結構課的時候做的筆記的，現在重新整理了一下，也算是一篇簡單的科普文。

基本概念：

圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。

圖論是一種表示 "多對多" 的關係

圖是由頂點和邊組成的：(可以無邊，但至少包含一個頂點)

• 一組頂點：通常用 V(vertex) 表示頂點集合
• 一組邊：通常用 E(edge) 表示邊的集合

圖可以分為有向圖和無向圖，在圖中：

• (v, w) 表示無向邊，即 v 和 w 是互通的
• <v, w> 表示有向邊，該邊始於 v，終於 w

圖可以分為有權圖和無權圖：

• 有權圖：每條邊具有一定的權重(weight)，通常是一個數字
• 無權圖：每條邊均沒有權重，也可以理解為權為 1

圖又可以分為連通圖和非連通圖：

• 連通圖：所有的點都有路徑相連
• 非連通圖：存在某兩個點沒有路徑相連

圖中的頂點有度的概念：

• 度(Degree)：所有與它連接點的個數之和
• 入度(Indegree)：存在於有向圖中，所有接入該點的邊數之和
• 出度(Outdegree)：存在於有向圖中，所有接出該點的邊數之和

圖的表示：

圖在程序中的表示一般有兩種方式：

1. 鄰接矩陣：

• 在 n 個頂點的圖需要有一個 n × n 大小的矩陣
• 在一個無權圖中，矩陣坐標中每個位置值為 1 代表兩個點是相連的，0 表示兩點是不相連的
• 在一個有權圖中，矩陣坐標中每個位置值代表該兩點之間的權重，0 表示該兩點不相連
• 在無向圖中，鄰接矩陣關於對角線相等

2. 鄰接鏈表：

• 對於每個點，存儲著一個鏈表，用來指向所有與該點直接相連的點
• 對於有權圖來說，鏈表中元素值對應著權重

例如在無向無權圖中：

在無向有權圖中：

可以看出在無向圖中，鄰接矩陣關於對角線對稱，而鄰接鏈表總有兩條對稱的邊

而在有向無權圖中：

鄰接矩陣和鏈表對比：

1. 鄰接矩陣由於沒有相連的邊也佔有空間，因此存在浪費空間的問題，而鄰接鏈表則比較合理地利用空間

2. 鄰接鏈表比較耗時，犧牲很大的時間來查找，因此比較耗時，而鄰接矩陣法相比鄰接鏈表法來說，時間複雜度低。

圖的遍歷：

圖的遍歷就是要找出圖中所有的點，一般有以下兩種方法：

1. 深度優先遍歷：(Depth First Search, DFS)

基本思路：深度優先遍歷圖的方法是，從圖中某頂點 v 出發

1. 訪問頂點 v
2. 從 v 的未被訪問的鄰接點中選取一個頂點 w，從 w 出發進行深度優先遍歷
3. 重複上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到

偽碼實現：

//偽碼實現，類似於樹的先序遍歷npublic void DFS(Vertex v){n visited[v] = true;n for(v 的每個鄰接點 W){ntif(!visited[W]){nt DFS(W);nt}n }n}n

2. 廣度優先搜索：(Breadth First Search, BFS)

廣度優先搜索，可以被形象地描述為 "淺嘗輒止"，它也需要一個隊列以保持遍歷過的頂點順序，以便按出隊的順序再去訪問這些頂點的鄰接頂點。

實現思路：

1. 頂點 v 入隊列
2. 當隊列非空時則繼續執行，否則演算法結束
3. 出隊列取得隊頭頂點 v；訪問頂點 v 並標記頂點 v 已被訪問

4. 查找頂點 v 的第一個鄰接頂點 col
5. 若 v 的鄰接頂點 col 未被訪問過的，則 col 繼續
6. 查找頂點 v 的另一個新的鄰接頂點 col，轉到步驟 5 入隊列，直到頂點 v 的所有未被訪問過的鄰接點處理完。轉到步驟 2

要理解深度優先和廣度優先搜索，首先要理解搜索步，一個完整的搜索步包括兩個處理

1. 獲得當前位置上，有幾條路可供選擇
2. 根據選擇策略，選擇其中一條路，並走到下個位置

相當於在漆黑的夜裡，你只能看清你站的位置和你前面的路，但你不知道每條路能夠通向哪裡。搜索的任務就是，給出初始位置和目標位置，要求找到一條到達目標的路徑。

• 深度優先就是，從初始點出發，不斷向前走，如果碰到死路了，就往回走一步，嘗試另一條路，直到發現了目標位置。這種不撞南牆不回頭的方法，即使成功也不一定找到一條好路，但好處是需要記住的位置比較少。

• 廣度優先就是，從初始點出發，把所有可能的路徑都走一遍，如果裡面沒有目標位置，則嘗試把所有兩步能夠到的位置都走一遍，看有沒有目標位置；如果還不行，則嘗試所有三步可以到的位置。這種方法，一定可以找到一條最短路徑，但需要記憶的內容實在很多，要量力而行。

最短路徑演算法 (Shortest Path Algorithm)

1. 無權圖：

問題：在圖中找到某一個頂點到其它所有點的距離

對於初始點 v 來說，某個點的 d 代表該點到初始點的距離。

基本步驟：

1. 將所有點的距離 d 設為無窮大
2. 挑選初始點 s，將 ds 設為 0，將 shortest 設為 0
3. 找到所有距離為 d 為 shortest 的點，查找他們的鄰接鏈表的下一個頂點 w，如果 dw 的值為無窮大，則將 dw 設為 shortest + 1
4. 增加 shortest 的值，重複步驟 3，直到沒有頂點的距離值為無窮大

2. 有權圖：

在有權圖中，常見的最短路徑演算法有 Dijkstra 演算法 Floyd 演算法

迪傑斯特拉 Dijkstra 演算法：Dijkstra 演算法適用於權值為正的的圖

Dijkstra 演算法屬於單源演算法，即只能求出某點到其它點最短距離，並不能得出任意兩點之間的最短距離。

演算法步驟：

1. 將所有邊初始化為無窮大
2. 選擇一個開始的頂點，添加到優先隊列中
3. 對於該點的所有鄰接頂點進行判斷，如果到該點的距離小於原先的值，則將該值進行更新
4. 將該點所有鄰接頂點添加到優先隊列中
5. 從優先隊列中挑選出一個路徑值最小的頂點，將其彈出，作為新的頂點，重複步驟 3，4，5
6. 直到所有點都被處理過一次

例如：

首先選取 v0 作為起始點，添加到優先隊列中，將v0彈出，然後對 v0 鄰接點進行判斷，由於一開始所有邊都為無窮大，那麼 <v0, v1> 和 <v0, v3> 都更新，值為 2 和 1，按路徑大小升序將v3、v1添加到優先隊列。

之後將 v3 彈出，對所有 v3 鄰接點進行值的更新，並將所有鄰接點按路徑大小升序添加到優先隊列中，若遇到值相同，則無所謂其先後順序

重複這樣的過程，直到所有的點都被處理過，則演算法終止，這樣最後可以得出從 v0 到其它 v1~v6 節點的距離。

Dijkstra 演算法適合於權值為正的情況下，若權值為負則不能使用，因為出現死循環。這時候我們需要計算每個頂點被處理的次數，當某個頂點已經處理過的話，就跳出該循環。

佛洛伊德 Floyd 演算法：可以求出任意兩點的最短距離

Floyd 演算法是一個經典的動態規劃演算法。用通俗的語言來描述的話，首先我們的目標是尋找從點 i 到點 j 的最短路徑。

從任意節點 i 到任意節點 j 的最短路徑不外乎 2 種可能：

1. 是直接從 i 到 j
2. 是從 i 經過若干個節點 k 到 j

所以，我們假設 Dis(i,j) 為節點 u 到節點 v 的最短路徑的距離，對於每一個節點 k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，我們便設置 Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當我們遍歷完所有節點 k，Dis(i,j) 中記錄的便是 i 到 j 的最短路徑的距離。

時間複雜度： O(n^3)

for(int k=0; k<n; k++) { n for(i=0; i<n; i++) {n for(j=0; j<n; j++)n if(A[i][j]>(A[i][k]+A[k][j])) {n A[i][j]=A[i][k]+A[k][j];n path[i][j]=k;n } n }n} n

最小生成樹 (Minimum Spanning Trees MST)

例如：要在 n 個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。

特點：

1. 該樹是連通的
2. 權值之和最小
3. 邊數比頂點個數少 1

存在個數：最小生成樹在一些情況下可能會有多個

1. 當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹

2. 如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個

比如：

生成最小生成樹的演算法一般有兩種，分別是 Prim 演算法和 Kruskal 演算法

1. 普里姆演算法 (Prim 演算法):

演算法步驟：

1. 輸入：一個加權連通圖，其中頂點集合為 V，邊集合為 E
2. 初始化：Vnew = {x}，其中 x 為集合 V 中的任一節點(起始點)，Enew = {} 為空
3. 在集合 E 中選取權值最小的邊 <u, v>，其中 u 為集合 Vnew 中的元素，而 v 不在 Vnew 集合當中，並且 v∈V (如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）
4. 將 v 加入集合 Vnew 中，將 <u, v> 邊加入集合 Enew 中
5. 重複步驟 3、4 直到 Vnew = V

時間複雜度：O(V^2)

2. Kruskal 演算法：需要一個集合用來升序存儲所有邊

演算法步驟：

1. 先構造一個只含有 n 個頂點，而邊集為空的子圖
2. 從邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖。(也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹) 反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之
3. 重複步驟 2，直到所有點連通

時間複雜度：O( ElogV )

例如：

在對所有邊進行排序之後，我們得到一個邊集合，從邊集合中取出最小權的邊 AD

剩下的邊中尋找。我們找到了 CE。這裡邊的權重也是 5，依次類推我們找到了 6,7,7

儘管現在長度為 8 的邊是最小的未選擇的邊。但是他們已經連通了

最後就剩下 EG 和 FG 了。當然我們選擇了 EG

結尾：

當然，如果你看到這仍意猶未盡，想通過代碼將上面的演算法進行表示，我推薦下面的教程：

數據結構與演算法系列 目錄 - 如果天空不死 - 博客園

裡面有對前面講的演算法進行詳細實現。

之前有用 D3js 寫過關於圖論演算法的動畫，感興趣地可以玩玩：Graph Animation

參考鏈接：

最小生成樹-Prim演算法和Kruskal演算法 - as_ - 博客園

推薦閱讀：