數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 6.3 圖的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)拓?fù)渑判騿?wèn)題關(guān)鍵路徑問(wèn)題最短路徑問(wèn)題6.3圖的應(yīng)用最小生成樹連通無(wú)向圖中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱v和v'是連通的連通圖如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則是連通圖連通分量無(wú)向圖的極大連通子圖連通圖只有一個(gè)連通分量，即其自身非連通的無(wú)向圖有多個(gè)連通分量最小生成樹15732461573246強(qiáng)連通圖有向圖中，如果每一對(duì)頂點(diǎn)vi,vj∈V(vi!=vj)，從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖稱作強(qiáng)連通分量強(qiáng)連通圖的強(qiáng)連通分量是其自身非強(qiáng)連通的有向圖可能有多個(gè)強(qiáng)連通分量最小生成樹123245136生成樹連通最小生成樹是一個(gè)極小連通子圖它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊最小生成樹生成樹一個(gè)圖可以有許多棵不同的生成樹生成樹具有以下共同特點(diǎn)：頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通最小生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹最小生成樹設(shè)G=(V，E)是一個(gè)連通圖則從圖中任一頂點(diǎn)出發(fā)，遍歷圖G時(shí)，得到一個(gè)邊集T(G)，T(G)與圖中所有頂點(diǎn)一起構(gòu)成圖G的極小連通子圖，它是連通圖的一棵生成樹。由DFS得到的是深度優(yōu)先生成樹由BFS得到的為廣度優(yōu)先生成樹連通無(wú)向最小生成樹V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹這些連通分量的生成樹組成非連通圖的生成森林非連通最小生成樹ABLMCFDEGHKIJABLMCFJDEGHKI最小生成樹不是唯一的從不同的頂點(diǎn)出發(fā)，能得到不同的生成樹連通網(wǎng)絡(luò)G=(V,E)各邊帶權(quán)生成樹各邊帶權(quán)生成樹的權(quán)生成樹各邊權(quán)值的和最小生成樹權(quán)值最小的生成樹最小生成樹1654327131791812752410最小生成樹問(wèn)題提出在n個(gè)城市間建立通信網(wǎng)絡(luò)頂點(diǎn)—表示城市權(quán)—城市間建立通信線路所需花費(fèi)代價(jià)希望找到一條路徑，使建立該通信網(wǎng)所需花費(fèi)的總代價(jià)最小路徑上各邊權(quán)值的和最小問(wèn)題分析n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路如何在可能的線路中選擇n-1條邊，把所有城市連起來(lái)，且總耗費(fèi)(各邊權(quán)值之和)最小找圖中的最小生成樹貪心（Prim）在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇算法得到的是在某種意義上的局部最優(yōu)解貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但是在求最小生成樹問(wèn)題上適用貪心算法克魯斯卡爾（Kruskal）算法尋找每一步當(dāng)前情況下的最小路徑不能形成回路無(wú)環(huán)圖（DAG）一個(gè)無(wú)環(huán)（回路）的有向圖叫做有向無(wú)環(huán)圖AOV網(wǎng)頂點(diǎn)表示活動(dòng)的網(wǎng)頂點(diǎn)表示活動(dòng)弧表示活動(dòng)間的先后關(guān)系A(chǔ)OV網(wǎng)中不允許有回路拓?fù)渑判騿?wèn)題拓?fù)渑判騿?wèn)題提出問(wèn)題提出如果現(xiàn)在只有一名工人做整個(gè)工程，每次只能做一項(xiàng)活動(dòng)，他應(yīng)怎樣安排所做事情的前后順序，才能順利完成此項(xiàng)工程。拓?fù)渑判蛲負(fù)渑判虻姆椒◤挠邢驁D中任選一個(gè)入度為0的頂點(diǎn)，并訪問(wèn)對(duì)所有以它為尾的弧，弧頭頂點(diǎn)的入度減1刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已訪問(wèn)，或當(dāng)圖中不存在度為0的頂點(diǎn)為止不存在度為0的頂點(diǎn):存在環(huán)拓?fù)渑判蚺e例V1：材料進(jìn)場(chǎng) V2：閥門試壓 V3：預(yù)埋預(yù)留 V4：設(shè)備安裝V5：管道預(yù)制 V6：支吊架安裝 V7：?jiǎn)螜C(jī)試運(yùn)轉(zhuǎn) V8：管道安裝V9：試壓、閉水 V10：衛(wèi)生器具安裝 V11：油漆防腐V12：沖洗消毒 V13：驗(yàn)收拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蚺e例拓?fù)渑判蛲負(fù)湫蛄校篤1→V2→V3→V4→V5→V6→V7→V8→V9→V10→V11→V12→V13或：V1→V2→V5→V3→V6→V8→V9→V11→V10→V12→V4→V7→V13AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏年P(guān)鍵路徑問(wèn)題987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4用有向圖表示工程計(jì)劃，頂點(diǎn)表示事件，弧表示活動(dòng)每個(gè)頂點(diǎn)表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始問(wèn)題描述一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件V1表示工程開(kāi)始，V9表示工程結(jié)束完成整項(xiàng)工程至少需要多少時(shí)間？哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？源點(diǎn)和匯點(diǎn)正常情況(無(wú)環(huán))下，網(wǎng)中只有一個(gè)入度為零的點(diǎn),稱為源點(diǎn)一個(gè)出度為零的點(diǎn),稱為匯點(diǎn)關(guān)鍵路徑完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度(路徑長(zhǎng)度等于路徑上各邊的權(quán)之和)這條具有最大長(zhǎng)度的路徑稱為關(guān)鍵路徑關(guān)鍵路徑問(wèn)題的相關(guān)概念關(guān)鍵路徑問(wèn)題的相關(guān)概念ee(i)：表示事件Vi的最早發(fā)生時(shí)間le(i)：表示事件Vi的最遲發(fā)生時(shí)間e(k)：活動(dòng)ak=<vi，vj>的最早開(kāi)始時(shí)間l(k)：活動(dòng)ak=<vi，vj>的最遲開(kāi)始時(shí)間l(k)-e(k)：完成活動(dòng)ak的時(shí)間余量關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)求關(guān)鍵路徑步驟求ee(i)求le(j)求e(k)求l(k)計(jì)算l(k)-e(k)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4頂點(diǎn)eele0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e

00002266046258377077071031616014140033若:l(i)-e(i)=0，則ai是關(guān)鍵活動(dòng)V1V2V3V4V5V6V7V8V9用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)：表示城市邊：表示城市間的交通聯(lián)系權(quán)：表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題提出：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，求各邊上權(quán)值之和最小的一條路徑（最短路徑）最短路徑問(wèn)題迪杰斯特拉(Dijkstra)算法每次對(duì)所有可見(jiàn)點(diǎn)的路徑長(zhǎng)度進(jìn)行排序后，選擇一條最短的路徑，這條路徑就是對(duì)應(yīng)頂點(diǎn)到源點(diǎn)的最短路徑。以對(duì)應(yīng)點(diǎn)為中繼，優(yōu)化它的鄰接點(diǎn)到源點(diǎn)的路徑。求單源最短路徑弗洛伊德(Floy