第6章圖6.1圖的基本介紹6.1.1圖的定義圖G是一個有序二元組(V,E)，其中V稱為頂集(VerticesSet)，E稱為邊集(Edgesset)，E與V不相交。它們亦可寫成V(G)和E(G)。其中，頂集的元素被稱為頂點(Vertex)，邊集的元素被稱為邊(edge)。E的元素都是二元組，用(x,y)表示，其中x,y∈V。下面是有關圖的一些基本概念。有向圖、無向圖：如果給圖的每條邊規定一個方向，那么得到的圖稱為有向圖，如圖(a)所示。在有向圖中，與一個結點相關聯的邊有出邊和入邊之分。相反，邊沒有方向的圖稱為無向圖，如圖(b)所示。完全圖：完全圖是指邊數達到最大值的圖，即在頂點數為n的無向圖中，邊數為n(n-1)/2；在頂點數為n的有向圖中，邊數為n(n-1)，如圖(c)所示。單圖：一個圖如果任意兩頂點之間只有一條邊（在有向圖中為兩頂點之間每個方向只有一條邊）；邊集中不含環，則稱為單圖。連通圖：若V(G)中任意兩個不同的頂點Vi和Vj都連通（即有路徑），則稱G為連通圖(ConnectedGraph)。連通分量：無向圖的極大連通子圖稱為的連通分量(ConnectedComponent)。任何連通圖的連通分量只有一個，即是其自身，非連通的無向圖有多個連通分量，如圖所示。強連通圖：有向圖中，若對于V(G)中任意兩個不同的頂點Vi和Vj，都存在從Vi到Vj以及從Vj到Vi的路徑，則稱是強連通圖。強連通分量：有向圖的極大強連通子圖稱為G的強連通分量，強連通圖只有一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。要注意強連通圖和強連通分量只是針對有向圖而言的。強連通分量：有向圖的極大強連通子圖稱為G的強連通分量，強連通圖只有一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。要注意強連通圖和強連通分量只是針對有向圖而言的。子圖（Sub-Graph）：當圖G'=(V',E')其中V‘包含于V，E’包含于E，則G'稱作圖G=(V,E)的子圖。每個圖都是本身的子圖。度（Degree）：一個頂點的度是指與該頂點相關聯的邊的條數，頂點v的度記作d(v)。入度（In-degree）和出度（Out-degree）：對于有向圖來說，一個頂點的度可細分為入度和出度。一個頂點的入度是指與其關聯的各邊之中，以其為終點的邊數；出度則是相對的概念，指以該頂點為起點的邊數。自環（Loop）：若一條邊的兩個頂點為同一頂點，則此邊稱作自環。路徑（Path）：從u到v的一條路徑是指一個序列v0,e1,v1,e2,v2,...ek,vk，其中ei的頂點為vi及vi-1，k稱作路徑的長度。如果它的起止頂點相同，該路徑是“閉”的，反之，則稱為“開”的。一條路徑稱為一簡單路徑(simplepath)，如果路徑中除起始與終止頂點可以重合外，所有頂點兩兩不等。網：網指的是邊上帶權值的圖。通常權值為非負實數，可以表示為從一個頂點到另一個頂點的距離、時間和代價等。6.1.2圖的存儲方法1．鄰接矩陣法

鄰接矩陣（AdjacencyMatrix）是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖，其中V={v1,v2,…,vn}。G的鄰接矩陣是一個具有下列性質的n階方陣：①對無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，有向圖則不一定如此。②在無向圖中，任一頂點i的度為第i列（或第i行）所有非零元素的個數，在有向圖中頂點i的出度為第i行所有非零元素的個數，而入度為第i列所有非零元素的個數。③用鄰接矩陣法表示圖共需要n2個空間，由于無向圖的鄰接矩陣一定具有對稱關系，所以扣除對角線為零外，僅需要存儲上三角形或下三角形的數據即可，因此僅需要n(n-1)/2個空間。④稠密圖適合使用鄰接矩陣的存儲表示。圖的領接矩陣存儲結構定義如下：

2．鄰接表法圖的鄰接表存儲方法是一種順序分配和鏈式分配相結合的存儲結構。如果這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放于表頭結點所指向的單向鏈表中，這個單鏈表稱為該頂點的邊表。邊表的頭指針和頂點的數據信息采用順序存儲（稱為頂點表），所以在鄰接表中存在兩種結點：頂點表結點和邊表結點，如圖所示。無向圖和有向圖的鄰接表實例分別如左下圖和右下圖所示。圖的鄰接表存儲結構定義如下：3．鄰接表的基本操作（1）創建無向圖（2）創建有向圖創建有向圖的操作與創建無向圖類似，只不過只需要插入一種方向的邊。（3）插入邊結點插入邊結點的算法add_arc(i,j,value)是指在邊表中插入一個由序號為i的頂點指向序號為j的頂點的權值為value的邊結點。插入過程采用頭插法的方法。（4）查找頂點序號為i的第一個鄰接點（5）查找下一個鄰接點（6）獲取頂點u到頂點v的邊權值圖的鄰接表存儲方法具有以下特點：1．若圖G為無向圖，則鄰接表存儲方法所需的存儲空間為O(|V|+2|E|)；若圖G為有向圖，則所需的存儲空間為O(|V|+|E|)。前者是后者的兩倍是由于在無向圖中，每條邊在鄰接表中出現了兩次。2．對稀疏圖而言，采用鄰接表法表示圖可以極大地節省存儲空間。3．在鄰接表中，如果給定一個頂點，則能夠很容易獲得它的所有鄰邊；而在鄰接矩陣需要掃描一整行，花費的時間為O(n)。但是如果要確定給定兩個頂點間是否存在邊，在鄰接矩陣里可以立刻查到；而在鄰接表中需要在相應頂點的邊表上遍歷查詢另一個結點，效率較低。4．圖的鄰接表表示不是唯一的，每個頂點的邊表各結點次序可以是任意的，它取決于建立鄰接表的算法以及邊的輸入次序。除了鄰接矩陣法和鄰接表法，還有十字鏈表和鄰接多重表，有興趣的同學可以查閱相關資料了解。6.2圖的遍歷6.2.1廣度優先搜索廣度優先搜索算法（Breadth-FirstSearch，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索算法。廣度優先搜索算法類似于二叉樹的層次遍歷算法。對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之后，依次訪問頂點v的所有未被訪問過的鄰接點，然后再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。在廣度優先搜索中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便后面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然后，再依次出隊，并訪問它們的鄰接點。同時為了避免重復訪問某個頂點，也需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。廣度優先搜索的算法描述如下：下面通過實例來演示圖的廣度優先搜索的過程，給定圖如下所示。假設從結點a開始進行廣度優先搜索，先將a入隊，并把a標記為已訪問。此時隊列非空，將隊頭結點a出隊，由于結點b和結點c都與結點鄰接且未被訪問過，故將結點b和結點c入隊；此時隊列非空，將隊頭結點b出隊，由于結點d和結點e都與結點b鄰接，故將結點d和結點e鄰接；此時隊列非空，將隊頭結點c出隊，由于結點f、g、h與結點c鄰接，故將結點f、g、h入隊；此時隊列非空，將隊頭結點d入隊，由于沒有結點與其鄰接，故繼續循環出隊；當結點f作為隊頭結點出隊時，由于結點i與其鄰接，故將結點i入隊……最終取出隊頭結點i之后，隊列為空，從而循環結束。此次遍歷的結果為abcdefghi。從上述演示的過程中，不難發現圖的廣度優先搜索和二叉樹的層次遍歷是類似的，這也說明了圖的廣度優先搜索算法是二叉樹的層次遍歷算法的擴展。實現廣度優先搜索算法總是需要一個輔助隊列Q，n個頂點均需入隊一次，在最壞情況下，空間復雜度為O(|V|)。采用鄰接表存儲方式時，每個頂點均需搜索一次（或入隊一次），故時間復雜度為O(|V|)，在搜索任一頂點的鄰接點時，每條邊至少被訪問一次，故時間復雜度為O(|E|)，則算法總的時間復雜度為O(|V|+|E|)。采用鄰接矩陣存儲方式時，查找每個頂點的鄰接點的時間復雜度為O(|V|)，故算法中的時間復雜度為O(|V|2)。6.2.2深度優先搜索深度優先搜索算法（Depth-FirstSearch，DFS）是一種用于遍歷或搜索樹或圖的算法。這個算法會盡可能深地搜索一個圖。首先訪問某一起始結點v，然后由結點v出發，去訪問與結點v鄰接且未被訪問過的任一結點v1，再去訪問與結點v1鄰接且未被訪問過的任一結點v2……重復如上過程。當不能再往下繼續訪問時，搜索將回溯到最近被訪問的結點，如果該節點還有未被訪問的鄰接結點，則繼續朝該鄰接結點搜索下去，直至圖中所有的結點都已經被訪問過。深度優先搜索算法由于其向下搜索并且需要回溯的特性，通常以遞歸的形式來實現，遞歸形式的實現代碼也比較簡潔。深度優先搜索算法由于其向下搜索并且需要回溯的特性，通常以遞歸的形式來實現，遞歸形式的實現代碼也比較簡潔。

深度優先搜索的遞歸形式算法如下：下面通過實例來演示圖的深度優先搜索的過程，遍歷過程如圖6.8所示。假設從結點a開始進行深度優先搜索，把結點a標記為已訪問；向下訪問結點a的第一個鄰接結點b，把結點b標記為已訪問；繼續向下訪問結點b的第一個鄰接結點d，把結點d標記為已訪問；發現結點d沒有鄰接結點，則回溯到結點b，尋找是否存在與結點b鄰接的未訪問結點，如不存在則繼續回溯……最終最上層的遞歸程序結束，所有的結點都被訪問完畢。此次遍歷的結果為abdecfigh。

從深度優先搜索的過程中不難發現，圖的深度優先搜索和二叉樹的先序遍歷是有相通之處的，都是從初始結點開始，逐步往深處搜索。

深度優先搜索算法是一個遞歸算法，需要借助一個遞歸工作棧，故其空間復雜度為O(|V|)。當圖以鄰接表表示時，查找所有頂點的鄰接點所需的時間為O(|E|)，訪問頂點所需的時間為O(|V|)，此時，總的時間復雜度為O(|V|+|E|)。當圖以鄰接矩陣表示時，查找每個頂點的鄰接點所需的時間為O(|V|)，故總的時間復雜度為O(|V|2)。6.3圖的應用6.3.1最小生成樹最小生成樹是一幅連通加權無向圖中一棵權值最小的生成樹。在一給定的帶權無向圖G=(V,E)中，生成樹不同，每棵樹的權（即樹中所有邊上的權值之和）也可能不同。設S為G的所有生成樹的集合，若T為S中邊的權值之和最小的那棵生成樹，則T成為G的最小生成樹（MinimumSpanningTree,MST）。一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小于或者等于其它生成樹的邊的權值之和。廣義上而言，對于非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的并被稱為最小生成森林。以有線電視電纜的架設為例，若只能沿著街道布線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使布線成本最低。實現最小生成樹的算法主要有Prim（普里姆）算法和Kruskal（克魯斯卡爾）算法。1．Prim算法該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克發現；并在1957年由美國計算機科學家羅伯特·普里姆獨立發現；1959年，艾茲格·迪科斯徹再次發現了該算法。Prim算法步驟如下：1）輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；2）初始化：Vnew={x}，其中x為集合V中的任一結點（起始點），Enew={},為空；3）重復下列操作，直到Vnew=V：a.在集合E中選取權值最小的邊<u,v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；b.將v加入集合Vnew中，將<u,v>邊加入集合Enew中；4）輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。Prim算法構造最小生成樹的過程如圖所示。初始時取頂點1加入樹T，此時樹中只含有一個頂點，之后再選擇一個與當前T中頂點集合中距離最近的頂點，并將該頂點和相應的邊加入樹T，每次操作后樹T的頂點數和邊數都加一。以此類推，直到圖中所有頂點都被加入到樹T中，得到的樹T就是最小生成樹。如在第一輪中，與V1相連的點有V2、V3、V4，其中V1到V3的距離最近，故將V3和該邊加入樹中；在第二輪中，在V1和V3相連的邊中再取距離最近的邊，故將V6和V3到V6的邊加入樹中……直至構造最小生成樹完成。Prim算法的時間復雜度為O(|V|2)，不依賴于邊數，故該算法更適合求解邊稠密的圖的最小生成樹。2．Kruskal算法Kruskal算法由JosephKruskal在1956年發表。與Prim算法從頂點開始擴展最小生成樹不同，Kruskal算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法。Kruskal算法步驟如下：1）新建圖G，G中擁有原圖中相同的結點，但沒有邊；2）將原圖中所有的邊按權值從小到大排序；3）從權值最小的邊開始，如果這條邊連接的兩個結點于圖G中不在同一個連通分量中，則添加這條邊到圖G中；4）重復3，直至圖G中所有的結點都在同一個連通分量中。Kruskal算法構造最小生成樹的過程如圖所示。

通常在Kruskal算法中，采用堆來存放邊的集合，因此每次選擇最小權值邊只需O(log|E|)的時間，故總的時間復雜度為O(|E|log|E|)。由于Kruskal算法的時間復雜度與圖中的邊數相關，故Kruskal算法適合于邊稀疏而頂點較多的圖。6.3.2最短路徑最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。其中帶權有向圖G的最短路徑問題一般可分類為兩種：一是單源最短路問題，即已知起始結點，求最短路徑的問題，在邊權非負時適合使用Dijkstra算法，若邊權為負時則適合使用Floyd算法；二是求每對頂點間的最短路徑，可通過Floyd算法來求解。1．Dijkstra算法Dijkstra（迪杰斯特拉）算法是荷蘭計算機科學家EdsgerWybeDijkstra在1956年發現的算法，并于3年后在期刊上發表。迪杰斯特拉算法使用類似廣度優先搜索的方法解決賦權圖的單源最短路徑問題

下面通過實例來演示Dijkstra算法的過程，如圖和表所示。算法執行過程的說明如下。

初始化：集合S初始為{v1}，v1可到達v2和v5，不能到達v3和v4，故dist[]數組各元素的初始值依次設置為dist[2]=10，dist[3]=∞，dist[4]=∞，dist[5]=5。

第一輪：選出dist[]中的最小值dist[5]，將頂點v5并入集合S，即此時已經找到v1到v5的最短路徑。當v5加入到集合S后，從v1到集合V-S中可達頂點的最短路徑長度可能會發生變化，因此需要更新dist[]數組。v5可以到達v2，由于v1→v5→v4的距離8比dist[2]=10要小，故更新dist[2]為8；v5可以到達v3，由于v1→v5→v3的距離14比dist[3]=∞要小，故更新dist[3]為14；v5可以到達v4，由于v1→v5→v4的距離7比dist[4]=∞要小，故更新dist[4]為7。

第二輪：選出最小值dist[4]，將頂點v4并入集合S，繼續更新dist[]數組。v4不可到達v2，則dist[2]不變；v4可到達v3，v1→v5→v4→v3的距離13比dist[3]=14要小，故更新dist[3]為13。

第三輪：選出最小值dist[2]，將頂點v2并入集合S，繼續更新dist[]數組。v2可到達v3，v1→v5→v2→v3的距離9比dist[3]小，故更新dist[3]為9。

第四輪：選出唯一的最小值dist[3]，將頂點v3并入集合S，此時全部的頂點都已包含在S中。

從過程說明中可以發現，Dijkstra算法是基于貪心策略的。在使用鄰接矩陣或鄰接表存儲方法存儲圖時，Dijkstra算法的時間復雜度都為O(|V|2)。Dijkstra算法有一個值得注意的缺點，當邊上帶有負權值時該算法并不適用。若允許邊上帶有負權值，則在與S（已求得最短路徑的頂點集）內某點（記為v1）以負邊相連的點（記為v2）確定其為最短路徑時，其最短路徑長度加上這條負邊的權值結果可能小于v1原先確認的最短路徑長度，而此時v1在Dijkstra算法下是無法更新的。2．Floyd算法Floyd（弗洛伊德）算法是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權（但不可存在負權回路）的最短路徑問題。Floyd算法的原理是動態規劃。其算法步驟如下：1）設Di,j,k為從i到j的只以（1..k）集合中的結點為中間結點的最短路徑長度。2）若最短路徑經過點k，則Di,j,k=Di,k,k-1+Dk,j,k-1;若最短路徑不經過點k，則Di,j,k=Di,j,k-1。3）Di,j,k=min(Di,j,k-1,Di,k,k-1,Dk,j,k-1)。Floyd算法的時間復雜度為O(|V|3)。6.3.3拓撲排序在整個工程中，有些子工程(活動)必須在其它有關子工程完成之后才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先后關系，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先后關系，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之后，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先后關系的有向圖稱作頂點活動網(ActivityOnVertexnetwork)，簡稱AOV網。一個AOV網應該是一個有向無環圖，即不應該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行。在AOV網中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topologicalorder)，由AOV網構造拓撲序列的過程叫做拓撲排序(Topologicalsort)。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現沖突的情況。在圖論中，由一個有向無環圖的頂點組成的序列，當且僅當滿足下列條件時，才能稱為該圖的一個拓撲排序（Topologicalsorting）：

1）序列中包含每個頂點，且每個頂點只出現一次；2）若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。有向無環圖的拓撲排序過程如圖所示。每一輪選擇一個入度為0的頂點并輸出，然后刪除該頂點和所有以它為起點的有向邊，所以該圖最后得到的拓撲排序結果為{1,3,4,5,2}。由于拓撲排序中輸出每個頂點的同時還要刪除以它為起點的邊，故拓撲排序的時間復雜度為O(|V|+|E|)。6.3.4關鍵路徑關鍵路徑通常是決定項目工期的進度活動序列。它是項目中最長的路徑，即使很小浮動也可能直接影響整個項目的最早完成時間。關鍵路徑的工期決定了整個項目的工期。關鍵路徑上的活動稱為關鍵活動。關鍵路徑在1950年代由杜邦的MorganR.Walker和JamesE.Kelley提出。用頂點表示事件，弧表示活動，弧上的權值表示活動持續時間的帶權有向圖叫AOE（ActivityOnEdgeNetwork）網。AOE網有以下特點：1）只有在某頂點所代表的事件發生后，從該頂點出發的各有向邊所代表的活動才能開始。2）只有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。在AOE網中，僅有一個入度為0的頂點，稱為開始頂點（源點），它表示整個工程的開始；網中也僅存在一個出度為0的頂點，稱為結束頂點（匯點），它表示整個工程的結束。在AOE網中，有些活動是可以并行進行的。從源點到匯點的有向路徑可能有多條，并且這些路徑長度可能不同。完成不同路徑上的活動所需的時間雖然不同，但是只有所有路徑上的活動都已經完成，整個工程才算結束。因此從源點到匯點的所有路徑中，具有最大路徑長度的路徑稱為關鍵路徑，而把關鍵路徑上的活動稱為關鍵活動。完成整個工程的最短時間就是關鍵路徑的長度，即關鍵路徑上各活動花費開銷的總和。這是因為關鍵活動影響了整個工程的時間，若關鍵活動不能按時完成，則整個工程的完成時間就會延長。所以說找到了關鍵路徑，就能得出整個工程的最短完成時間。尋找關鍵活動時會用到幾個參量的定義。1．事件vk的最早發生時間ve(k)它是指從源點v1到頂點vk的最長路徑長度。事件vk的最早發生事件決定了所有從vk開始的活動能夠開工的最早事件。可用以下的遞推公式來計算：ve(源點)=0ve(k)=Max{ve(j)+Weight(vj,vk)}，其中vk為vj的任意后繼，Weight(vj,vk)表示<vj,vk>上的權值。2．事件vk的最遲發生時間vl(k)它是指在不推遲整個工程完成的前提下，即保證它的后繼事件vj在其最遲發生時間vl(j)能夠發生時，該事件最遲必須發生的時間。可用以下的遞推公式來計算：vl(匯點)=ve(匯點)vl(k)=Min(vl(j)–Weight(vk,vj))，其中vk為vj的任意前驅。

3．活動ai的最早開始時間e(i)它是指該活動弧的起點所表示的事件的最早發生時間。若邊<vk,vj>表示活動ai，則有e(i)=ve(k)。

4．活動ai的最遲開始時間l(i)它是指該活動弧的終點所表示事件的最遲發生時間與該活動所需時間之差。若邊<vk,vj>表示活動ai，則有l(i)=vl(i)–Weight(vk,vj)。5．一個活動ai的最遲開始時間l(i)和其最早開始時間e(i)的差額d(i)=l(i)–e(i)它是指該活動完成的時間余量，即在不增加完成整個工程所需總時間的情況下，活動ai可以拖延的時間。若一個活動的時間余量為0，則說明該活動必須要如期完成，否則就會拖延整