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

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

6.1圖的基本概念

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

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

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

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

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

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

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

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

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

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

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

V2，E1

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

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

(6-1)

在一個(gè)圖中，如果圖的邊或弧具有一個(gè)與它相關(guān)的數(shù)時(shí)，這個(gè)數(shù)就稱為該邊或弧的權(quán)。權(quán)常用來表示一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。如果圖中的每條邊都具有權(quán)時(shí)，這個(gè)帶權(quán)圖被稱為網(wǎng)絡(luò)，簡稱為網(wǎng)。圖6-4給出了一個(gè)網(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中，頂點(diǎn)1到頂點(diǎn)4的路徑長度為8。

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

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

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

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

6.2圖的存儲(chǔ)方法

6.2.1鄰接矩陣

鄰接矩陣是表示圖中頂點(diǎn)之間相鄰關(guān)系的矩陣。對一個(gè)有n個(gè)頂點(diǎn)的圖G，其鄰接矩陣是一個(gè)n×n階的方陣，矩陣中的每一行和每一列都對應(yīng)一個(gè)頂點(diǎn)。矩陣中的元素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鄰接表

鄰接表存儲(chǔ)方法是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。在這種方法中，因?yàn)橹豢紤]非零元素，所以當(dāng)圖中的頂點(diǎn)很多而邊又很少時(shí)，可以節(jié)省存儲(chǔ)空間。圖6-7鄰接表和逆鄰接表示例

6.3圖的遍歷

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

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

因?yàn)樗阉鱪個(gè)頂點(diǎn)的所有鄰接點(diǎn)需要對各邊表結(jié)點(diǎn)掃描一遍，而邊表結(jié)點(diǎn)的數(shù)目為2e，所以算法的時(shí)間復(fù)雜度為O(2e+n)，空間復(fù)雜度為O(n)。

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

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

6.4生成樹和最小生成樹

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

1.?Prim算法

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

}，TE={

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

})；然后，從u

U，v

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

U，v

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

(6-4)

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

(1)將頂點(diǎn)值2寫入T[i].fromvex，并將其余頂點(diǎn)值寫入相應(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的值，則進(jìn)行替換；否則保持不變。圖6-13一個(gè)網(wǎng)絡(luò)及其鄰接矩陣圖6-14T數(shù)組變化情況及最小生成樹

2.?Kruskal算法

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

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

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

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

6.5最短路徑

6.5.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

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

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

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

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

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

AOV網(wǎng)中的有向邊表示了活動(dòng)之間的制約關(guān)系。例如，計(jì)算機(jī)軟件專業(yè)的學(xué)生必須學(xué)完一系列的課程才能畢業(yè)，其中一些課程是基礎(chǔ)課，學(xué)習(xí)基礎(chǔ)課程無須先學(xué)習(xí)其他課程；而另一些課程的學(xué)習(xí)，則必須在完成其他基礎(chǔ)先修課的學(xué)習(xí)之后才能進(jìn)行學(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)鍵路徑

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