數(shù)據(jù)結(jié)構(gòu)第18講-最小生成樹與拓?fù)渑判?C

1、第7章 圖7.1 圖的定義和術(shù)語7.2 圖的存儲結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問題7.5 有向無環(huán)圖及其應(yīng)用7.6 最短路徑7.4 圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹3）普里姆算法4）克魯斯卡爾算法例：圖及其生成樹65665513420 對于帶權(quán)的連通圖(連通網(wǎng))G，其生成樹也是帶權(quán)的，將權(quán)最小的生成樹稱為最小生成樹。 連通網(wǎng)最小生成樹的意義？ 如何構(gòu)造最小生成樹？ 對于帶權(quán)的連通圖(連通網(wǎng))G，其生成樹也是帶權(quán)的，將權(quán)最小的生成樹稱為最小生成樹。 連通網(wǎng)最小生成樹的意義？ 如何構(gòu)造最小生成樹？最小生成樹的MST性質(zhì)： 假設(shè) N =（V,E）是一個連通網(wǎng)，U是頂點

2、集 V 的一個非空子集。若（u,v）是一條具有最小權(quán)值（代價）的邊，其中 u U，vV-U，則必存在一棵包含邊（u,v）的最小生成樹。656655134207.4 圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹3）普里姆算法4）克魯斯卡爾算法3.普里姆（Prim）算法基本思想：(1)假設(shè) G=(V,E) 是一個具有 n 個頂點的連通網(wǎng)絡(luò)，T=(U，TE)是 G 的最小生成樹，其中 U 是 T 的頂點集，TE 是 T 的邊集，U 和 TE 的初值均為空；(2)從 V 中任取一個頂點（假定為 V1），將此頂點并入 U中，此時最小生成樹頂點集 U=V1；(3)從那些其中一個端點已在 U 中

3、，另一端點仍在 U 外的所有邊中，找一條最短（即權(quán)值最?。┑倪?，設(shè)該邊為(Vi,Vj)，其中 ViU，VjV-U，并把該邊和頂點 Vj分別并入 T 的邊集 TE 和頂點集 U；(4)如此進(jìn)行下去，每次往生成樹里并入一個頂點和一條邊，直到 n-1 次后，把所有 n 個頂點都并入生成樹 T 的頂點集 U 中，此時 U=V，TE中包含有（n-1）條邊；這樣，T 就是最后得到的最小生成樹。 實現(xiàn)該算法需附設(shè)一個輔助數(shù)組closedge，以記錄從 U 到 V-U 具有最小代價的邊。對每個頂點 viV-U，在輔助數(shù)組中存在一個相應(yīng)分量closedgei-1(下標(biāo)從0開始)，它包括兩個域。其中：lowcos

4、t存儲該邊上的權(quán)。顯然， closedgei-1.lowcost =Mincost(u，vi)|uU 即vi到已生成子樹的最短距離等于到U中所有頂點中的最小邊的權(quán)值。 vex域存儲該邊依附的在U中的頂點。例：求下圖最小生成樹。假設(shè)開始頂點就選為頂點1， 故有U=1，V-U=2，3，4，5，6 (a )無向網(wǎng)64V1V2V4V36213V55V6556(b) U=1 V-U=2,3,4,5,612345665153124561456(c) U=1,3 V-U=2,4,5,631 2456 4215 6 (d) U=1,3,6 V-U=2,4,531245642156(e) U=1,3,6,4 V

5、-U=2,5(f) U=1,3,6,4,2 V-U=512435642153(g) U=1,3,6,4,2,5 V-U= 54213124356 (a )無向網(wǎng)64V1V2V4V36213V55V6556基于鄰接矩陣的普里姆算法 struct VertaxType adjvex; /頂點編號 VRType lowcost; / =Mincost(u,vi|uU) closedgeMAX_VERTEX_NUM;Void MiniSpanTree_PRIM(MGraph G, VertexType u) k = LocateVex ( G, u ); / 頂點u為構(gòu)造生成樹的起始點,返回頂點u在圖

6、中的位置 for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej= u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu邊k，j的權(quán)值 for (i=1; iG.vexnum; +i) /在其余頂點中選擇 k = minimum(closedge); / 求出T的下一結(jié)點(k) printf(closedgek.adjvex, G.vexsk); /輸出生成樹的邊 closedgek.lowcost = 0; / 第k頂點并入U集 for (j=0; jG.vexnum; +j) if (G.

7、arcskj.adj closedgej.lowcost) / 新頂點并入U后重新選擇最小邊 closedgej=G.vexsk,G.arcskj.adj; / for / MiniSpanTree_PRIMT(n)=O(n2)4.克魯斯卡爾（Kruskal）算法基本思想 為使生成樹上總的權(quán)值最小，應(yīng)使每條邊上的權(quán)值盡可能小，自然應(yīng)從權(quán)值最小的邊選起，直至選出n-1條權(quán)值最小的邊為止，同時這n-1條邊必須不構(gòu)成回路。因此，并非每一條當(dāng)前權(quán)值最小的邊都可選。4.克魯斯卡爾（Kruskal）算法具體做法 先構(gòu)造一個只含 n個頂點的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中去，并使森林中不

8、產(chǎn)生回路，直至森林變成一棵樹為止。例：對下圖中無向網(wǎng)，用克魯斯卡爾算法求最小生成樹的過程。 22156134 無向網(wǎng)6462135556465312345一般來講： 普里姆算法的時間復(fù)雜度為 O(n2)，適于稠密圖； 克魯斯卡爾算法需對 e 條邊按權(quán)值進(jìn)行排序，其時間復(fù)雜度為 O(eloge)，適于稀疏圖。第7章 圖7.1 圖的定義和術(shù)語7.2 圖的存儲結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問題7.5 有向無環(huán)圖及其應(yīng)用7.6 最短路徑7.5 有向無環(huán)圖及其應(yīng)用 有向無環(huán)圖(directed acycline graph)簡稱DAG圖，是描述一項工程或系統(tǒng)的進(jìn)行過程的有效工具。 對整個工程和系

9、統(tǒng)，人們關(guān)心的是兩個方面的問題：一是工程能否順利進(jìn)行；二是估算整個工程完成所必須的最短時間。 有向無環(huán)圖的應(yīng)用：拓?fù)渑判蜿P(guān)鍵路徑 在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關(guān)系： 先后關(guān)系，即必須在一子項目完成后，才能開始實施另一個子項目； 子項目之間無次序要求，即兩個子項目可以同時進(jìn)行，互不影響。 我們用一種有向圖來表示上述問題。在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關(guān)系，這種有向圖叫做頂點表示活動的網(wǎng)絡(luò)(Activity On Vertex Network)簡稱為AOV網(wǎng)。7.5.1 拓?fù)渑判蛘n程編號課程名稱先導(dǎo)課程編號C1程序設(shè)計基礎(chǔ)無C2離散數(shù)

10、學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5算法分析與設(shè)計C3，C4C6計算機(jī)組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c2 在AOV網(wǎng)絡(luò)中，如果頂點Vi的活動必須在頂點Vj的活動以前進(jìn)行，則稱Vi為Vj的前趨頂點，而稱Vj為Vi的后繼頂點。這種前趨后繼關(guān)系有傳遞性。此外，任何活動i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。 從前驅(qū)和后繼的傳遞性和反自反性來看，AOV

11、網(wǎng)中不能出現(xiàn)回路(有向環(huán))，回路表示頂點之間的先后關(guān)系進(jìn)入了死循環(huán)。 判斷AOV網(wǎng)是否有有向環(huán)的方法是對該AOV網(wǎng)進(jìn)行拓?fù)渑判颍瑢OV網(wǎng)中頂點排列成一個線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。何謂“拓?fù)渑判颉?？拓?fù)湫蛄校?在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓?fù)湫蛄?。拓?fù)渑判?由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫拓?fù)渑判?。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?，滿足上述定義的任一線性序列都稱為它的拓?fù)湫蛄?。拓?fù)溆行蛐蛄校?（C1，C2

12、，C3，C4，C5，C8，C9，C7，C6） （C2，C5，C1，C8，C3，C9，C4，C7，C6）如何進(jìn)行拓?fù)渑判?？解決方法： 1）從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之； 2）從有向圖中刪去此頂點以及所有以它為尾的??； 3）重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。后一種情況說明有向圖中存在環(huán)。如何在計算機(jī)中實現(xiàn) 拓?fù)渑判蚰?？拓?fù)渑判蛩惴ǖ膶崿F(xiàn)為了實現(xiàn)拓?fù)渑判虻乃惴?，對給定的有向圖可采用鄰接表作為它的存儲結(jié)構(gòu)。將每個鏈表的表頭結(jié)點構(gòu)成一個順序表，各表頭結(jié)點的Data域存放相應(yīng)頂點的入度值。每個頂點入度初值可隨鄰接表動態(tài)生成過程中累計得到。在拓?fù)渑判蜻^程中，凡入度為零

13、的頂點即是沒有前趨的頂點，可將其取出列入有序序列中，同時將該頂點從圖中刪除掉不再考慮。刪去一個頂點時，所有它的直接后繼頂點入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個堆棧，將已檢驗到的入度為零的頂點標(biāo)號進(jìn)棧，當(dāng)再出現(xiàn)新的無前趨頂點時，也陸續(xù)將其進(jìn)棧。每次選入度為零的頂點時，只要取棧頂頂點即可。4004 2100314 AOV網(wǎng)絡(luò)的鄰接表01234頂點的入度數(shù)組下標(biāo)用鄰接表存儲AOV網(wǎng)絡(luò)，拓?fù)渑判蛩惴枋觯?1) 把鄰接表中所有入度為零的頂點進(jìn)棧；(2) 在棧不空時： 退棧并輸出棧頂?shù)捻旤c j； 在鄰接表的第 j 個單鏈表中，查找頂點為 j 的所有直接后繼頂點 k，并將 k 的入度減1。若頂

14、點 k 的入度為零，則頂點 k 進(jìn)棧； 若?？諘r輸出的頂點個數(shù)不是 n，則有向圖中有環(huán)路，否則拓?fù)渑判蛲戤?。拓?fù)渑判蛩惴⊿tatus Topological Sort(ALGraph G)/有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路， /則輸出G的頂點的1個拓?fù)湫蛄胁⒎祷豋K，否則ERROR FindInDegree(G，indegree)； /對各頂點求入度indegree0.vernum-1 InitStack(S)； for(i=0；inextarc)k=p-adjvex；/對i號頂點的每個鄰接點入度減1if(！(-indegreek)Push(S，k); /若入度減為0，則入棧 /for/whileif(countG.ve