數據結構與算法6

第6章圖（4課時）圖也是一種非常重要的非線性數據結構，它比樹結構更為復雜。在樹結構中，各數據元素之前有著明顯的層次關系，上一層中的一個前繼結點對應下一層中的d（d≥0）個后繼結點，但下一層中的一個后繼結點最多只與上一層中的一個前繼結點相關，因此，樹型結構主要是用來表示數據元素之間一對多的關系。而在圖結構中，結點之間的關系可以是任意的，圖中任意兩個結點都可能相關，圖結構可以用來表示數據元素之間多對多的關系。6.1

圖的基本概念及特性6.1.1圖的基本概念6.1.2用圖來描述實際問題6.1圖的基本概念及特性6.1.1圖的基本概念圖G由頂點（圖中通常將結點稱為頂點）的非空有限集合V和邊的集合E組成，記為G=(V,E)。每一個頂點偶對就是圖中的一條邊，所以，E用于表示V上的連接關系。在一個圖中，至少要包含一個頂點，但可以沒有任何邊。通常用V(G)和E(G)來表示圖G的頂點集合和邊集合。下面給出圖的基本術語。1.有向圖和無向圖若E(G)中的頂點偶對是有序的，則這些有序偶對就形成了有向邊，此時圖G稱為有向圖。其中，有向邊也簡稱為弧。在有向圖G中，對于一條從頂點vi到頂點vj的弧，記作<vi,vj>并有<vi,vj>∈E(G)，稱vi為弧尾，vj為弧頭。例如，圖6-1（a）中所示的G1是一個有向圖，其頂點集合V(G1)={v0,v1,v2,v3,v4}，邊集合E(G1)={<v0,v1>,<v0,v2>,<v1,v4>,<v2,v0>,<v3,v0>,<v3,v2>}。6.1圖的基本概念及特性6.1.1圖的基本概念2.頂點的度、入度和出度在無向圖G中，若存在(vi,vj)∈E(G)，則稱頂點vi和頂點vj互為鄰接點，即頂點vi和頂點vj相鄰接，或者說頂點vi、vj與邊(vi,vj)相關聯(lián)。與頂點vi相關聯(lián)的邊的數目稱為頂點vi的度，記作D(vi)。例如，圖6-1（b）所示的無向圖G2中，各頂點的度分別為：D(v0)=3，D(v1)=D(v2)=D(v3)=2，D(v4)=1。在有向圖G中，若存在<vi,vj>∈E(G)，則稱頂點vi鄰接到頂點vj，或頂點vj鄰接自頂點vi。以頂點vi為弧頭的弧的數目稱為頂點vi的入度，記作ID(vi)；以頂點vi為弧尾的弧的數目稱為vi的出度，記作OD(vi)；頂點vi的入度和出度之和稱為vi的度，記作D(vi)。6.1圖的基本概念及特性6.1.1圖的基本概念3.路徑、路徑長度和回路

在圖G中，若存在一個頂點序列(,,…,)，使得對于任意0≤j<n-1有（若G為有向圖）或（若G為無向圖），則該序列是從頂點到頂點的一條路徑。顯然，從一個頂點到另一個頂點的路徑不一定唯一。一條路徑中邊的數目稱為路徑長度。在一條路徑中，若一個頂點至多只經過一次，則該路徑稱為簡單路徑；若組成路徑的頂點序列中第一個頂點與最后一個頂點相同，則該路徑稱為回路（或環(huán)）；在一個回路中，若除第一個頂點與最后一個頂點外，其他頂點只出現一次，則該回路稱為簡單回路（或簡單環(huán)）。6.1圖的基本概念及特性6.1.1圖的基本概念4.連通圖對無向圖，若至少存在一條從頂點vi到頂點vj的路徑，則稱頂點vi和頂點vj是連通的。若無向圖G中任意兩個頂點都是連通的，則稱G為連通圖。

對有向圖，若存在從頂點vi到頂點vj的路徑或存在從頂點vj到頂點vi的路徑，則稱頂點vi和頂點vj是單向連通的；若兩條路徑同時存在則稱頂點vi和頂點vj是強連通的。有向圖G中，若任意兩個頂點都是單向連通的，則稱G是單向連通圖；若任意兩個頂點都是強連通的，則稱G為強連通圖。6.1圖的基本概念及特性6.1.1圖的基本概念5.子圖、連通分量和強連通分量

對于圖G、G'，若滿足且，則G'是G的子圖。也就是說，從圖G的頂點集合中選出一個子集并從邊集合中選出與該頂點子集相關的一些邊所構成的圖，就是圖G的子圖。

一個無向圖的極大連通子圖稱為該無向圖的連通分量；一個有向圖的極大強連通子圖稱為該有向圖的強連通分量。這里的“極大”是指向連通子圖或強連通子圖中再添加一個頂點，該子圖就不再連通或強連通。顯然，若一個圖本身就是連通圖或強連通圖，那么它的連通分量或強連通分量就是圖本身，具有唯一性。若一個圖本身是非連通圖或非強連通圖，那么它的連通分量可能有多種形式。

6.1圖的基本概念及特性6.1.1圖的基本概念

例如，圖6-2（a）和圖6-2（c）分別是非連通圖和非強連通圖，對應的兩種形式的連通分量和強連通分量分別如圖6-2（b）和圖6-2（d）所示。

6.1圖的基本概念及特性6.1.1圖的基本概念6.權和帶權圖

與前一章學習的樹中結點的權相似，可以為一個圖中的每條邊標上一個具有某種意義的實數，該實數就稱為是邊的權。通常用邊的權表示從一個頂點到另一個頂點的代價。邊上帶權的圖就稱為帶權圖。

6.1圖的基本概念及特性6.1.1圖的基本概念7.生成樹和最小生成樹

若無向圖G的一個子圖G'是一棵包含圖G所有頂點的樹，則G'稱為圖G的生成樹。生成樹本身是一棵樹，具備樹的所有性質。對于樹中的任一結點，根結點都是其祖先，因此樹中的任意兩個結點都是連通的，即子圖G'是連通圖。另一方面，子圖G'與圖G具有相同的頂點集合，而子圖G'的邊集合是圖G邊集合的子集，因此圖G必然也是連通圖。也就是說，只有連通圖才有生成樹。

連通圖的生成樹不具有唯一性，從不同的頂點出發(fā)或采用不同的遍歷算法，可以得到不同的生成樹。6.1圖的基本概念及特性6.1.1圖的基本概念例如，圖6-3（b）所示的就是根據圖6-3（a）得到的兩種不同形式的生成樹。在所有形式的生成樹中，邊上的權之和最小的生成樹，稱為最小生成樹。

6.1圖的基本概念及特性6.1.1圖的基本概念下面通過兩個實例介紹如何用圖來描述實際問題?！纠?-1】有若干個城市，通過在兩個城市之間修建高速公路使得從任一城市出發(fā)經過高速公路都可以到達另一城市。為了使修建高速公路的工程總造價最低，應如何設計？

該問題的圖描述如下：將所有城市作為圖的頂點，任意兩個頂點相連接形成邊，兩個城市之間修建高速公路的工程造價作為邊的權。顯然，邊沒有方向，因此對于該問題應使用無向圖表示。

如圖6-4（a）所示是該問題的一個圖描述示例，這里考慮4個城市，任意兩個城市之間修建高速公路的工程造價作為邊的權在邊上標注。從而，該問題就轉化為了從圖G中計算子圖G'的問題，目標子圖G'具有如下特點：6.1圖的基本概念及特性6.1.2用圖來描述實際問題是一個連通圖且包含圖G中的所有頂點（從任一城市出發(fā)可以到達另一城市）；在所有滿足上一條件的子圖中，目標子圖G'的權之和最?。üこ炭傇靸r最低）。根據上述兩條特點，可知目標子圖G'應是一棵樹（刪除任一條邊都會導致子圖不連通，添加任一條邊都會使最終的權之和增加），并且應該是具有最小權之和的最小生成樹。關于最小生成樹的計算方法在6.4.1節(jié)中給出。6.1圖的基本概念及特性6.1.2用圖來描述實際問題【例6-2】一個人開車從一個地方去另一個地方，有多種路線，為了使總里程數最少，應走哪條路線？該問題的圖描述如下：將所有路口作為圖的頂點，路口之間的道路作為連接兩個頂點的邊，道路長度作為邊的權。考慮有些道路是單行路，且往返行駛里程數可能會有所不同，因此，對于該問題應使用有向圖表示。如圖6-4（b）所示是該問題的一個圖描述示例，這里考慮5個路口，從一個路口到另一個路口的行駛里程數作為邊的權在邊上標注。從而，該問題就轉化為了計算圖中兩個頂點間最短路徑的問題。關于最短路徑的計算方法在6.4.2節(jié)中給出。6.1圖的基本概念及特性6.1.2用圖來描述實際問題6.2圖的抽象數據類型和表示方式圖一般需要進行下面的基本操作：創(chuàng)建圖對圖作深度優(yōu)先遍歷對圖作廣度優(yōu)先遍歷獲取頂點數目獲取邊的數目獲取與指定頂點相關聯(lián)的第一條邊獲取與指定邊有相同關聯(lián)頂點的下一條邊添加一個頂點添加一條邊獲取一個頂點中存儲的數據判斷一條邊是否存在設置一條邊的權獲取一條邊的權6.2圖的抽象數據類型和表示方式在計算機中存儲圖，主要是要確定頂點的存儲方式及頂點之間關系（即邊）的存儲方式。與前面學習的線性表和樹相比，圖存儲的難點在于頂點之間的關系更為復雜（圖中任意兩個頂點都可以通過連接形成邊）。因此，如何存儲圖中的邊以方便地對邊進行增、刪、改、查等操作是圖存儲要解決的首要問題。根據邊的存儲方式的不同，圖的存儲結構有多種表示方法，讀者可以根據實際應用需要選取合適的表示方法。下面主要介紹鄰接矩陣、鄰接壓縮表和鄰接鏈表這三種常用表示方法并給出每種表示方法的具體實現。6.2圖的抽象數據類型和表示方式6.2.1鄰接矩陣6.2.3鄰接鏈表6.2.2鄰接壓縮表6.2圖的抽象數據類型和表示方式鄰接矩陣法是用矩陣來表示各頂點之間的連接關系。對于有n個頂點的圖G=(V,E)，其鄰接矩陣A為n*n的方陣，元素A[i][j]（0≤i,j<n）定義為：其中，wij為邊(vi,vj)或<vi,vj>上的權。例如，圖6-5（a）中所示的有向圖G1和圖6-5（c）中所示的無向圖G2的鄰接矩陣分別如圖6-5（b）和圖6-5（d）所示。6.2.1鄰接矩陣6.2圖的抽象數據類型和表示方式6.2.1鄰接矩陣6.2圖的抽象數據類型和表示方式鄰接壓縮表可以看作是鄰接矩陣的一種壓縮表示形式。當圖中邊的數目遠遠小于結點數目的平方時，鄰接壓縮表占據的存儲空間會遠遠小于鄰接矩陣占據的存儲空間；但其缺點是邊的添加、刪除等操作較為復雜。鄰接壓縮表使用三個順序表來表示圖中頂點之間的連接關系和權，下面給出具體存儲形式。設圖中共有n個頂點{v0,v1,…,vn-1}，三個順序表分別為s、w和h。在s中依次記錄與頂點vi（i=0,1,…,n-1）相關聯(lián)的頂點，如圖6-6（a）所示，可知：對無向圖G，s中的元素數目兩倍于圖中邊的數目，且有（j=0,1,…,ji-1）；對有向圖G，s中的元素數目等于圖中邊的數目，且有（j=0,1,…,ji-1）。在w中依次記錄s中存儲的各條邊的權，其元素數目等于s中的元素數目，如圖6-6（b）所示。在h中依次記錄與頂點vi相關聯(lián)的頂點在s中的起始存儲位置，如圖6-6（c）所示，h中的元素數目等于圖中頂點的數目。6.2.2鄰接壓縮表6.2.2鄰接壓縮表6.2圖的抽象數據類型和表示方式6.2.2鄰接壓縮表6.2圖的抽象數據類型和表示方式鄰接鏈表可以看作是圖的一種鏈式存儲結構。在鄰接鏈表中，每個頂點中設置一個指向鏈表頭的指針，在鏈表中保存與該頂點相鄰接的頂點信息（包括頂點位置及兩個頂點形成的邊的權）。例如，圖6-5（a）中所示的有向圖G1和圖6-5（c）中所示的無向圖G2的鄰接鏈表分別如圖6-8（a）和圖6-8（b）所示。6.2.3鄰接鏈表6.2圖的抽象數據類型和表示方式6.3圖的遍歷圖的遍歷，是指從某一頂點出發(fā)按照某種規(guī)則依次訪問圖中的所有頂點，且每個頂點只被訪問一次。與樹相比，圖中頂點之間的關系更為復雜，因此圖的遍歷也要比樹的遍歷更復雜。根據搜索路徑的不同，圖的遍歷通常采有兩種方法：廣度優(yōu)先遍歷和深度優(yōu)先遍歷。下面分別介紹這兩種遍歷方法并給出它們的具體實現。6.3圖的遍歷6.3.1廣度優(yōu)先遍歷及其實現6.3.2深度優(yōu)先遍歷及其實現6.3圖的遍歷廣度優(yōu)先遍歷類似于樹的逐層遍歷，即先從某一個頂點開始訪問，然后訪問與該頂點相鄰接且未被訪問過的頂點集V1(G)，再訪問與V1(G)中頂點相鄰接且未被訪問過的頂點集V2(G)，重復該過程直至與初始頂點連通的所有頂點都被訪問完。對于非連通圖或非強連通圖，還要從某一個未被訪問的頂點開始重復上一過程，直至所有頂點訪問完畢。例如，對于圖6-5（a）所示按例6-1創(chuàng)建的有向圖，從頂點v0開始按照廣度優(yōu)先遍歷依次訪問到的頂點為：v0、v1、v2、v4、v3；對于圖6-5（c）所示按例6-1創(chuàng)建的無向圖，從頂點v0開始按照廣度優(yōu)先遍歷依次訪問到的頂點為：v0、v1、v2、v3、v4。6.3.1廣度優(yōu)先遍歷及其實現深度優(yōu)先遍歷類似于樹的先序遍歷，即從某一個頂點開始訪問，訪問后將該頂點去除得到若干子圖，對每個子圖再依次進行深度優(yōu)先遍歷。例如，對于圖6-5（a）所示按例6-1創(chuàng)建的有向圖，從頂點v0開始按照深度優(yōu)先遍歷依次訪問到的頂點為：v0、v1、v4、v2、v3；對于圖6-5（c）所示按例6-1創(chuàng)建的無向圖，從頂點v0開始按照深度優(yōu)先遍歷依次訪問到的頂點為：v0、v1、v4、v2、v3。對于圖的深度優(yōu)先遍歷，與樹的先序遍歷一樣，有遞歸和非遞歸兩種實現方式，其中非遞歸方式需要利用棧。6.3.2深度優(yōu)先遍歷及其實現6.3圖的遍歷6.4應用實例這里給出最小生成樹的求解算法和具體實現方法。6.4.1最小生成樹6.4.2最短路徑6.4應用實例1.Prim算法

對于有n個頂點的圖G=(V,E)，Prim算法從空樹T開始，按照以下規(guī)則將n個頂點和n-1條邊依次添加到樹中，形成最小生成樹：從某一頂點v0'開始，將該頂點作為樹的根結點加入到T中，使得T中的數據元素集合D={v0'}，數據元素關系集合R={}。對于一個頂點在集合D中、另一個頂點在集合V-D中的那些邊，找出權最小的一條邊，將該邊在集合V-D中的頂點vi'（i=1,2,…,n-1）加入到集合D中，并將頂點間關系<vj',vi'>（j<i）加入到關系集合R中。重復上一步驟直至集合D中包括圖G中所有n個頂點（此時關系集合R中包括n-1條邊）。若在某一步驟中找不到邊，則說明圖G是一個非連通圖或非強連通圖，在這種情況下不存在最小生成樹。6.4應用實例6.4.1最小生成樹6.4應用實例6.4.1最小生成樹2.Kruskal算法對于有n個頂點的圖G=(V,E)，Kruskal算法根據圖G中所有n個頂點生成一個包括n棵只有根結點的樹Ti（i=0,1,…,n-1）的森林F，并按照以下規(guī)則森林F中的樹合并，形成最小生成樹：從邊集合E中選取未被訪問過且具有最小權的邊，置該邊狀態(tài)為已訪問。判斷該邊的兩個頂點是否屬于不同的樹，若屬于不同的樹則使用該邊將兩棵樹合并為一棵；若屬于同一棵樹則不做任何處理。重復上一步驟直至森林F中只剩下一棵樹，該樹即是圖G的最小生成樹。若最后森林F中剩下不止一棵樹，則說明圖G是非連通圖或非強連通圖，在這種情況下不存在最小生成樹。6.4應用實例6.4.1最小生成樹6.4應用實例6.4.1最小生成樹1.從某個頂點到其余各頂點的最短路徑

圖中兩個頂點間的最短路徑計算問題，與從某個頂點到其余各頂點的最短路徑計算問題采用同樣的算法。只是前者在得到兩個頂點間的最短路徑后，不需再進行后繼計算。Dijkstra提出了一種按路徑長度遞增次序生成最短路徑的算法。對于有n個頂點的圖G=(V,E)，若要計算從頂點v0'到其余各頂點vi'（i=1,2,…,n-1）的最短路徑，則其計算步驟為：6.4.2最短路徑6.4應用實例令集合S為已計算出最短路徑的頂點集合（初始時S={v0'}），w(vj',vi')表示從頂點vj'到頂點vi'的邊的權（這里為方便計算，令w(vi',vi')=0），D(v0',vi')表示當前計算得到的從頂點v0'到頂點vi'的最短路徑長度（初始D(v0',vi')=w(v0',vi')）。將頂點加入到集合S中，并將從頂點v0‘到頂點vm’的最短路徑記錄下來。若仍有頂點沒有加到集合S中，則對集合V-S中的頂點vi‘計算。重復上一步驟直至圖中所有頂點都加到集合S中。6.4.2最短路徑6.4應用實例例如，對于圖6-4（b）中所示的有向圖，若計算從頂點v0到其余各頂點的最短路徑，則其計算過程如圖6-11所示。Dijkstra算法的原理可理解為：從某一頂點v0'到另一頂點vi'的最短路徑或者是(v0',vi')、或者是(v0',vi1',vi2',…,vij',vi')，若為后者則其中(v0',vi1',vi2',…,vij',vj')必然為從頂點v0'到頂點vj'的最短路徑。因此，根據已計算出的那些頂點的最短路徑，可以依次得到其他頂點的最短路徑。6.4.2最短路徑6.4應用實例6.4.2最短路徑6.4應用實例2.每一對頂點之間的最短路徑若要計算圖中每一對頂點之間的最短路徑，可以重復使用Dijkstra算法依次計算