數(shù)據(jù)結(jié)構(gòu)第講最小生成樹與拓撲排序

數(shù)據(jù)結(jié)構(gòu)第講最小生成樹與拓撲排序第1頁，課件共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是頂點集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個頂點的連通網(wǎng)絡(luò)，T=(U，{TE})是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空；(2)從V中任取一個頂點（假定為V1），將此頂點并入U中，此時最小生成樹頂點集U={V1}；第8頁，課件共36頁，創(chuàng)作于2023年2月(3)從那些其中一個端點已在U中，另一端點仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪叄O(shè)該邊為(Vi,Vj)，其中Vi∈U，Vj∈V-U，并把該邊和頂點Vj分別并入T的邊集TE和頂點集U；(4)如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到n-1次后，把所有n個頂點都并入生成樹T的頂點集U中，此時U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。第9頁，課件共36頁，創(chuàng)作于2023年2月第10頁，課件共36頁，創(chuàng)作于2023年2月例：求下圖最小生成樹。假設(shè)開始頂點就選為頂點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;//頂點編號VRTypelowcost;//=Min{cost(u,vi|u∈U)}}closedge[MAX_VERTEX_NUM];VoidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);

//頂點u為構(gòu)造生成樹的起始點,返回頂點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){//在其余頂點中選擇

k=minimum(closedge);

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

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

//新頂點并入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個頂點的森林，然后依權(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)值進行排序，其時間復(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圖，是描述一項工程或系統(tǒng)的進行過程的有效工具。第20頁，課件共36頁，創(chuàng)作于2023年2月對整個工程和系統(tǒng)，人們關(guān)心的是兩個方面的問題：一是工程能否順利進行；二是估算整個工程完成所必須的最短時間。有向無環(huán)圖的應(yīng)用：拓撲排序關(guān)鍵路徑第21頁，課件共36頁，創(chuàng)作于2023年2月在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項目完成后，才能開始實施另一個子項目；②子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。第22頁，課件共36頁，創(chuàng)作于2023年2月我們用一種有向圖來表示上述問題。在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關(guān)系，這種有向圖叫做頂點表示活動的網(wǎng)絡(luò)(ActivityOnVertexNetwork)簡稱為AOV網(wǎng)。7.5.1拓撲排序第23頁，課件共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計算機組成原理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ò)中，如果頂點Vi的活動必須在頂點Vj的活動以前進行，則稱Vi為Vj的前趨頂點，而稱Vj為Vi的后繼頂點。這種前趨后繼關(guān)系有傳遞性。此外，任何活動i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。從前驅(qū)和后繼的傳遞性和反自反性來看，AOV網(wǎng)中不能出現(xiàn)回路(有向環(huán))，回路表示頂點之間的先后關(guān)系進入了死循環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對該AOV網(wǎng)進行拓撲排序，將AOV網(wǎng)中頂點排列成一個線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。第26頁，課件共36頁，創(chuàng)作于2023年2月何謂“拓撲排序”？拓撲序列：在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓撲序列。拓撲排序由AOV網(wǎng)構(gòu)造拓撲序列的過程叫拓撲排序。AOV網(wǎng)的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱為它的拓撲序列。第27頁，課件共36頁，創(chuàng)作于2023年2月拓撲有序序列：（C1，C2，C3，C4，C5，C8，C9，C7，C6）（C2，C5，C1，C8，C3，C9，C4，C7，C6）第28頁，課件共36頁，創(chuàng)作于2023年2月如何進行拓撲排序？解決方法：1）從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之；2）從有向圖中刪去此頂點以及所有以它為尾的弧；3）重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。后一種情況說明有向圖中存在環(huán)。第29頁，課件共36頁，創(chuàng)作于2023年2月如何在計算機中實現(xiàn)拓撲排序呢？第30頁，課件共36頁，創(chuàng)作于2023年2月拓撲排序算法的實現(xiàn)為了實現(xiàn)拓撲排序的算法，對給定的有向圖可采用鄰接表作為它的存儲結(jié)構(gòu)。將每個鏈表的表頭結(jié)點構(gòu)成一個順序表，各表頭結(jié)點的Data域存放相應(yīng)頂點的入度值。每個頂點入度初值可隨鄰接表動態(tài)生成過程中累計得到。在拓撲排序過程中，凡入度為零的頂點即是沒有前趨的頂點，可將其取出列入有序序列中，同時將該頂點從圖中刪除掉不再考慮。刪去一個頂點時，所有它的直接后繼頂點入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個堆棧，將已檢驗到的入度為零的頂點標(biāo)號進棧，當(dāng)再出現(xiàn)新的無前趨頂點時，也陸續(xù)將其進棧。每次選入度為零的頂點時，只要取棧頂頂點即可。第31頁，課件共36頁，創(chuàng)作于2023年2月4∧0∧04∧21003∧14∧AOV網(wǎng)絡(luò)的鄰接表01234頂點的入度數(shù)組下標(biāo)第32頁，課件共36頁，創(chuàng)作于2023年2月用鄰接表存儲AOV網(wǎng)絡(luò)，拓撲排序算法描述：(1)把鄰接表中所有入度為零的頂點進棧；(2)在棧不空時：①退棧并輸出棧頂?shù)捻旤cj；②在鄰接表的第j個單鏈表中，查找頂點為j的所有直接后繼頂點k，并將k的入度減1。若頂點k的入度為零，則頂點k進棧；③若?？諘r輸出的頂點個數(shù)不是n，則有向圖中有環(huán)路，否則拓撲排序完畢。第33頁，課件共36頁，創(chuàng)作于2023年2月拓撲排序算法StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路，//則輸出G的頂點的1個拓撲序列并返回OK，否則ERROR

FindInDegree(G，indegree)；

//對各頂點求入度indegree[0..vernum-1]

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

while(!StackEmpty(S)){