數(shù)據(jù)結(jié)構(gòu)-最小生成樹(shù)

1、最小生成樹(shù)最小生成樹(shù)生成樹(shù)和生成森林生成樹(shù)和生成森林最小生成樹(shù)最小生成樹(shù)*關(guān)節(jié)點(diǎn)和重連通分量關(guān)節(jié)點(diǎn)和重連通分量小結(jié)和作業(yè)小結(jié)和作業(yè)遍歷應(yīng)用舉例遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例1.1.求一條求一條從頂點(diǎn)從頂點(diǎn)i i到頂點(diǎn)到頂點(diǎn)s s的簡(jiǎn)單路徑的簡(jiǎn)單路徑2.2.求兩個(gè)頂點(diǎn)之間的一條求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短長(zhǎng)度最短的路徑的路徑圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例1.1.求一條求一條從頂點(diǎn)從頂點(diǎn)i i到頂點(diǎn)到頂點(diǎn)s s的簡(jiǎn)單路徑的簡(jiǎn)單路徑求從頂點(diǎn)b b到頂點(diǎn)k k的一條簡(jiǎn)單路徑。abchdekfg從頂點(diǎn)b b出發(fā)進(jìn)行深度優(yōu)先搜索遍歷圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例求從頂點(diǎn)b b到頂點(diǎn)k k

2、的一條簡(jiǎn)單路徑。假設(shè)找到的第一個(gè)鄰接點(diǎn)是a,a,且且得到的結(jié)點(diǎn)訪問(wèn)序列為: b a c h d e k f g假設(shè)找到的第一個(gè)鄰接點(diǎn)是g, ,則得到的結(jié)點(diǎn)訪問(wèn)序列為:b g f k e a d h cabchdekfg圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例1. 從頂點(diǎn) i 到頂點(diǎn)s ,若存在路徑，則從頂點(diǎn) i 出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s 。2. 簡(jiǎn)單路徑可能有多條。3. 由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。結(jié)論：結(jié)論：圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例void DFSearch( int v, int s, char *PATH) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍

3、歷圖G， / 求得一條從v到s的簡(jiǎn)單路徑，并記錄在PATH中 visitedv = TRUE; / 訪問(wèn)第 v 個(gè)頂點(diǎn) for (w=FirstAdjVex(v); w=0; w=NextAdjVex(v) ) if (!visitedw) DFSearch(w, s, PATH); Append(PATH, getVertex(v); / 第v個(gè)頂點(diǎn)加入路徑if (w = = s) found = TRUE; Append(PATH, w);break; else if (!found) Delete (PATH); / 從路徑上刪除頂點(diǎn) v 圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例2.2.求兩個(gè)頂

4、點(diǎn)之間的一條求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短長(zhǎng)度最短的路的路徑徑 若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例abchdekfg求從頂點(diǎn)b b到頂點(diǎn)k k的一條路徑長(zhǎng)度最短的路徑。圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例abchdekfgabchdekfg廣度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序是按廣度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序是按“路徑長(zhǎng)度路徑長(zhǎng)度”漸增的次序漸增的次序。廣度優(yōu)先搜索廣度優(yōu)先搜索是使用是使用“隊(duì)列隊(duì)列”實(shí)現(xiàn)的，實(shí)現(xiàn)的，如何記住路徑的所有結(jié)點(diǎn)？如何記住路徑的所有結(jié)點(diǎn)？圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例012345ABCDEF140435250

5、11253BACDFE圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例0 A1 B2 C 3 D4 E5 F6 G7 K1-110001abchdekfg1圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例怎樣修改廣度優(yōu)先遍歷算法呢？while (!QueueEmpty(Q) DeQueue(Q, u); for(w=FirstAdjVex(G, u); w; w=NextAdjVex(G,u,w) w.parent = u; if( w = = ?) found =true; break; if(!visitedw) visitedw=TRUE; EnQueue(Q, w); / for if(found) break; /

6、 while/ 從w開(kāi)始往后找祖先結(jié)點(diǎn)，逆向打印生成樹(shù)生成樹(shù)一、定義一、定義圖圖G的生成樹(shù)是的生成樹(shù)是G的極小連通子圖，即包含的極小連通子圖，即包含G中的所有頂點(diǎn)（中的所有頂點(diǎn)（n）和）和n-1條邊的連通子圖條邊的連通子圖生成樹(shù)生成樹(shù)V1V2V3V4V5V8V6V7V1V2V4V8V5V3V6V7V1V2V3V4V5V8V6V7深度優(yōu)先：深度優(yōu)先：廣度優(yōu)先：廣度優(yōu)先：生成樹(shù)生成樹(shù)二、算法二、算法圖的遍歷算法訪問(wèn)了圖中的每個(gè)頂點(diǎn)一次圖的遍歷算法訪問(wèn)了圖中的每個(gè)頂點(diǎn)一次且僅一次。且僅一次。訪問(wèn)某個(gè)頂點(diǎn)的鄰接點(diǎn)時(shí)，要經(jīng)過(guò)與這兩訪問(wèn)某個(gè)頂點(diǎn)的鄰接點(diǎn)時(shí)，要經(jīng)過(guò)與這兩個(gè)頂點(diǎn)相關(guān)聯(lián)的邊。個(gè)頂點(diǎn)相關(guān)聯(lián)的邊。因

7、此，圖的遍歷算法可以產(chǎn)生一顆生成樹(shù)：因此，圖的遍歷算法可以產(chǎn)生一顆生成樹(shù)：所有的頂點(diǎn)和經(jīng)過(guò)的邊。所有的頂點(diǎn)和經(jīng)過(guò)的邊。生成森林生成森林一、定義一、定義 非連通圖非連通圖G的每個(gè)連通分量的生成樹(shù)，的每個(gè)連通分量的生成樹(shù)，構(gòu)成了圖構(gòu)成了圖G的生成森林的生成森林生成森林生成森林abchdekfg812345670812345670achdkfebgabchdekfg非連通圖非連通圖G：G的深度優(yōu)先搜索生的深度優(yōu)先搜索生成森林：成森林：最小生成樹(shù)最小生成樹(shù) 假設(shè)要在假設(shè)要在 n n 個(gè)城市之間建立通訊聯(lián)絡(luò)個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通網(wǎng)，則連通 n n 個(gè)城市只需要修建個(gè)城市只需要修建 n-1n-1

8、條線(xiàn)條線(xiàn)路，路，如何在最節(jié)省如何在最節(jié)省經(jīng)費(fèi)經(jīng)費(fèi)的前提下建立的前提下建立這個(gè)這個(gè)通訊網(wǎng)通訊網(wǎng)？問(wèn)題：?jiǎn)栴}：最小生成樹(shù)最小生成樹(shù)abcdegf195141827168213127連通網(wǎng)：連通網(wǎng)：n個(gè)城市和城市間個(gè)城市和城市間可能的通信線(xiàn)路可能的通信線(xiàn)路網(wǎng)的頂點(diǎn)：網(wǎng)的頂點(diǎn)：表示城市表示城市網(wǎng)的邊：網(wǎng)的邊：表示兩個(gè)城市之間表示兩個(gè)城市之間的線(xiàn)路的線(xiàn)路網(wǎng)的邊上的權(quán)值：網(wǎng)的邊上的權(quán)值：通信代價(jià)通信代價(jià)最小生成樹(shù)最小生成樹(shù) 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值權(quán)值之和之和”為最小。算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：該問(wèn)題等價(jià)于：

9、算法算法三三：（普里姆算法）：（普里姆算法）算法算法一一：（：（破圈法破圈法）破圈法破圈法一、基本思想1、如果圖G是一個(gè)連通圖，但不是樹(shù)，則邊數(shù)n-1，圖中一定存在回路（環(huán)/圈）。2、將所有的邊按權(quán)重從大到小排列3、對(duì)每條邊e嘗試下面的操作，直到G中的邊數(shù)=n-1 如果刪除e, 圖G仍然是連通圖，則從G中刪除e，否則，保留e。破圈法破圈法abcdegf195141827168213127二、示例(venum=7, arcnum=11, 67) 克魯斯卡爾算法克魯斯卡爾算法具體做法具體做法: : 先構(gòu)造一個(gè)只含先構(gòu)造一個(gè)只含n n個(gè)頂點(diǎn)的子圖個(gè)頂點(diǎn)的子圖SGSG，然，然后從權(quán)值最小的邊開(kāi)始，若它

10、的添加不使后從權(quán)值最小的邊開(kāi)始，若它的添加不使SGSG中產(chǎn)中產(chǎn)生回路，則在生回路，則在SGSG上加上這條邊，如此重復(fù)，直至上加上這條邊，如此重復(fù)，直至加上加上n-1n-1條邊為止。條邊為止?？紤]問(wèn)題的出發(fā)點(diǎn)考慮問(wèn)題的出發(fā)點(diǎn): : 為使生成樹(shù)上為使生成樹(shù)上邊的權(quán)值之和邊的權(quán)值之和達(dá)到最小達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小。能地小?？唆斔箍査惴唆斔箍査惴╝bcdegf3abcegfd 21581416克魯斯卡爾算法克魯斯卡爾算法算法描述算法描述: :構(gòu)造非連通圖構(gòu)造非連通圖 ST=(V, );ST=(V, ); k=i=0; / k k=i=0

11、; / k 選中的邊數(shù)選中的邊數(shù) while (kn-1) while (kn-1) +i; +i; 檢查邊集檢查邊集E E中第中第i i條權(quán)值最小的邊條權(quán)值最小的邊(u,v);(u,v); if if 若若(u,v)(u,v)加入加入STST后不使后不使STST中產(chǎn)生回路中產(chǎn)生回路， 則輸出邊則輸出邊(u,v);(u,v); 且且k+;k+; 普里姆算法普里姆算法 在生成樹(shù)的構(gòu)造過(guò)程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集U和尚未落在生成樹(shù)上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。UV-U普里姆算法普里姆算法abcdegf19514182716

12、8213127abegf14d8c351621g b dg b fc 普里姆算法普里姆算法算法的核心：選擇向集合U中加入的頂點(diǎn)時(shí)，要選擇到U具有最短邊的頂點(diǎn)1、對(duì)任何一個(gè)頂點(diǎn)v，如果它有多個(gè)鄰接U的邊，則需要找出最短的邊作為鄰接到U的邊2、從所有的V U頂點(diǎn)中，找出具有最短邊的頂點(diǎn)，將它加入U(xiǎn)普里姆算法普里姆算法技巧：技巧：設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前V VU U集中的每個(gè)頂點(diǎn)，集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集記錄和頂點(diǎn)集U U中頂點(diǎn)相連接的代價(jià)最小的邊：中頂點(diǎn)相連接的代價(jià)最小的邊：struct VertexType adjvex; / U集中的頂點(diǎn)序號(hào) VRType lowc

13、ost; / 邊的權(quán)值 closedgeMAX_VERTEX_NUM;普里姆算法普里姆算法初始時(shí)U=v0對(duì)wV U， closedgew.lowcost=或者= closedgew.adjvex=v0當(dāng)U=U u時(shí)，對(duì)wV U， 修改closedgewclosedgew.lowcost=或者不變closedgew.adjvex=u普里姆算法普里姆算法abcdegf195141827168213127aedcbaaa19141814e12ee8168d3dd7213c5 5普里姆算法普里姆算法void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從

14、頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù) k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 繼續(xù)向生成樹(shù)上添加頂點(diǎn)繼續(xù)向生成樹(shù)上添加頂點(diǎn);普里姆算法普里姆算法 k = minimum(closedge); / 求出加入生成樹(shù)的下一個(gè)頂點(diǎn)(k) printf(closedgek.adjvex, G.vexsk, closedgek.lowcost

15、); / 輸出生成樹(shù)上一條邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) /修改其它頂點(diǎn)的最小邊 if (G.arcskj.adj adjvex; DFSArticul(G, v); / 從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索 if (count nextarc) min =visitedv0 = +count; / v0是第是第count個(gè)訪問(wèn)的頂點(diǎn)個(gè)訪問(wèn)的頂點(diǎn), 并設(shè)并設(shè)lowv0的初值為的初值為min / 檢查v0的每個(gè)鄰接點(diǎn)lowv0 = min;關(guān)節(jié)點(diǎn)和重連通圖關(guān)節(jié)點(diǎn)和重連通圖 w = p-adjvex; / w為v0的鄰

16、接頂點(diǎn) if (visitedw = 0) / w未曾被訪問(wèn) DFSArticul(G, w); / 返回前求得loww else / w是回邊上的頂點(diǎn)if (loww =visitedv0) printf(v0, G.verticesv0.data); /輸出關(guān)節(jié)點(diǎn)輸出關(guān)節(jié)點(diǎn)if (visitedw =0;w=NextAdjVex(G,v,w) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode);*p=GetVex(G,v),NULL,NULL;if(first) T-lchild=p;first=FALSE;else q-nextsibling=p;q=p;DFSTree(G,w.q);/end of if/end of DFSTreeSG1SG2SG3Vw1w3w2生成森林生成森林二、算法二、算法以孩子兄