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

認(rèn)證信息

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

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

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2023-07-24 格式：PPT 頁(yè)數(shù)：36 大小：2.63MB 積分：15 舉報(bào) 版權(quán)申訴

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

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

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

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

//頂點(diǎn)u為構(gòu)造生成樹(shù)的起始點(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頁(yè)，課件共36頁(yè)，創(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]);

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

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

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

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

FindInDegree(G，indegree)；

//對(duì)各頂點(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；//對(duì)輸出頂點(diǎn)計(jì)數(shù)第34頁(yè)，課件共36頁(yè)，創(chuàng)作于2023年2月

while(!StackEmpty(S)){