上傳人：農(nóng)***

認(rèn)證信息

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

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

IP屬地：廣東

IP屬地：廣東 上傳時間：2023-07-24 格式：PPT 頁數(shù)：36 大?。?.63MB 積分：15 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)第講最小生成樹與拓?fù)渑判虻?頁，課件共36頁，創(chuàng)作于2023年2月7.4圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹3）普里姆算法4）克魯斯卡爾算法第2頁，課件共36頁，創(chuàng)作于2023年2月例：圖及其生成樹⑤④①②③65665513420第3頁，課件共36頁，創(chuàng)作于2023年2月對于帶權(quán)的連通圖(連通網(wǎng))G，其生成樹也是帶權(quán)的，將權(quán)最小的生成樹稱為最小生成樹。

連通網(wǎng)最小生成樹的意義？如何構(gòu)造最小生成樹？第4頁，課件共36頁，創(chuàng)作于2023年2月對于帶權(quán)的連通圖(連通網(wǎng))G，其生成樹也是帶權(quán)的，將權(quán)最小的生成樹稱為最小生成樹。

連通網(wǎng)最小生成樹的意義？如何構(gòu)造最小生成樹？第5頁，課件共36頁，創(chuàng)作于2023年2月最小生成樹的MST性質(zhì)：假設(shè)N=（V,{E}）是一個連通網(wǎng)，U是頂點(diǎn)集V的一個非空子集。若（u,v）是一條具有最小權(quán)值（代價）的邊，其中u∈U，v∈V-U，則必存在一棵包含邊（u,v）的最小生成樹。⑤④①②③65665513420第6頁，課件共36頁，創(chuàng)作于2023年2月7.4圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹3）普里姆算法4）克魯斯卡爾算法第7頁，課件共36頁，創(chuàng)作于2023年2月3.普里姆（Prim）算法基本思想：(1)假設(shè)G=(V,{E})是一個具有n個頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U，{TE})是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空；(2)從V中任取一個頂點(diǎn)（假定為V1），將此頂點(diǎn)并入U中，此時最小生成樹頂點(diǎn)集U={V1}；第8頁，課件共36頁，創(chuàng)作于2023年2月(3)從那些其中一個端點(diǎn)已在U中，另一端點(diǎn)仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪叄O(shè)該邊為(Vi,Vj)，其中Vi∈U，Vj∈V-U，并把該邊和頂點(diǎn)Vj分別并入T的邊集TE和頂點(diǎn)集U；(4)如此進(jìn)行下去，每次往生成樹里并入一個頂點(diǎn)和一條邊，直到n-1次后，把所有n個頂點(diǎn)都并入生成樹T的頂點(diǎn)集U中，此時U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。第9頁，課件共36頁，創(chuàng)作于2023年2月第10頁，課件共36頁，創(chuàng)作于2023年2月例：求下圖最小生成樹。假設(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,6}12345665153124561456(c)U={1,3}V-U={2,4,5,6}31

2456

4215

6(d)U={1,3,6}V-U={2,4,5}第11頁，課件共36頁，創(chuàng)作于2023年2月31245642156(e)U={1,3,6,4}V-U={2,5}(f)U={1,3,6,4,2}V-U={5}12435642153(g)U={1,3,6,4,2,5}V-U={}54213124356

(a)無向網(wǎng)64V1V2V4V36213V55V6556第12頁，課件共36頁，創(chuàng)作于2023年2月基于鄰接矩陣的普里姆算法struct{VertaxTypeadjvex;//頂點(diǎn)編號VRTypelowcost;//=Min{cost(u,vi|u∈U)}}closedge[MAX_VERTEX_NUM];VoidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);

//頂點(diǎn)u為構(gòu)造生成樹的起始點(diǎn),返回頂點(diǎn)u在圖中的位置for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化if(j!=k)closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;

//初始，U＝{u}邊k，j的權(quán)值第13頁，課件共36頁，創(chuàng)作于2023年2月for(i=1;i<G.vexnum;++i){//在其余頂點(diǎn)中選擇

k=minimum(closedge);

//求出T的下一結(jié)點(diǎn)(k)printf(closedge[k].adjvex,G.vexs[k]);

//輸出生成樹的邊closedge[k].lowcost=0;//第k頂點(diǎn)并入U集for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost)

//新頂點(diǎn)并入U后重新選擇最小邊closedge[j]={G.vexs[k],G.arcs[k][j].adj};}//for}//MiniSpanTree_PRIMT(n)=O(n2)第14頁，課件共36頁，創(chuàng)作于2023年2月4.克魯斯卡爾（Kruskal）算法基本思想為使生成樹上總的權(quán)值最小，應(yīng)使每條邊上的權(quán)值盡可能小，自然應(yīng)從權(quán)值最小的邊選起，直至選出n-1條權(quán)值最小的邊為止，同時這n-1條邊必須不構(gòu)成回路。因此，并非每一條當(dāng)前權(quán)值最小的邊都可選。第15頁，課件共36頁，創(chuàng)作于2023年2月4.克魯斯卡爾（Kruskal）算法具體做法先構(gòu)造一個只含n個頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中去，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。第16頁，課件共36頁，創(chuàng)作于2023年2月例：對下圖中無向網(wǎng)，用克魯斯卡爾算法求最小生成樹的過程。22156134

無向網(wǎng)6462135556465312345第17頁，課件共36頁，創(chuàng)作于2023年2月一般來講：普里姆算法的時間復(fù)雜度為O(n2)，適于稠密圖；克魯斯卡爾算法需對e條邊按權(quán)值進(jìn)行排序，其時間復(fù)雜度為O(eloge)，適于稀疏圖。第18頁，課件共36頁，創(chuàng)作于2023年2月第7章圖7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑第19頁，課件共36頁，創(chuàng)作于2023年2月7.5有向無環(huán)圖及其應(yīng)用

有向無環(huán)圖(directedacyclinegraph)簡稱DAG圖，是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。第20頁，課件共36頁，創(chuàng)作于2023年2月對整個工程和系統(tǒng)，人們關(guān)心的是兩個方面的問題：一是工程能否順利進(jìn)行；二是估算整個工程完成所必須的最短時間。有向無環(huán)圖的應(yīng)用：拓?fù)渑判蜿P(guān)鍵路徑第21頁，課件共36頁，創(chuàng)作于2023年2月在工程實(shí)踐中，一個工程項(xiàng)目往往由若干個子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開始實(shí)施另一個子項(xiàng)目；②子項(xiàng)目之間無次序要求，即兩個子項(xiàng)目可以同時進(jìn)行，互不影響。第22頁，課件共36頁，創(chuàng)作于2023年2月我們用一種有向圖來表示上述問題。在這種有向圖中，頂點(diǎn)表示活動，有向邊表示活動的優(yōu)先關(guān)系，這種有向圖叫做頂點(diǎn)表示活動的網(wǎng)絡(luò)(ActivityOnVertexNetwork)簡稱為AOV網(wǎng)。7.5.1拓?fù)渑判虻?3頁，課件共36頁，創(chuàng)作于2023年2月課程編號課程名稱先導(dǎo)課程編號C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(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第24頁，課件共36頁，創(chuàng)作于2023年2月課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c2第25頁，課件共36頁，創(chuàng)作于2023年2月在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動必須在頂點(diǎn)Vj的活動以前進(jìn)行，則稱Vi為Vj的前趨頂點(diǎn)，而稱Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。此外，任何活動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ù)渑判颍瑢OV網(wǎng)中頂點(diǎn)排列成一個線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點(diǎn)，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。第26頁，課件共36頁，創(chuàng)作于2023年2月何謂“拓?fù)渑判颉保客負(fù)湫蛄校涸贏OV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓?fù)湫蛄?。拓?fù)渑判蛴葾OV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫拓?fù)渑判?。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏模瑵M足上述定義的任一線性序列都稱為它的拓?fù)湫蛄?。?7頁，課件共36頁，創(chuàng)作于2023年2月拓?fù)溆行蛐蛄校海–1，C2，C3，C4，C5，C8，C9，C7，C6）（C2，C5，C1，C8，C3，C9，C4，C7，C6）第28頁，課件共36頁，創(chuàng)作于2023年2月如何進(jìn)行拓?fù)渑判?？解決方法：1）從有向圖中選取一個沒有前驅(qū)的頂點(diǎn)，并輸出之；2）從有向圖中刪去此頂點(diǎn)以及所有以它為尾的??；3）重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。后一種情況說明有向圖中存在環(huán)。第29頁，課件共36頁，創(chuàng)作于2023年2月如何在計算機(jī)中實(shí)現(xiàn)拓?fù)渑判蚰?？?0頁，課件共36頁，創(chuàng)作于2023年2月拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，對給定的有向圖可采用鄰接表作為它的存儲結(jié)構(gòu)。將每個鏈表的表頭結(jié)點(diǎn)構(gòu)成一個順序表，各表頭結(jié)點(diǎn)的Data域存放相應(yīng)頂點(diǎn)的入度值。每個頂點(diǎn)入度初值可隨鄰接表動態(tài)生成過程中累計得到。在拓?fù)渑判蜻^程中，凡入度為零的頂點(diǎn)即是沒有前趨的頂點(diǎn)，可將其取出列入有序序列中，同時將該頂點(diǎn)從圖中刪除掉不再考慮。刪去一個頂點(diǎn)時，所有它的直接后繼頂點(diǎn)入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個堆棧，將已檢驗(yàn)到的入度為零的頂點(diǎn)標(biāo)號進(jìn)棧，當(dāng)再出現(xiàn)新的無前趨頂點(diǎn)時，也陸續(xù)將其進(jìn)棧。每次選入度為零的頂點(diǎn)時，只要取棧頂頂點(diǎn)即可。第31頁，課件共36頁，創(chuàng)作于2023年2月4∧0∧04∧21003∧14∧AOV網(wǎng)絡(luò)的鄰接表01234頂點(diǎn)的入度數(shù)組下標(biāo)第32頁，課件共36頁，創(chuàng)作于2023年2月用鄰接表存儲AOV網(wǎng)絡(luò)，拓?fù)渑判蛩惴枋觯?1)把鄰接表中所有入度為零的頂點(diǎn)進(jìn)棧；(2)在棧不空時：①退棧并輸出棧頂?shù)捻旤c(diǎn)j；②在鄰接表的第j個單鏈表中，查找頂點(diǎn)為j的所有直接后繼頂點(diǎn)k，并將k的入度減1。若頂點(diǎn)k的入度為零，則頂點(diǎn)k進(jìn)棧；③若?？諘r輸出的頂點(diǎn)個數(shù)不是n，則有向圖中有環(huán)路，否則拓?fù)渑判蛲戤?。?3頁，課件共36頁，創(chuàng)作于2023年2月拓?fù)渑判蛩惴⊿tatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路，//則輸出G的頂點(diǎn)的1個拓?fù)湫蛄胁⒎祷豋K，否則ERROR

FindInDegree(G，indegree)；

//對各頂點(diǎn)求入度indegree[0..vernum-1]

InitStack(S)；for(i=0；i<G.vexnum；++i)//建零入度頂點(diǎn)棧if(!indegree[i])Push(S，i)//入度為0者進(jìn)棧count=0；//對輸出頂點(diǎn)計數(shù)第34頁，課件共36頁，創(chuàng)作于2023年2月

while(!StackEmpty(S)){