圖論基礎複習

本章將複習一下圖論的基本理論。如果讀者以前接觸過圖算法，那麼可以便可以馬上開始本章的學習；如果讀者以前沒有相關圖算法背景知識，我們建議最好還是對其有一個瞭解，可以去看Cormen, Leiserson, 和Rivest寫的Introduction to Algorithms(《算法導論》)。

圖簡介

圖是用來解決各種實際問題的數學抽像。從根本上說，一個圖是由一組頂點集合和一組邊集合組成的，其中，一條邊連接圖中兩個頂點。更準確的描述是，一個組是一個（V，E）對，V是一個有限集，e是表示V的二元關係。V被稱作頂點集,其中的元素統稱為vertices。E是邊的集合，一條邊是一個(u,v) 對，u,v分別是頂點集V中的元素。在一個有向圖中，邊是一個連接源點和目標點的有序對。在一個無向圖中，邊是一個無序對，僅僅連接兩個頂點，因此五項途中（u，v）和（v，u）含義相同。

以上對於圖的定義在某些方面有點含糊不清，例如，沒有說清頂點和邊到底表示什麼。他們可能是城市和連接城市的公路；亦或是網頁和鏈接網頁的超鏈接。這些細節不被考慮到定義中是有原因的，它們不屬於圖抽像的部分。通過省略這些細節，我們能夠建立一個可復用的原理，它能夠幫我們解決各種不同的問題。

切回到我們的定義：圖是一組頂點和邊的集合。演示一下，我們來建立一個圖，該圖頂點已經用字母標好，因此邊可以簡單的寫成一個字母對。現在我們可以寫出一個有向圖，如下：

V = {v, b, x, z, a, y } E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) } G = (V, E)

圖一是該圖的圖示版。邊（x，x）叫做閉包。邊（b，y）和另一條（b，y）邊是平行邊，平行變僅僅出現在多重圖中（一般有向圖和無向圖是不允許出現的）。

**圖 1:** 一個有向圖的例子

下面我們將演示一個與圖一相似的圖，不過這次是無向的。圖二是該圖的圖示。閉包是不允許出現在無向圖中的。該圖是邊（b，y）的無向版本，相同的頂點和去除方向的邊。相同的邊被刪除，有些邊被合併，比如（a，z）和（z，a）。無向圖的有向版本是把其中每條邊換成兩條，每一條指向一個方向。

V = {v, b, x, z, a, y } E = { (b,y), (y,v), (z,a), (b,x), (x,v) } G = (V, E)

**圖 2:** 一個無向圖的例子

現在開始講講圖的專業術語吧。如果邊（u，v）屬於一個圖，那麼頂點v是頂點u的鄰接點。在一個有向圖中，邊（u，v）是頂點u的出邊、頂點v的入邊。在一個無向圖中，邊（u，v）是與u，v關聯的。

在圖一中，頂點y是頂點b的鄰接點（但是b不是y的鄰接）。邊（b，y）是b的出邊，是y的入邊。在圖二中，y是b的臨界點，反之亦然。邊（y，b）是與y和b關聯的。

在有向圖中，一個頂點出邊的數量叫做該點的出度，入邊的數量叫做該點的入度。無向圖中，點關聯的邊的數量叫做該點的度。在圖一中，頂點的出度是3，入度是0。在圖二中，頂點b僅僅是度為2。

路徑是圖中邊的序列，該序列中，每條邊的目標頂點是下一條邊的源頂點。如果一條路徑起始於頂點u終止於頂點v，那麼我們便說v是從u可到達的。如果一條路徑中沒有重複頂點，我們便稱該路徑是簡單的。路徑<(b,x),(x,v)>是簡單的，但是<(a,z),(z,a)>不是。路徑<(a,z),(z,a)>叫做環，因為路徑中起點和終點是同一個點。一個沒有環的圖被稱作無環的。

可平面圖是一個圖能夠被畫到一個平面上，並且其中沒有邊相互交叉。能夠用上面方法畫出的圖叫做平面圖。一個平面圖的面是被邊環繞的平面的連通區域。可平面圖的一個重要性質是：面、邊和頂點的數量關係遵循歐拉公式：|F|-|E|+|V|=2。這意味著簡單的可平面圖最多有O(|V|)條邊。

圖相關數據結構

在圖中，考慮使用什麼數據結構時，最重要的一個屬性是稀疏性，稀疏性指邊的數量相對於點的數量。一個圖中，邊的數量接近於頂點平方，該圖是稠密圖，反之，一個圖中E=α×V，並且α比V小得多的時候稱該圖為稀疏圖。表示稠密圖，鄰接矩陣表示法是最佳選擇；鄰接列表表示法是稀疏圖的最佳選擇。某些情況下，對於稀疏圖，邊-表表示法在空間效率選擇上更加合適。

鄰接矩陣表示法

圖的鄰接矩陣表示的就是一個V×V的2維數組。數組中的每一個元素auv存儲一個布爾值，該值表示邊（u，v）是否出現在圖中。圖三表示的是圖一的鄰接矩陣（刪除了平行邊（b，y））。存儲一個鄰接矩陣需要的空間是O(V2)。訪問、增加、刪除一條邊的複雜度是O(1)。增加或者刪除一個頂點需要重新分配空間並且拷貝整張圖到新的空間，負責度是O(V2)。 adjacency_matrix 類實現了按照BGL的圖接口規範實現了鄰接矩陣數據結構。

**圖 3:** 圖的鄰接矩陣表示法

鄰接表表示法

圖的鄰接列表表示的是每個頂點的出邊序列。對於一個稀疏圖來講，該表示法節省了空間，因為僅需了O(V + E)大小的內存。而且，訪問頂點出邊更加有效率。邊得插入操作複雜度是O(1)，但是訪問制定邊的效率是O(α)，α表示矩陣的稀疏因子（稀疏因子等於最大的頂點出度）。圖四表示的是圖一的鄰接列表。 adjacency_list 類是鄰接列表表示法的一個實現。

**圖 4:** 圖的鄰接表表示法

邊列表表示法

圖的邊列表表示就是一個邊的序列，其中每條邊使用一個頂點ID對來表示的。該表示法僅需要O(E)大小的內存。邊插入複雜度是O(1)，但是訪問一個指定邊的複雜度是O(E)（效率低下）。圖五表示了圖一的邊列表表示。 edge_list適配器類內被用來實現邊列表表示。

**圖 5:** 圖的邊列表表示法

圖相關算法

圖搜索算法

樹邊是通過圖搜索算法遍歷一個圖時所建立的搜索樹的邊。如果遍歷邊（調用 visitor 的explore ()方法）（u，v）時，點v首先被遍歷到，那麼邊（u，v）就是一條樹邊。在搜索樹中，後向邊連接頂點到他們的祖先。所以邊（u，v）中，點v一定是點 u的祖先。閉包被認為是反向邊。前向邊是非樹邊，搜索樹中（u，v）連接點u到它的子孫節點v。交叉邊是不屬於前面三種定義的邊。

廣度優先搜索

廣度優先搜索（BFS）是指從某點開始遍歷整張圖，遍歷順序是首先遍歷該點的鄰居結點會，然後是它鄰居節點的鄰居節點優先遍歷到，直至遍歷完整張圖。可以把深度優先遍歷想像成石子落入水中時激起的漣漪，在相同波浪的頂點和源點的距離是相同的。發現點是該算法瀏覽時首先遇到的點，結束點是遍歷完它所有鄰居的最後一個點。下面有一個例子將幫助你理解。圖六中展示了一幅圖，並且在圖下面列出了BFS（深度優先算法）的算法中頂點的發現和結束順序。

**圖 6:** 圖遍歷的廣度優先搜索

  order of discovery: s r w v t x u y 
  order of finish: s r w v t x u y

我們從s點開始，首先訪問的是r和w（s的兩個鄰居）。它的兩個鄰居都被訪問過後，我們將訪問r的鄰居（頂點v），然後訪問w的鄰居（r和w的發現順序無所謂）t和x。最後，我們訪問t和x的鄰居u和y。

為了能夠知道我們在圖中的位置以及知道將要訪問的下一個點，BFS算法需要對頂點進行染色（color）（請參考 Property Maps一節來瞭解更多關於圖屬性的細節）。顏色值既可以放在圖結構內，也可以作為算法的參數傳進去。

深度優先搜索

深度優先搜索（DFS）訪問圖中所有頂點的方法是，我們依據邊來進行遍歷，該算法會始終選擇圖中較深一層的邊來遍歷。也就是說，DFS會首先訪問它未被訪問的鄰接頂點，然後鄰接頂點訪問該鄰接頂點的鄰接頂點，直到一點沒有鄰接頂點時，再回溯到前面頂點繼續沿著未被訪問的邊來遍歷頂點。DFS算法從一點遍歷完所有能夠到達的頂點後，它將選擇仍未被發現的頂點來進行搜索。搜索的過程建立了一組深度優先樹（depth-first trees），這些樹合起來就成了深度優先森林（depth-first forest）。DFS把圖中的邊分為三類：樹邊，反向邊和正向邊（或稱交叉邊）。根據一些典型的深度優先森林，邊還有一些其它的分類方法。

DFS一個比較有意思的特性是按點的發現和結束順序插入到括號中，方法是：把發現一點放到左括號，把結束一點放到右括號，最後形成了一個嵌套的括號集合。圖七展示了DFS對於一個無向圖的應用，該圖邊上已經標好了遍歷的順序。下面我們列出了發現和結束的順序，以及嵌套的括號集合。DFS是其他一些算法的核心，比如托普排序和連通份量算法。DFS算法還能檢測是圖中是否存在環（參考文件依賴例子中的Cylic Dependencies（循環依賴）一節）。

**圖 7:** 無向圖的深度優先搜索

  order of discovery: a b e d c f g h i
  order of finish: d f c e b a
  parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)

最小生成樹問題

最小生成樹（minimum-spanning-tree）定義如下：從E中找到一個無環子集T，E是連接這圖中所有頂點，要求T權值是最小的，權值計算法法如下：

w(T) = sum of w(u,v) over all (u,v) in T, where w(u,v) is the weight on the edge (u,v)

這樣的T稱為最小生成樹。

最短路徑算法

圖論中的一個經典問題是找出兩點之間的最短路徑。在圖G中，一條路徑是一個頂點序列<v0,v1,....,Vk>，使得序列中的每個頂點都和下一個頂點相連(邊（vi，vi+1）i=0,1,....k屬於邊集E)。在最短路徑問題中，每條邊都會給出一個值作為權值。因此，我們可以說一條路徑的權值是：

w(p) = sum from i=1..k of w(v_i-1,v_i)

頂點u到v的最短路徑的權值是：

delta (u,v) = min { w(p) : u --> v } if there is a path from u to v
delta (u,v) = infinity otherwise.

最短路徑可以是權值等於最短路徑權值的任何一條路徑。

還有一些最短路徑的衍生問題。上面我們定義了single-pair問題，但是還有一個single-source問題，該問題等效於單目標single -destination問題和all-pairs問題。沒有解決single-pair問題比解決single-source問題還快的算法。

在圖G=(V,E)中，以某點為根的最短路徑樹是該圖的一個有向子圖G'=(V',E')，其中V'是V的子集，E'是E的子集，而且V'還是該點能夠到到達頂點的集合。G'是一顆以頂點為根的有根樹，因而，從V'中一點v到G'中一點u的唯一簡單路徑就是從v到u的最短路徑。single-source 算法的結果就是一顆最短路徑樹。

網絡流算法

一個網絡流是一個以頂點s為源點，以頂點t為接受點的有向圖G=(V,E)。每條邊e均具有一個非負容量（capacity ）c(e)而且每個頂點對還有一個流f(e)。流一定要滿足下面三個條件：

容量約束(Capacity constraint)：對於V*V中所有頂點對(u, v)有：f(u,v) <= c(u,v)
斜對稱性(Skew symmetry):對於V*V中所有頂點對(u, v)有：f(u,v) = - f(v,u)
流守恆(Flow conservation)：f(u,v) = 0

網絡流是指流向接收點t的流（等效於流出源點s的流）。

|f| = sum_{u in V} f(u,t) = sum_{v in V} f(s,v)

一條邊的剩餘容量為：r(u,v) = c(u,v) - f(u,v)。如果r(u,v)>0則該邊是有餘量的，包含該邊的圖為有餘量圖。如果r(u,v)=0，則該邊為飽和的。

最大流問題是指確定|f|的最大值和圖中每個頂點對相應的流是多少。

圖八表示一個流網絡，頂點A為源點，頂點H為終點。

**Figure 8:** 一個最大流網絡
邊已經被標上流和容量值

解決最大流問題算法已經有很長歷史了，首先提出解決該問題的算法是 Ford 和 Fulkerson.對於數據最通用的算法是Goldberg提出的push-relabel算法，該算法基於Karzanov提出的前向(preflow)概念。

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)