《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第6章

第6章圖6.1圖的基本概念6.2圖的存儲方法6.3圖的遍歷6.4生成樹和最小生成樹6.5最短路徑6.6拓?fù)渑判?.7關(guān)鍵路徑

6.1圖的基本概念

圖(G)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由兩個集合V(G)和E(G)組成，形式上記為G=(V，E)。其中，V(G)是頂點(Vertex)的非空有限集合；E(G)是V(G)中任意兩個頂點之間的關(guān)系集合，又稱為邊(Edge)的有限集合。當(dāng)G中的每條邊有方向時，則稱G為有向圖。有向邊通常用由兩個頂點組成的有序?qū)肀硎?，記為〈起始頂點，終止頂點〉。有向邊又稱為弧，因此，弧的起始頂點就稱為弧尾；終止頂點稱為弧頭。例如，圖6-1(a)給出了一個有向圖的示例，該圖的頂點集和邊集分別為

V(G1)={A,B,C}

E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}圖6-1有向圖和無向圖示例若G中的每條邊是無方向的，則稱G為無向圖。這時兩個頂點之間最多只存在一條邊。無向邊用兩個頂點組成的無序?qū)Ρ硎?，記?頂點1，頂點2)。圖6-1(b)給出了一個無向圖的示例，該圖的頂點集和邊集分別為

V(G2)={A,B,C}

E(G2)={(A,B),(B,C),(C,A)}?

={(B,A),(C,B),(A,C)}

在下面討論的圖中，我們不考慮頂點到其自身的邊，也不允許一條邊在圖中重復(fù)出現(xiàn)，如圖6-2所示。圖6-2本章中不考慮的圖邊示例在這兩條假設(shè)條件的約束下，圖的邊和頂點之間存在以下的關(guān)系：

(1)一個無向圖，它的頂點數(shù)n和邊數(shù)e滿足0≤e≤n(n-1)

/2的關(guān)系。如果e=n(n-1)/2，則該無向圖稱為完全無向圖。

(2)一個有向圖，它的頂點數(shù)n和邊數(shù)e滿足0≤e≤n(n-1)的關(guān)系。如果e=n(n-1)，則稱該有向圖為完全有向圖。

(3)若圖中的頂點為n，邊數(shù)為e，如果e<nlbn，則該圖為稀疏圖；否則為稠密圖。如果有兩個同類型的圖G1=(V1,E1)和G2=(V2,E2)，存在關(guān)系V1

V2，E1

E2，則稱G1是G2的子圖。圖6-3給出了G1和G2的子圖示例。圖6-3子圖示例如果圖G中有n個頂點，e條邊，且每個頂點的度為D(vi)

(1≤i≤n)，則存在以下關(guān)系：

(6-1)

在一個圖中，如果圖的邊或弧具有一個與它相關(guān)的數(shù)時，這個數(shù)就稱為該邊或弧的權(quán)。權(quán)常用來表示一個頂點到另一個頂點的距離或耗費。如果圖中的每條邊都具有權(quán)時，這個帶權(quán)圖被稱為網(wǎng)絡(luò)，簡稱為網(wǎng)。圖6-4給出了一個網(wǎng)絡(luò)示例。圖6-4網(wǎng)絡(luò)示例例如，在圖6-1(b)中，(A，B，C)是一條路徑。而在圖6-1(a)中，(A，C，B)就不是一條路徑。對于無權(quán)圖，沿路徑所經(jīng)過的邊數(shù)稱為該路徑的長度。而對于有權(quán)圖，則取沿路徑各邊的權(quán)之和作為此路徑的長度。在圖6-4中，頂點1到頂點4的路徑長度為8。

若路徑中的頂點不重復(fù)出現(xiàn)，則這條路徑被稱為簡單路徑。起點和終點相同并且路徑長度不小于2的簡單路徑，被稱為簡單回路或者簡單環(huán)。例如，圖6-1(b)所示無向圖中，頂點序列(A，B，C)是一條簡單路徑，而(A，B，C，A)則是一個簡單環(huán)。在一個有向圖中，若存在一個頂點v，從該頂點有路徑可到達圖中其他的所有頂點，則稱這個有向圖為有根圖；v稱為該圖的根。例如，圖6-1(a)就是一個有根圖，該圖的根是A和B。

在無向圖G中，若頂點vi和vj(i≠j)有路徑相通，則稱vi和vj是連通的。如果v(G)中的任意兩個頂點都連通，則稱G是連通圖；否則為非連通圖。例如圖6-1(b)就是一個連通圖。

無向圖G中的極大連通子圖稱為G的連通分量。對任何連通圖而言，連通分量就是其自身；非連通圖可有多個連通分量。

圖6-5給出了一個無向圖和它的兩個連通分量。圖6-5無向圖及其連通分量

6.2圖的存儲方法

6.2.1鄰接矩陣

鄰接矩陣是表示圖中頂點之間相鄰關(guān)系的矩陣。對一個有n個頂點的圖G，其鄰接矩陣是一個n×n階的方陣，矩陣中的每一行和每一列都對應(yīng)一個頂點。矩陣中的元素A[i,j]可按以下規(guī)則取值：

(6-2)圖6-6(a)和(b)所示有向圖G1和無向圖G2的鄰接矩陣分別為A1和A2：圖6-6有向圖G1和無向圖G2示例對于網(wǎng)絡(luò)，鄰接矩陣元素A[i,j]可按以下規(guī)則取值：

(6-3)圖6-4所示網(wǎng)絡(luò)的鄰接矩陣為6.2.2鄰接表

鄰接表存儲方法是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲方法。在這種方法中，因為只考慮非零元素，所以當(dāng)圖中的頂點很多而邊又很少時，可以節(jié)省存儲空間。圖6-7鄰接表和逆鄰接表示例

6.3圖的遍歷

6.3.1深度優(yōu)先搜索遍歷

圖的深度優(yōu)先搜索遍歷(DFS)類似于樹的先序遍歷，是樹先序遍歷的推廣。圖6-8深度優(yōu)先搜索遍歷過程當(dāng)圖6-8采用圖6-9所示的鄰接表表示時，按以上算法進行深度優(yōu)先搜索遍歷得到的序列為A，B，C，E，D。

因為搜索n個頂點的所有鄰接點需要對各邊表結(jié)點掃描一遍，而邊表結(jié)點的數(shù)目為2e，所以算法的時間復(fù)雜度為O(2e+n)，空間復(fù)雜度為O(n)。

在使用鄰接表作為存儲結(jié)構(gòu)時，由于圖的鄰接表表示不是唯一的，因此DFSL算法得到的DFS序列也不是唯一的，它取決于鄰接表中邊表結(jié)點的鏈接次序。圖6-9鄰接表的一種表示6.3.2廣度優(yōu)先搜索遍歷

圖的廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷。這種方法的遍歷過程是：在假設(shè)初始狀態(tài)是圖中所有頂點都未被訪問的條件下，從圖中某一個頂點vi出發(fā)，訪問vi；然后依次訪問vi的鄰接點vj；在所有的vj都被訪問之后，再訪問vj的鄰接點vk；……直到圖中所有和初始出發(fā)點vi有路徑相通的頂點都被訪問為止。若該圖是非連通的，則選擇一個未曾被訪問的頂點作為起始點，重復(fù)以上過程，直到圖中所有頂點都被訪問為止。

6.4生成樹和最小生成樹

在圖論中，樹是指一個無回路存在的連通圖，而一個連通圖G的生成樹指的是：一個包含了G的所有頂點的樹。對于一個有n個頂點的連通圖G，其生成樹包含了n-1條邊，從而生成樹是G的一個極小連通的子圖。所謂極小是指該子圖具有連通所需的最小邊數(shù)，若去掉其中的一條邊，該子圖就變成了非連通圖；若任意增加一條邊，該子圖就有回路產(chǎn)生。圖6-10生成樹的示例圖6-11含有(u,v)的回路

1.?Prim算法

用Prim算法構(gòu)造最小生成樹的過程是：設(shè)G(V,E)是有n個頂點的連通網(wǎng)絡(luò)，T=(U，TE)是要構(gòu)造的生成樹，初始時U={

}，TE={

}。首先，從V中取出一個頂點u0放入生成樹的頂點集U中作為第一個頂點，此時T=({u0}，{

})；然后，從u

U，v

V-U的邊(u，v)中找一條代價最小的邊(u*,v*)放入TE中，并將v*放入U中,此時T=({u0,v*}，{(u0，v*)})；繼續(xù)從u

U，v

V-U的邊(u,v)中找一條代價最小的邊(u*,v*)放入TE中，并將v*放入U中，直到U=V為止。這時T的TE中必有n-1條邊，構(gòu)成所要構(gòu)造的最小生成樹。圖6-12Prim算法構(gòu)造最小生成樹的過程在以上算法中，構(gòu)造第一個頂點所需的時間復(fù)雜度是O(n)，求k條邊的時間復(fù)雜度大約為

(6-4)

其中，O(1)表示某個正常數(shù)C。所以式(6-4)的時間復(fù)雜度是O(n2)。下面結(jié)合圖6-13所示的例子再來觀察以上算法的工作過程。設(shè)選定的第一個頂點為2，其工作過程如下：

(1)將頂點值2寫入T[i].fromvex，并將其余頂點值寫入相應(yīng)的T[i].endvex中；然后從dist矩陣中取出第2行寫入相應(yīng)的T[i].length中，得到圖6-14(a)。

(2)在圖6-14(a)中找出最小權(quán)值的邊(2，1)，將其交換到下標(biāo)值為0的單元中；然后從dist陣中取出第1行的權(quán)值與相應(yīng)的T[i].length的值相比較。若取出的權(quán)值小于相應(yīng)T[i].length的值，則進行替換；否則保持不變。圖6-13一個網(wǎng)絡(luò)及其鄰接矩陣圖6-14T數(shù)組變化情況及最小生成樹

2.?Kruskal算法

Kruskal算法是從另外一條途徑來求網(wǎng)絡(luò)的最小生成樹。

用Kruskal算法構(gòu)造最小生成樹的過程是：設(shè)G=(V，E)是一個有n個頂點的連通圖，令最小生成樹的初值狀態(tài)為只有n個頂點而無任何邊的非連通圖T=(V，{

})，此時圖中每個頂點自成一個連通分量。按照權(quán)值遞增的順序依次選擇E中的邊，若該邊依附于T中兩個不同的連通分量，則將此邊加入TE中；否則舍去此邊而選擇下一條代價最小的邊，直到T中所有頂點都在同一個連通分量上為止。這時的T，便是G的一棵最小生成樹。

對于圖6-13所示的網(wǎng)絡(luò)，按Kruskal算法構(gòu)造最小生成樹的過程如圖6-15所示。圖6-15Kruskal算法構(gòu)造最小生成樹的過程

6.5最短路徑

6.5.1從某個源點到其余各頂點的最短路徑

對于給定的有向網(wǎng)絡(luò)G?=?(V,E)及源點v，計算從v到G的其余各頂點的最短路徑。

例如，已知有向網(wǎng)絡(luò)G如圖6-16所示，假定以頂點F為源點，則源點F到其余各頂點A、B、C、D、E的最短路徑如表6-1所示。圖6-16有向網(wǎng)絡(luò)G對圖6-16所示的有向網(wǎng)絡(luò)按以上算法思想處理，所求得的從源點F到其余頂點的最短路徑的過程如圖6-17所示。圖6-17Dijkstra算法求最短路徑示例6.5.2每一對頂點之間的最短路徑

在一個有n個頂點的有向網(wǎng)絡(luò)G=(V，E)中，求每一對頂點之間的最短路徑?？梢砸来伟延邢蚓W(wǎng)絡(luò)G的每個頂點作為源點，重復(fù)執(zhí)行Dijkstra算法n次，從而得到每對頂點之間的最短路徑。這種方法的時間復(fù)雜度為O(n3)。弗洛伊德(Floyd)于1962年提出了解決這個問題的另外一種算法，它在形式上比較簡單，易于理解，而時間復(fù)雜度同樣為O(n3)。圖6-18Floyd算法選代過程中矩陣A和path的變化情況

6.6拓?fù)渑判?/p>

無論是一項工程的進行，還是一個產(chǎn)品的生產(chǎn)或一個專業(yè)課程的學(xué)習(xí)，都是由許多按一定次序進行的活動來構(gòu)成的。這些活動既可以是一個工程中的子工程，一個產(chǎn)品生產(chǎn)中的部件生產(chǎn)，也可以是課程學(xué)習(xí)中的一門課程。對于這些按一定順序進行的活動，可以用有向圖的頂點表示活動，頂點之間的有向邊表示活動間的先后關(guān)系，這種有向圖稱為頂點表示活動網(wǎng)絡(luò)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)。AOV網(wǎng)中的頂點也可帶有權(quán)值，用于表示一項活動完成所需要的時間。

AOV網(wǎng)中的有向邊表示了活動之間的制約關(guān)系。例如，計算機軟件專業(yè)的學(xué)生必須學(xué)完一系列的課程才能畢業(yè)，其中一些課程是基礎(chǔ)課，學(xué)習(xí)基礎(chǔ)課程無須先學(xué)習(xí)其他課程；而另一些課程的學(xué)習(xí)，則必須在完成其他基礎(chǔ)先修課的學(xué)習(xí)之后才能進行學(xué)習(xí)。這些課程和課程之間的關(guān)系如表6-3所示。它們也可以用圖6-19所示的AOV網(wǎng)表示，其中有向邊

<Ci，Cj>表示了課程Ci是課程Cj的先修課程。圖6-19表示課程先后關(guān)系的AOV網(wǎng)圖6-20AOV網(wǎng)拓?fù)渑判蜻^程圖6-21AOV網(wǎng)G1及其鄰接表圖6-22鏈棧的初始邏輯狀態(tài)圖圖6-23排序過程中入度域變化示例

6.7關(guān)鍵路徑

因為一項工程只有一個開始點和一個結(jié)束點，所以AOE網(wǎng)絡(luò)中只有一個入度為0的頂點(稱做源點)表示開始和一個出度為0的頂點(稱做匯點)表示結(jié)束。同時，AOE網(wǎng)絡(luò)應(yīng)該是不存在回路并相對源點連通的網(wǎng)絡(luò)。圖6-24給出了一個AOE網(wǎng)絡(luò)的例子，它包括了7個事件和10個活動。其中，頂點v1表示整個工程開始；頂點v7表示整個工程結(jié)束；邊<v1，v2>，<v1，v3>，…，<v6，v7>分別表示一個活動，并分別用a1，a2，