圖-無向圖
圖是由一組頂點和一組能夠將兩個頂點相連的邊組成。
頂點叫什麼名字並不重要，但我們需要一個方法來指代這些頂點。一般使用 0 至 V-1 來表示一張含有 V 個頂點的圖中的各個頂點。這樣約定是為了方便使用數組的索引來編寫能夠高效訪問各個頂點資訊的程式碼。用一張符號表來為頂點的名字和 0 到 V-1 的整數值建立一一對應的關係並不困難，因此直接使用數組索引作為結點的名稱更方便且不失一般性，也不會損失什麼效率。
我們用 v-w 的記法來表示連接 v 和 w 的邊， w-v 是這條邊的另一種表示方法。
在繪製一幅圖時，用圓圈表示頂點，用連接兩個頂點的線段表示邊，這樣就能直觀地看出圖地結構。但這種直覺有時可能會誤導我們，因為圖地定義和繪製地影像是無關的，一組數據可以繪製不同形態的影像。
特殊的圖
自環：即一條連接一個頂點和其自身的邊；
多重圖：連接同一對頂點的兩條邊成為平行邊，含有平行邊的圖稱為多重圖。
沒有平行邊的圖稱為簡單圖。
1.相關術語
當兩個頂點通過一條邊相連時，稱這兩個頂點是相鄰得，並稱這條邊依附於這兩個頂點。某個頂點的度數即為依附於它的邊的總數。子圖是由一幅圖的所有邊的一個子集（以及它們所依附的所有頂點）組成的圖。許多計算問題都需要識別各種類型的子圖，特別是由能夠順序連接一系列頂點的邊所組成的子圖。
在圖中，路徑是由邊順序連接的一系列頂點。簡單路徑是一條沒有重複頂點的路徑。環是一條至少含有一條邊且起點和終點相同的路徑。簡單環是一條（除了起點和終點必須相同之外）不含有重複頂點和邊的環。路徑或環的長度為其中所包含的邊數。
當兩個頂點之間存在一條連接雙方的路徑時，我們稱一個頂點和另一個頂點是連通的。
如果從任意一個頂點都存在一條路徑到達另一個任意頂點，我們稱這副圖是連通圖。一幅非連通的圖由若干連通的部分組成，它們都是其極大連通子圖。
一般來說，要處理一張圖需要一個個地處理它的連通分量（子圖）。
樹是一幅無環連通圖。互不相連的樹組成的集合稱為森林。連通圖的生成樹是它的一幅子圖，它含有圖中的所有頂點且是一棵樹。圖的生成森林是它的所有連通子圖的生成樹的集合。
樹的定義非常通用，稍作改動就可以變成用來描述程式行為（函數調用層次）模型和數據結構。當且僅當一幅含有 V 個結點的圖 G 滿足下列 5 個條件之一時，它就是一棵樹：
G 有 V – 1 條邊且不含有環；
G 有 V – 1 條邊且是連通的；
G 是連通的，但刪除任意一條都會使它不再連通；
G 是無環圖，但添加任意一條邊都會產生一條環；
G 中的任意一對頂點之間僅存在一條簡單路徑；
圖的密度是指已經連接的頂點對占所有可能被連接的頂點對的比例。在稀疏圖中，被連接的頂點對很少；而在稠密圖中，只有少部分頂點對之間沒有邊連接。一般來說，如果一幅圖中不同的邊的數量在頂點總數 v 的一個小的常數倍以內，那麼我們認為這幅圖是稀疏的，否則就是稠密的。
二分圖是一種能夠將所有結點分為兩部分的圖，其中圖的每條邊所連接的兩個頂點都分別屬於不同的集合。
2.表示無向圖的數據結構
圖的幾種表示方法
接下來要面對的圖處理問題就是用哪種數據結構來表示圖並實現這份API，包含下面兩個要求：
1.必須為可能在應用中碰到的各種類型圖預留出足夠的空間；
2.Graph 的實例方法的實現一定要快。
下面有三種選擇：
1.鄰接矩陣：我們可以使用一個 V 乘 V 的布爾矩陣。當頂點 v 和 w 之間有連接的邊時，定義 v 行 w 列的元素值為 true，否則為 false。這種表示方法不符合第一個條件–含有上百萬個頂點的圖所需的空間是不能滿足的。
2.邊的數組：我們可以使用一個 Edge 類，它含有兩個 int 實例變數。這種表示方法很簡單但不滿足第二個條件–要實現 Adj 需要檢查圖中的所有邊。
3.鄰接表數組：使用一個以頂點為索引的列表數組，其中每個元素都是和該頂點相連的頂點列表。
非稠密圖的標準表示成為鄰接表的數據結構，它將每個頂點的所有相鄰頂點都保存在該頂點對應的元素所指向的一張鏈表中。我們使用這個數組就是為了快速訪問給定頂點的鄰接頂點列表。這裡使用 Bag 來實現這個鏈表，這樣我們就可以在常數時間內添加新的邊或遍歷任意頂點的所有相鄰頂點。
要添加一條連接 v 與 w 的邊，我們將 w 添加到 v 的鄰接表中並把 v 添加到 w 的鄰接表中。因此在這個數據結構中每條邊都會出現兩次。這種 Graph 的實現的性能特點：
1.使用的空間和 V+E 成正比；
2.添加一條邊所需的時間為常數；
3.遍歷頂點 v 的所有相鄰頂點所需的時間和 v 的度數成正比。
對於這些操作，這樣的特性已經是最優的了，而且支援平行邊和自環。注意，邊的插入順序決定了 Graph 的鄰接表中頂點的出現順序。多個不同的鄰接表可能表示著同一幅圖。因為演算法在使用 Adj() 處理所有相鄰的頂點時不會考慮它們在鄰接表中的出現順序，這種差異不會影響演算法的正確性，但在調試或是跟蹤鄰接表的軌跡時需要注意這一點。
public class Graph { private int v; private int e; private List<int>[] adj; //鄰接表(用List 代替 bag) /// <summary> /// 創建一個含有V個頂點但不含有邊的圖 /// </summary> /// <param name="V"></param> public Graph(int V) { v = V; e = 0; adj = new List<int>[V]; for (var i = 0; i < V; i++) adj[i] = new List<int>(); } public Graph(string[] strs) { foreach (var str in strs) { var data = str.Split(' '); int v = Convert.ToInt32(data[0]); int w = Convert.ToInt32(data[1]); AddEdge(v,w); } } /// <summary> /// 頂點數 /// </summary> /// <returns></returns> public int V() { return v; } /// <summary> /// 邊數 /// </summary> /// <returns></returns> public int E() { return e; } /// <summary> /// 向圖中添加一條邊 v-w /// </summary> /// <param name="v"></param> /// <param name="w"></param> public void AddEdge(int v, int w) { adj[v].Add(w); adj[w].Add(v); e++; } /// <summary> /// 和v相鄰的所有頂點 /// </summary> /// <param name="v"></param> /// <returns></returns> public IEnumerable<int> Adj(int v) { return adj[v]; } /// <summary> /// 計算 V 的度數 /// </summary> /// <param name="G"></param> /// <param name="V"></param> /// <returns></returns> public static int Degree(Graph G, int V) { int degree = 0; foreach (int w in G.Adj(V)) degree++; return degree; } /// <summary> /// 計算所有頂點的最大度數 /// </summary> /// <param name="G"></param> /// <returns></returns> public static int MaxDegree(Graph G) { int max = 0; for (int v = 0; v < G.V(); v++) { var d = Degree(G, v); if (d > max) max = d; } return max; } /// <summary> /// 計算所有頂點的平均度數 /// </summary> /// <param name="G"></param> /// <returns></returns> public static double AvgDegree(Graph G) { return 2.0 * G.E() / G.V(); } /// <summary> /// 計算自環的個數 /// </summary> /// <param name="G"></param> /// <returns></returns> public static int NumberOfSelfLoops(Graph G) { int count = 0; for (int v = 0; v < G.V(); v++) { foreach (int w in G.Adj(v)) { if (v == w) count++; } } return count / 2; //每條邊都被計算了兩次 } public override string ToString() { string s = V() + " vertices, " + E() + " edges\n"; for (int v = 0; v < V(); v++) { s += v + ":"; foreach (int w in Adj(v)) { s += w + " "; } s += "\n"; } return s; } }
在實際應用中還有一些操作可能有用，例如：
添加一個頂點；
刪除一個頂點。
實現這些操作的一種方法是，使用符號表 ST 來代替由頂點索引構成的數組，這樣修改之後就不需要約定頂點名必須是整數了。可能還需要：
刪除一條邊；
檢查圖是否含有 v-w。
要實現這些方法，可能需要使用 SET 代替 Bag 來實現鄰接表。我們稱這種方法為鄰接集。現在還不需要，因為：
不需要添加，刪除頂點和邊或是檢查一條邊是否存在；
上述操作使用頻率很低或者相關鏈表很短，可以直接使用窮舉法遍歷；
某些情況下會使性能損失 logV。
3.圖的處理演算法的設計模式
因為我們會討論大量關於圖處理的演算法，所以設計的首要目標是將圖的表示和實現分離開來。為此，我們會為每個任務創建一個相應的類，用例可以創建相應的對象來完成任務。類的構造函數一般會在預處理中構造各種數據結構，以有效地響應用例的請求。典型的用常式序會構造一幅圖，將圖作為參數傳遞給某個演算法類的構造函數，然後調用各種方法來獲取圖的各種性質。
我們用起點 s 區分作為參數傳遞給構造函數的頂點與圖中的其他頂點。在這份 API 中，構造函數的任務就是找到圖中與起點連通的其他頂點。用例可以調用 marked 方法和 count 方法來了解圖的性質。方法名 marked 指的是這種基本方法使用的一種實現方式：在圖中從起點開始沿著路徑到達其他頂點並標記每個路過的頂點。
在 union-find演算法 已經見過 Search API 的實現，它的構造函數會創建一個 UF 對象，對圖中的每條邊進行一次 union 操作並調用 connected(s,v) 來實現 marked 方法。實現 count 方法需要一個加權的 UF 實現並擴展它的API，以便使用 count 方法返回 sz[find(v)]。
下面的一種搜索演算法是基於深度優先搜索（DFS）的，它會沿著圖的邊尋找喝起點連通的所有頂點。
4.深度優先搜索
要搜索一幅圖，只需要一個遞歸方法來遍歷所有頂點。在訪問其中一個頂點時：
1.將它標記為已訪問；
2.遞歸地訪問它所有沒有被標記過地鄰居頂點。
這種方法稱為深度優先搜索（DFS）。
namespace Graphs { /// <summary> /// 使用一個 bool 數組來記錄和起點連通地所有頂點。遞歸方法會標記給定地頂點並調用自己來訪問該頂點地相鄰頂點列表中 /// 所有沒有被標記過地頂點。 如果圖是連通的，每個鄰接鏈表中的元素都會被標記。 /// </summary> public class DepthFirstSearch { private bool[] marked; private int count; public DepthFirstSearch(Graph G,int s) { marked = new bool[G.V()]; Dfs(G,s); } private void Dfs(Graph g, int V) { marked[V] = true; count++; foreach (var w in g.Adj(V)) { if (!marked[w]) Dfs(g,w); } } public bool Marked(int w) { return marked[w]; } } }
深度優先搜索標記與起點連通的所有頂點所需的時間和頂點的度數之和成正比。
這種簡單的遞歸模式只是一個開始 — 深度優先搜索能夠有效處理許多和圖有關的任務。
1.連通性。給定一幅圖，兩個給定的頂點是否連通？（兩個給定的頂點之間是否存在一條路徑?路徑檢測） 圖中有多少個連通子圖？
2.單點路徑。給定一幅圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條路徑？如果有，找出這條路徑。
5.尋找路徑
單點路徑的API：
構造函數接受一個起點 s 作為參數，計算 s 到與 s 連通的每個頂點之間的路徑。在為起點 s 創建 Paths 對象之後，用例可以調用 PathTo 方法來遍歷從 s 到任意和 s 連通的頂點的路徑上的所有頂點。
實現
下面的演算法基於深度優先搜索，它添加了一個 edgeTo[ ] 整型數組，這個數組可以找到從每個與 s 連通的頂點回到 s 的路徑。它會記住每個頂點到起點的路徑，而不是記錄當前頂點到起點的路徑。為了做到這一點，在由邊 v-w 第一次任意訪問 w 時，將 edgeTo[w] = v 來記住這條路徑。換句話說， v-w 是從s 到 w 的路徑上最後一條已知的邊。這樣，搜索的結果是一棵以起點為根結點的樹，edgeTo[ ] 是一棵由父鏈接表示的樹。 PathTo 方法用變數 x 遍歷整棵樹，將遇到的所有頂點壓入棧中。
public class DepthFirstPaths { private bool[] marked; private int[] edgeTo; //從起點到一個頂點的已知路徑上的最後一個頂點 private int s;//起點 public DepthFirstPaths(Graph G, int s) { marked = new bool[G.V()]; edgeTo = new int[G.V()]; this.s = s; Dfs(G,s); } private void Dfs(Graph G, int v) { marked[v] = true; foreach (int w in G.Adj(v)) { if (!marked[w]) { edgeTo[w] = v; Dfs(G,w); } } } public bool HasPathTo(int v) { return marked[v]; } public IEnumerable<int> PathTo(int v) { if (!HasPathTo(v)) return null; Stack<int> path = new Stack<int>(); for (int x = v; x != s; x = edgeTo[x]) path.Push(x); path.Push(s); return path; } }
使用深度優先搜索得到從給定起點到任意標記頂點的路徑所需的時間與路徑長度成正比。
6.廣度優先搜索
深度優先搜索得到的路徑不僅取決於圖的結構，還取決於圖的表示和遞歸調用的性質。
單點最短路徑：給定一幅圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條路徑？如果有，找出其中最短的那條（所含邊最少）。
解決這個問題的經典方法叫做廣度優先搜索（BFS）。深度優先搜索在這個問題上沒有什麼作用，因為它遍歷整個圖的順序和找出最短路徑的目標沒有任何關係。相比之下，廣度又出現搜索正式為了這個目標才出現的。
要找到從 s 到 v 的最短路徑，從 s 開始，在所有由一條邊就可以到達的頂點中尋找 v ，如果找不到就繼續在與 s 距離兩條邊的所有頂點中查找 v ,如此一直進行。
在程式中，在搜索一幅圖時遇到有很多邊需要遍歷的情況時，我們會選擇其中一條並將其他邊留到以後再繼續搜索。在深度優先搜索中，我們用了一個可以下壓棧。使用LIFO （後進先出）的規則來描述下壓棧和走迷宮時先探索相鄰的
通道類似。從有待搜索的通道中選擇最晚遇到過的那條。在廣度優先搜索中，我們希望按照與起點距離的順序來遍歷所有頂點，使用（FIFO，先進先出）隊列來代替棧即可。我們將從有待搜索的通道中選擇最早遇到的那條。
實現
下面的演算法使用了一個隊列來保存所有已經被標記過但其鄰接表還未被檢查過的頂點。先將頂點加入隊列，然後重複下面步驟知道隊列為空：
1.取隊列的下一個頂點 v 並標記它；
2.將與 v 相鄰的所有未被標記過的頂點加入隊列。
下面的 Bfs 方法不是遞歸。它顯示地使用了一個隊列。和深度優先搜索一樣，它的結果也是一個數組 edgeTo[ ] ，也是一棵用父鏈接表示的根結點為 s 的樹。它表示了 s 到每個與 s 連通的頂點的最短路徑。
namespace Graphs { /// <summary> /// 廣度優先搜索 /// </summary> public class BreadthFirstPaths { private bool[] marked;//到達該頂點的最短路徑已知嗎？ private int[] edgeTo;//到達該頂點的已知路徑上的最後一個頂點 private int s;//起點 public BreadthFirstPaths(Graph G,int s) { marked = new bool[G.V()]; edgeTo = new int[G.V()]; this.s = s; Bfs(G,s); } private void Bfs(Graph G, int s) { Queue<int> queue = new Queue<int>(); marked[s] = true;//標記起點 queue.Enqueue(s);//將它加入隊列 while (queue.Count > 0) { int v = queue.Dequeue();//從隊列中刪去下一個頂點 foreach (var w in G.Adj(v)) { if (!marked[w])//對於每個未標記的相鄰頂點 { edgeTo[w] = v;//保存最短路徑的最後一條邊 marked[w] = true;//標記它，因為最短路徑已知 queue.Enqueue(w);//並將它添加到隊列中 } } } } public bool HasPathTo(int v) { return marked[v]; } } }
軌跡：
對於從 s 可達的任意頂點 v ,廣度優先搜索都能找到一條從 s 到 v 的最短路徑，沒有其他從 s 到 v 的路徑所含的邊比這條路徑更少。
廣度優先搜索所需的時間在最壞情況下和 V+E 成正比。
我們也可以使用廣度優先搜索來實現已經用深度優先搜索實現的 Search API，因為它檢查所有與起點連通的頂點和邊的方法只取決於查找能力。
廣度優先搜索和深度優先搜索在搜索中都會先將起點存入數據結構，然後重複以下步驟直到數據結構清空：
1.取其中的下一個頂點並標記它；
2.將 v 的所有相鄰而又未被標記的頂點加入數據結構。
這兩個演算法的不同之處在於從數據結構中獲取下一個頂點的規則（對於廣度優先搜索來說是最早加入的頂點，對於深度優先搜索來說是最晚加入的頂點）。這種差異得到了處理圖的兩種完全不同的視角，儘管無論使用哪種規則，所有與起點連通的頂點和邊都會被檢查到。
深度優先搜索不斷深入圖中並在棧中保存了所有分叉的頂點；廣度優先搜索則像扇面一般掃描圖，用一個隊列保存訪問過的最前端的頂點。深度優先搜索探索一幅圖的方式是尋找離起點更遠的頂點，只在碰到死胡同時才訪問進出的頂點；廣度優先搜索則首先覆蓋起點附近的頂點，只在臨近的所有頂點都被訪問了之後才向前進。根據應用的不同，所需要的性質也不同。
7.連通分量
深度優先搜索的下一個直接應用就是找出一幅圖的所有連通分量。在 union-find 中 「與……連通」 是一種等價關係，它能夠將所有頂點切分成等價類（連通分量）。
實現
CC 的實現使用了 marked 數組來尋找一個頂點作為每個連通分量中深度優先搜索的起點。遞歸的深度優先搜索第一次調用的參數是頂點 0 — 它會標記所有與 0 連通的頂點。然後構造函數中的 for 循環會查找每個沒有被標記的頂點並遞歸調用 Dfs 來標記和它相鄰的所有頂點。另外，還使用了一個以頂點作為索引的數組 id[ ] ，值為連通分量的標識符，將同一連通分量中的頂點和連通分量的標識符關聯起來。這個數組使得 Connected 方法的實現變得非常簡單。
namespace Graphs { public class CC { private bool[] marked; private int[] id; private int count; public CC(Graph G) { marked = new bool[G.V()]; id = new int[G.V()]; for (var s = 0; s < G.V(); s++) { if (!marked[s]) { Dfs(G,s); count++; } } } private void Dfs(Graph G, int v) { marked[v] = true; id[v] = count; foreach (var w in G.Adj(v)) { if (!marked[w]) Dfs(G,w); } } public bool Connected(int v, int w) { return id[v] == id[w]; } public int Id(int v) { return id[v]; } public int Count() { return count; } } }
深度優先搜索的預處理使用的時間和空間與 V + E 成正比且可以在常數時間內處理關於圖的連通性查詢。由程式碼可知每個鄰接表的元素都只會被檢查一次，共有 2E 個元素（每條邊兩個）。
union-find 演算法
CC 中基於深度優先搜索來解決圖連通性問題的方法與 union-find演算法 中的演算法相比，理論上，深度優先搜索更快，因為它能保證所需的時間是常數而 union-find演算法不行；但在實際應用中，這點差異微不足道。union-find演算法其實更快，因為它不需要完整地構造表示一幅圖。更重要的是，union-find演算法是一種動態演算法（我們在任何時候都能用接近常數的時間檢查兩個頂點是否連通，甚至是添加一條邊的時候），但深度優先搜索則必須對圖進行預處理。
因此，我們在只需要判斷連通性或是需要完成大量連通性查詢和插入操作混合等類似的任務時，更傾向使用union-find演算法，而深度優先搜索則適合實現圖的抽象數據類型，因為它能更有效地利用已有的數據結構。
使用深度優先搜索還可以解決 檢測環 和雙色問題：
檢測環，給定的圖是無環圖嗎？
namespace Graphs { public class Cycle { private bool[] marked; private bool hasCycle; public Cycle(Graph G) { marked = new bool[G.V()]; for (var s = 0; s < G.V(); s++) { if (!marked[s]) Dfs(G,s,s); } } private void Dfs(Graph g, int v, int u) { marked[v] = true; foreach (var w in g.Adj(v)) { if (!marked[w]) Dfs(g, w, v); else if (w != u) hasCycle = true; } } public bool HasCycle() { return hasCycle; } } }
是二分圖嗎？（雙色問題）
namespace Graphs { public class TwoColor { private bool[] marked; private bool[] color; private bool isTwoColorable = true; public TwoColor(Graph G) { marked = new bool[G.V()]; color = new bool[G.V()]; for(var s = 0;s<G.V();s++) { if (!marked[s]) Dfs(G,s); } } private void Dfs(Graph g, int v) { marked[v] = true; foreach (var w in g.Adj(v)) { if (!marked[w]) { color[w] = !color[v]; Dfs(g, w); } else if (color[w] == color[v]) isTwoColorable = false; } } public bool IsBipartite() { return isTwoColorable; } } }
8.符號圖
在典型應用中，圖都是通過文件或者網頁定義的，使用的是字元串而非整數來表示和指代頂點。為了適應這樣的應用，我們使用符號圖。符號圖的API：
這份API 定義一個構造函數來讀取並構造圖，用 name() 和 index() 方法將輸入流中的頂點名和圖演算法使用的頂點索引對應起來。
實現
需要用到3種數據結構：
1.一個符號表 st ，鍵的類型為 string（頂點名），值的類型 int （索引）；
2.一個數組 keys[ ]，用作反向索引，保存每個頂點索引對應的頂點名；
3.一個 Graph 對象 G，它使用索引來引用圖中頂點。
SymbolGraph 會遍歷兩遍數據來構造以上數據結構，這主要是因為構造 Graph 對象需要頂點總數 V。在典型的實際應用中，在定義圖的文件中指明 V 和 E 可能會有些不便，而有了 SymbolGraph，就不需要擔心維護邊或頂點的總數。
namespace Graphs { public class SymbolGraph { private Dictionary<string, int> st;//符號名 -> 索引 private string[] keys;//索引 -> 符號名 private Graph G; public SymbolGraph(string fileName, string sp) { var strs = File.ReadAllLines(fileName); st = new Dictionary<string, int>(); //第一遍 foreach (var str in strs) { var _strs = str.Split(sp); foreach (var _str in _strs) { st.Add(_str,st.Count); } } keys = new string[st.Count]; foreach (var name in st.Keys) { keys[st[name]] = name; } //第二遍 將每一行的第一個頂點和該行的其他頂點相連 foreach (var str in strs) { var _strs = str.Split(sp); int v = st[_strs[0]]; for (var i = 1; i < _strs.Length; i++) { G.AddEdge(v,st[_strs[i]]); } } } public bool Contains(string s) { return st.ContainsKey(s); } public int Index(string s) { return st[s]; } public string Name(int v) { return keys[v]; } public Graph Gra() { return G; } } }
間隔的度數
可以使用 SymbolGraph 和 BreadthFirstPaths 來查找圖中的最短路徑：
總結
