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

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

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