計算機軟件技術(shù)基礎(chǔ)教程課件-11第十一章-圖

第十一章圖11.1圖的基本概念圖(G)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由兩個集合V(G)和E(G)組成，形式上記為G=(V,E),其中V(G)是頂點(Vertex)的非空有限集合，而E(G)是V(G)中任意兩個頂點之間的關(guān)系集合，又稱為邊(Edge)的有限集合。11.1圖的基本概念當(dāng)G中的每條邊有方向時，則稱G為有向圖。有向邊通常使用由兩個頂點組成的有序?qū)肀硎?，記為：〈起始頂點，終止頂點〉。有向邊又稱為弧，因此弧的起始頂點就稱為弧尾，終止頂點稱為弧頭。例如圖11.1(a)給出了一個有向圖的示例，該圖的頂點集和邊集分別為V(G1)={A,B,C}E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}11.1圖的基本概念圖11.1有向圖和無向圖示例11.1圖的基本概念若G中的每條邊是無方向的，則稱G為無向圖。這時兩個頂點之間最多只存在一條邊。無向圖用兩個頂點組成的無序?qū)Ρ硎荆洖椋?頂點1，頂點2)。圖11.1(b)給出了一個無向圖的示例。該圖的頂點集和邊集分別為：V(G2)={A,B,C}E(G2)={(A,B),(B,C),(C,A)}={(B,A),(C,B),(A,C)}在下面的討論中，我們不考慮頂點到其自身的邊，也不允許一條邊在圖中重復(fù)出現(xiàn)，如圖11.2所示。11.1圖的基本概念圖11.2本章中不考慮的圖例11.1圖的基本概念

(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，則該圖為稀疏圖；否則為稠密圖。11.1圖的基本概念如果兩個同類型的圖G1=(V1,E1)和G2＝(V2,E2)存在關(guān)系V1V2,E1E2,則稱G1是G2的子圖。圖11.3給出了G1和G2的子圖的示例。圖11.3子圖示例11.1圖的基本概念如果圖G中有n個頂點，e條邊，且每個頂點的度為D(vi)

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

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

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

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

無向圖G中的極大連通子圖稱為G的連通分量。對任何連通圖而言，連通分量就是其自身；非連通圖可有多個連通分量。圖11-5給出了一個無向圖和它的兩個連通分量。11.1圖的基本概念圖11.5無向圖及其連通分量11.2圖的存儲方法由于圖的結(jié)構(gòu)復(fù)雜，任意兩個頂點之間都可能存在聯(lián)系，所以無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，但仍可以借助一個二維數(shù)組中各單元的數(shù)據(jù)取值或用多重鏈表來表示元素間的關(guān)系。無論采用什么存儲方法，都需要存儲圖中各頂點本身的信息和存儲頂點與頂點之間的關(guān)系。圖的存儲方法很多，常用的有鄰接矩陣存儲方法、鄰接表存儲方法、十字鏈表存儲方法和多重鄰接表存儲方法。至于具體選擇哪種存儲方法，取決于具體的應(yīng)用和所要施加的運算。這里僅介紹鄰接矩陣存儲方法和鄰接表存儲方法。11.2圖的存儲方法11.2.1鄰接矩陣存儲方法鄰接矩陣是表示圖中頂點之間相鄰關(guān)系的矩陣。對一個有n個頂點的圖G，其鄰接矩陣是一個n×n階的方陣，矩陣中的每一行和每一列都對應(yīng)一個頂點。矩陣中的元素A[i,j]可按以下規(guī)則取值：

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

11.2圖的存儲方法11.2.1鄰接矩陣存儲方法圖11-4所示網(wǎng)絡(luò)的鄰接矩陣為：

11.2圖的存儲方法11.2.2鄰接表存儲方法

鄰接表存儲方法是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲方法。在這種方法中，因為只考慮非零元素，所以當(dāng)圖中的頂點很多而邊又很少時，可以節(jié)省存儲空間。11.2圖的存儲方法11.2.2鄰接表存儲方法圖11.7鄰接表和逆鄰接表示例11.3圖的遍歷11.3.1深度優(yōu)先搜索遍歷

圖的深度優(yōu)先搜索遍歷(DFS)類似于樹的先序遍歷，是樹先序遍歷的推廣。11.3圖的遍歷11.3.1深度優(yōu)先搜索遍歷圖11.8深度優(yōu)先搜索遍歷過程11.3圖的遍歷11.3.1深度優(yōu)先搜索遍歷當(dāng)圖11-8采用圖11-9所示的鄰接表表示時，按以上算法進(jìn)行深度優(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é)點的鏈接次序。11.3圖的遍歷11.3.1深度優(yōu)先搜索遍歷圖11.9鄰接表的一種表示11.3圖的遍歷11.3.2廣度優(yōu)先搜索遍歷

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

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

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)造的最小生成樹。11.4生成樹和最小生成樹在以上算法中，構(gòu)造第一個頂點所需的時間復(fù)雜度是O(n)，求k條邊的時間復(fù)雜度大約為

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

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

(2)在圖11.13(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)行替換；否則保持不變。11.4生成樹和最小生成樹圖11.12一個網(wǎng)絡(luò)及其鄰接矩陣11.4生成樹和最小生成樹(a)初始化后的T數(shù)組

(b)找出最短邊(2,1)調(diào)整后的T數(shù)組

(c)找出最短邊(2,3)并調(diào)整后(d)找出最短邊(1,0)并調(diào)整后(e)找出最短邊(1,5)并調(diào)整后(f)最小生成樹圖11.13T數(shù)組變化情況及最小生成樹11.4生成樹和最小生成樹

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的一棵最小生成樹。對于圖11.12所示的網(wǎng)絡(luò)，按Kruskal算法構(gòu)造最小生成樹的過程如圖11.14所示。11.4生成樹和最小生成樹圖11.14Kruskal算法構(gòu)造最小生成樹的過程11.5最短路徑一個實際的交通網(wǎng)絡(luò)在計算機中可用圖的結(jié)構(gòu)來表示。在這類問題中經(jīng)?？紤]的問題有兩個：一是兩個頂點之間是否存在路徑；二是在有多條路徑的條件下，哪條路徑最短。由于交通網(wǎng)絡(luò)中的運輸路線往往是有方向性的，因此將以有向網(wǎng)絡(luò)來進(jìn)行討論，而無向網(wǎng)絡(luò)的情況與此相似。在討論中，習(xí)慣上稱路徑的開始點為源點(Source)，路徑的最后一個頂點為終點(Destination)，而最短路徑意味著沿路徑的各邊權(quán)值之和最小。在求最短路徑時，為方便起見，規(guī)定鄰接矩陣中某一頂點到自身的權(quán)值為0，即當(dāng)i=j時，dist[i][j]=0。最短路徑問題的研究分為兩種情況：一是從某個源點到其余各頂點的最短路徑；二是每一對頂點之間的最短路徑。11.5最短路徑11.5.1從某個源點到其余各頂點的最短路徑迪杰斯特拉(Dijkstra)通過對大量的圖中某個源點到其余頂點的最短路徑的頂點構(gòu)成集合和路徑長度之間關(guān)系的研究發(fā)現(xiàn)：若按長度遞增的次序來產(chǎn)生源點到其余頂點的最短路徑，則當(dāng)前正要生成的最短路徑除終點外，其余頂點的最短路徑已生成，即設(shè)A為源點，U為已求得的最短路徑的終點的集合?(初態(tài)時為空集)，則下一條長度較長的最短路徑?(設(shè)它的終點為X)?或者是弧(A,X)或者是中間只經(jīng)過U集合中的頂點，最后到達(dá)X的路徑。例如在圖11.15中，要生成從F點到其他頂點的最短路徑。首先應(yīng)找到最短的路徑F→B，然后找到最短的路徑F→B→C。這里除終點C以外，其余頂點的最短路徑F→B已生成。11.5最短路徑11.5.1從某個源點到其余各頂點的最短路徑迪杰斯特拉提出的按路徑長度遞增次序來產(chǎn)生源點到各頂點的最短路徑的算法思想是：對有n個頂點的有向連通網(wǎng)絡(luò)G=(V,E)，首先從V中取出源點u0放入最短路徑頂點集合U中，這時的最短路徑網(wǎng)絡(luò)S=({u0},{

});然后從u

U和v

V－U中找一條代價最小的邊(u*,v*)加入到S中去，此時S=({u0,v*},{(u0,v*)})。每往U中增加一個頂點，則要對V－U中的各頂點的權(quán)值進(jìn)行一次修正。若加進(jìn)v*作為中間頂點，使得從u0到其他屬于V－U的頂點vi的路徑不加v*時最短，則修改u0到vi的權(quán)值，即以(u0,v*)的權(quán)值加上(v*,vi)的權(quán)值來代替原(u0,vi)的權(quán)值，否則不修改u0到vi的權(quán)值。接著再從權(quán)值修正后的V－U中選擇最短的邊加入S中，如此反復(fù)，直到U=V為止。11.5最短路徑11.5.1從某個源點到其余各頂點的最短路徑圖11.15有向網(wǎng)絡(luò)G和F到其他頂點的最短距離11.5最短路徑圖11.16Dijkstra算法求最短路徑示例11.5最短路徑11.5最短路徑11.5.2每一對頂點之間的最短路徑求一個有n個頂點的有向網(wǎng)絡(luò)G=(V,E)中的每一對頂點之間的最短路徑，可以依次把有向網(wǎng)絡(luò)的每個頂點作為源點，重復(fù)執(zhí)行n次Dijkstra算法，從而得到每對頂點之間的最短路徑。這種方法的時間復(fù)雜度為O(n3)。弗洛伊德(Floyd)于1962年提出了解決這一問題的另一種算法。它形式比較簡單，易于理解，而時間復(fù)雜度同樣為O(n3)。11.5最短路徑11.5.2每一對頂點之間的最短路徑11.6拓?fù)渑判驘o論一項工程的進(jìn)行、一個產(chǎn)品的生產(chǎn)或一個專業(yè)的課程學(xué)習(xí)，都是由許多按一定次序進(jìn)行的活動來構(gòu)成的。這些活動可以是一個工程中的子工程、一個產(chǎn)品生產(chǎn)中的部件生產(chǎn)或課程學(xué)習(xí)中的一門課程。這些按一定順序進(jìn)行的活動，可以使用頂點表示活動、頂點之間的有向邊表示活動間的先后關(guān)系的有向圖來表示，這種有向圖稱為頂點表示活動網(wǎng)絡(luò)(ActivityOnVertexnetwork，簡稱AOV網(wǎng))。AOV網(wǎng)中的頂點也可帶有權(quán)值，表示一項活動完成所需要的時間。11.6拓?fù)渑判駻OV網(wǎng)中的有向邊表示了活動之間的制約關(guān)系。例如，計算機軟件專業(yè)的學(xué)生必須學(xué)完一系列的課程才能畢業(yè)，其中一些課程是基礎(chǔ)課，無須先修其他課程便可學(xué)習(xí)；而另一些課程則必須學(xué)完其他的基礎(chǔ)先修課后才能進(jìn)行學(xué)習(xí)。這些課程和課程之間的關(guān)系如表11.3所示。它們也可以用圖11.17的AOV網(wǎng)表示，這里有向邊＜Ci,Cj＞表示了課程Ci是課程Cj的先修課程。當(dāng)限制各個活動只能串行進(jìn)行時，如果可以將AOV網(wǎng)中的所有頂點排列成一個線性序列vi1,vi2,…,vin，并且這個序列同時滿足關(guān)系：若在AOV網(wǎng)中從頂點vi到頂點vj存在一條路徑，則在線性序列中vi必在vj之前，我們就稱這個線性序列為拓?fù)湫蛄?。把對AOV網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判颉?1.6拓?fù)渑判驁D11.17表示課程先后關(guān)系的AOV網(wǎng)11.6拓?fù)渑判?1.6拓?fù)渑判?1)從網(wǎng)中選擇一個入度為0的頂點并且輸出它。(2)從網(wǎng)中刪除此頂點及所有由它發(fā)出的邊。(3)重復(fù)上述兩步，直到網(wǎng)中再沒有入度為0的頂點為止。以上的操作會產(chǎn)生兩種結(jié)果：一種是網(wǎng)中的全部頂點都被輸出，整個拓?fù)渑判蛲瓿?；另一種是網(wǎng)中頂點未被全部輸出，剩余的頂點的入度均不為0，則說明網(wǎng)中存在有向環(huán)。用以上操作對圖11.17的AOV網(wǎng)拓?fù)渑判虻倪^程如圖11.18所示。這里得到了一種拓?fù)湫蛄蠧1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。11.6拓?fù)渑判驁D11.18AOV網(wǎng)拓?fù)渑判蜻^程11.6拓?fù)渑判驁D11.19AOV網(wǎng)G1及其鄰接表11.6拓?fù)渑判驁D11.20排序過程中入度域變化示例11.7關(guān)鍵路徑因為一項工程只有一個開始點和一個結(jié)束點，所以AOE網(wǎng)絡(luò)中只有一個入度為0的頂點（稱作源點）表示開始和一個出度為0