上傳人：我***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：孔**（實(shí)名認(rèn)證）

IP屬地：北京

IP屬地：北京 上傳時(shí)間：2022-09-22 格式：PPTX 頁數(shù)：46 大?。?04.99KB 積分：14 舉報(bào) 版權(quán)申訴

1、第7章 圖7.1 圖的定義和術(shù)語7.2 圖的存儲(chǔ)結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問題7.5 有向無環(huán)圖及其應(yīng)用7.6 最短路徑7.4 圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹2.1）普里姆算法2.2）克魯斯卡爾算法例：圖及其生成樹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）是一個(gè)連通網(wǎng)，

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

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

4、wcost存儲(chǔ)該邊上的權(quán)。顯然， closedgei-1.lowcost =Mincost(u，vi)|uU 即vi到已生成子樹的最短距離等于到U中所有頂點(diǎn)中的最小邊的權(quán)值。 vex域存儲(chǔ)該邊依附的在U中的頂點(diǎn)。例：求下圖最小生成樹。假設(shè)開始頂點(diǎn)就選為頂點(diǎn)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

5、,4 V-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; /頂點(diǎn)編號 VRType lowcost; / =Mincost(u,vi|uU) closedgeMAX_VERTEX_NUM;Void MiniSpanTree_PRIM(MGraph G, VertexType u) k = LocateVex ( G, u ); / 頂點(diǎn)u為構(gòu)造生成樹的起始點(diǎn),返回頂

6、點(diǎn)u在圖中的位置 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) /在其余頂點(diǎn)中選擇 k = minimum(closedge); / 求出T的下一結(jié)點(diǎn)(k) printf(closedgek.adjvex, G.vexsk); /輸出生成樹的邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) if

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

8、N = V, E ,最初先構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn)，沒有邊的非連通圖 T = V, , 圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在 E 中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到 T 中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。 如此重復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。v1v6v5v4v2v34623561556克魯斯卡爾（Kruskal）構(gòu)造最小生成樹算法： 設(shè) N=(V，E)是一個(gè)連通網(wǎng)，V是頂點(diǎn)集，T=（V， ），把E中權(quán)值最小的邊加入T中，再選權(quán)值最小的邊，而且它的頂點(diǎn)落在T中不同的連通分量上則加入T，否則不加入T，直到V都在T連通分量為止。

9、v1v6v5v4v2v342315v1v6v5v4v2v34231v1v6v5v4v2v3231v1v6v4v321v1v31克魯斯卡爾算法構(gòu)造最小生成樹的過程22連通分量1連通分量2連通分量3連通分量1連通分量1連通分量2連通分量2連通分量1201511264.克魯斯卡爾（Kruskal）算法具體做法 先構(gòu)造一個(gè)只含 n個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中去，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。例：對下圖中無向網(wǎng)，用克魯斯卡爾算法求最小生成樹的過程。 22156134 無向網(wǎng)6462135556465312345/*/* kruskal求解最小生成樹算法 *

10、/* 文件名kruskal.c 函數(shù)名kruskal() */*/void kruskal(edge adjlist,edge tree,int cnvx,int n) int v=0,j,k; for (j=0;jn;j+) cnvxj=j; /* 設(shè)置每一個(gè)頂點(diǎn)的連通分量 */ for (k=0;kn-1;k+) /*樹中共有n-1條邊*/ while (cnvxadjlistv.beg=cnvxadjlistv.en ) v+; /*找到屬于兩個(gè)連通分量權(quán)最小的邊*/treek=adjlistv; /*將邊v加入到生成樹中*/ for (j=0;jn;j+) /*兩個(gè)連通分量合并為一個(gè)連

11、通分量*/ if (cnvxj=cnvxadjlistv.en) cnvxj=cnvxadjlistv.beg; v+; printf(最小生成樹是：n); for (j=0;jn-1;j+) printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);算法8.6 Kruskal求解最小生成樹void kruskal(edge adjlist,edge tree,int cnvx,int n) int v=0,j,k; for (j=0;jn;j+) cnvxj=j; /* 設(shè)置每一個(gè)頂點(diǎn)的連通分量 */ for (k=0;kn-1;k+) /*樹中共

12、有n-1條邊*/ while (cnvxadjlistv.beg=cnvxadjlistv.en ) v+; /*找到屬于兩個(gè)連通分量權(quán)最小的邊*/ treek=adjlistv; /*將邊v加入到生成樹中*/ for (j=0;jn;j+) /*兩個(gè)連通分量合并為一個(gè)連通分量*/ if (cnvxj=cnvxadjlistv.en) cnvxj=cnvxadjlistv.beg; v+; printf(最小生成樹是：n); for (j=0;jn-1;j+) printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);一般來講,. 在不使用優(yōu)先隊(duì)列優(yōu)

13、化的條件下，普里姆算法的時(shí)間復(fù)雜度為 O(V2)，使用后的時(shí)間復(fù)雜度為O(elogV)，適于稠密圖； 克魯斯卡爾算法需對 e 條邊按權(quán)值進(jìn)行排序，其時(shí)間復(fù)雜度為 O(elogV)，適于稀疏圖。P.S.如果使用斐波那契堆，PRIM的效率會(huì)有進(jìn)一步提升。第7章 圖7.1 圖的定義和術(shù)語7.2 圖的存儲(chǔ)結(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圖，是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。有向無環(huán)圖Directed acycline graph DAG及其應(yīng)用有

14、向樹DAG環(huán)一般有向圖偏序：集合X中的元素只有部分成員可以比較關(guān)系（如先后關(guān)系）的。如：v1v2v4v3v2與v3誰先?全序：集合X中的全部成員都可以比較關(guān)系（如先后關(guān)系）的也稱為拓?fù)溆行颉Ｈ纾簐1v2v4v3v1v2v4v3v1v2v4v3v1v2v4v32320151202 對整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問題：一是工程能否順利進(jìn)行；二是估算整個(gè)工程完成所必須的最短時(shí)間。 有向無環(huán)圖的應(yīng)用：拓?fù)渑判蜿P(guān)鍵路徑 在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系： 先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開始實(shí)施另一個(gè)子項(xiàng)目； 子項(xiàng)目之間無次序要求，即兩個(gè)子項(xiàng)目

15、可以同時(shí)進(jìn)行，互不影響。20141114 我們用一種有向圖來表示上述問題。在這種有向圖中，頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)的優(yōu)先關(guān)系，這種有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Activity On Vertex Network)簡稱為AOV網(wǎng)。7.5.1 拓?fù)渑判蛘n程編號課程名稱先導(dǎo)課程編號C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5算法分析與設(shè)計(jì)C3，C4C6計(jì)算機(jī)組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7

16、c8c1c9c4c2c12c10c5c3c6c7c8c2 在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動(dòng)必須在頂點(diǎn)Vj的活動(dòng)以前進(jìn)行，則稱Vi為Vj的前趨頂點(diǎn)，而稱Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。此外，任何活動(dòng)i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。 從前驅(qū)和后繼的傳遞性和反自反性來看，AOV網(wǎng)中不能出現(xiàn)回路(有向環(huán))，回路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。 判斷AOV網(wǎng)是否有有向環(huán)的方法是對該AOV網(wǎng)進(jìn)行拓?fù)渑判?，將AOV網(wǎng)中頂點(diǎn)排列成一個(gè)線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點(diǎn)，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。AOV網(wǎng)

17、，即頂點(diǎn)活動(dòng)網(wǎng)何謂“拓?fù)渑判颉?？拓?fù)湫蛄校?在AOV網(wǎng)中，若不存在回路，則所有活動(dòng)可排列成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，我們把此序列叫做拓?fù)湫蛄?。拓?fù)渑判?由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫拓?fù)渑判?。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?，滿足上述定義的任一線性序列都稱為它的拓?fù)湫蛄小OV網(wǎng)，即頂點(diǎn)活動(dòng)網(wǎng)拓?fù)溆行蛐蛄校?（C1，C2，C3，C4，C5，C8，C9，C7，C6） （C2，C5，C1，C8，C3，C9，C4，C7，C6）如何進(jìn)行拓?fù)渑判?？解決方法： 1）從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之； 2）從有向圖中刪去此頂點(diǎn)以及所有以它為尾的??； 3）重復(fù)上述兩步

18、，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。后一種情況說明有向圖中存在環(huán)。如何在計(jì)算機(jī)中實(shí)現(xiàn) 拓?fù)渑判蚰?？拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，對給定的有向圖可采用鄰接表作為它的存儲(chǔ)結(jié)構(gòu)。將每個(gè)鏈表的表頭結(jié)點(diǎn)構(gòu)成一個(gè)順序表，各表頭結(jié)點(diǎn)的Data域存放相應(yīng)頂點(diǎn)的入度值。每個(gè)頂點(diǎn)入度初值可隨鄰接表動(dòng)態(tài)生成過程中累計(jì)得到。在拓?fù)渑判蜻^程中，凡入度為零的頂點(diǎn)即是沒有前趨的頂點(diǎn)，可將其取出列入有序序列中，同時(shí)將該頂點(diǎn)從圖中刪除掉不再考慮。刪去一個(gè)頂點(diǎn)時(shí)，所有它的直接后繼頂點(diǎn)入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個(gè)堆棧，將已檢驗(yàn)到的入度為零的頂點(diǎn)標(biāo)號進(jìn)棧，當(dāng)再出現(xiàn)新的無前趨頂點(diǎn)時(shí)，也陸續(xù)將其進(jìn)棧。每次選入度為零的頂點(diǎn)時(shí)，只要取棧頂頂點(diǎn)即可。4004 2100314 AOV網(wǎng)絡(luò)的鄰接表01234頂點(diǎn)的入度數(shù)組下標(biāo)用鄰接表存儲(chǔ)AOV網(wǎng)絡(luò)，拓?fù)渑判蛩惴枋觯?1) 把鄰接表中所有入度為零的頂點(diǎn)進(jìn)棧；