資源描述:
《§8.4最小生成樹—普里姆算法.ppt》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、§8.4最小生成樹—普里姆算法2015年11月引例公園導(dǎo)游圖設(shè)計(jì)功能要求:了解公園所有景點(diǎn)游客從公園大門進(jìn)入,選一條游覽各景點(diǎn)的線路。從一景點(diǎn)到另一景點(diǎn)的最短路徑各景點(diǎn)修建管道,總長度最短怎樣求得游覽各景點(diǎn)的線路?(第12課時)2Datastructures公園導(dǎo)游圖需完成的功能:如何存儲地圖?(第11課時)1(注:分5次課依次完成該案例)3如何求兩點(diǎn)間的最短路徑?(第13課時)4求得管道修建方案?(第14、15課時)思考:管道修建要解決的主要問題?如何鋪設(shè)管道?3怎樣保證總代價最???2如何連通所有景點(diǎn)?1問題
2、1:連通所有景點(diǎn)ABCEFDGABCEFDGABCEFDG生成樹:連通圖的極小連通子圖,含圖中所有n個頂點(diǎn),只有n-1條邊。圖a圖b圖c生成樹不唯一問題2:保證總代價最小ABCEFDG圖aABCEFDG505040302025圖bABCEFDG504030202025圖c最小生成樹:圖的所有生成樹中,所有邊上的權(quán)值之和最小的生成樹。5050404020202530Prim(普里姆)算法Kruskal(克魯斯卡爾)算法最小生成樹兩種算法:問題2:保證總代價最小普里姆(Prim)算法思想:1.將圖G=(V,E)分為
3、兩個頂點(diǎn)集U:已選頂點(diǎn)集;V-U:未選頂點(diǎn)集.2.每次從V-U中選擇一個到U中頂點(diǎn)距離最短的頂點(diǎn);直到所有頂點(diǎn)都被選擇.0543216513566425時間復(fù)雜度為o(n2),n:頂點(diǎn)數(shù)UV-U問題2:保證總代價最小1.普里姆(Prim)算法054321651UV-U012345構(gòu)造過程0543216513566425圖a1.普里姆(Prim)算法054321651V-U134525645構(gòu)造過程U0543216513566425圖a0貪心思想1.普里姆(Prim)算法054321651UV-U01525645
4、62構(gòu)造過程0543216513566425圖a34貪心思想1.普里姆(Prim)算法054321651UV-U01532564562構(gòu)造過程0543216513566425圖a4貪心思想1.普里姆(Prim)算法054321651UV-U015325645623構(gòu)造過程0543216513566425圖a4貪心思想1.普里姆(Prim)算法054321651UV-U015342564562305432115423構(gòu)造過程0543216513566425圖a貪心思想2.最小生成樹應(yīng)用管道最短問題轉(zhuǎn)化為:能連通所
5、有景點(diǎn)(頂點(diǎn)),且總距離最小的最小生成樹。公園管道設(shè)計(jì)給各景點(diǎn)修建自來水管道,總長度最短問題3:管道修建方案采用普里姆算法求得管道修建方案3.編程實(shí)現(xiàn)在VC中編程,采用prim算法求得自來水管道修建的方案。下一節(jié)將分析prim算法…504613228102514241618120410255圖a3212614課堂練習(xí)2020116166141160410253122052(1)(2)生成樹:連通圖中各頂點(diǎn)且無回路1最小生成樹:總代價最小2普里姆(Prim)算法(重點(diǎn)、難點(diǎn))3課堂小結(jié)課后實(shí)踐8個小組:實(shí)現(xiàn)校園
6、導(dǎo)游系統(tǒng)功能如下:查詢各景點(diǎn)的相關(guān)信息;查詢圖中任意兩個景點(diǎn)間的最短路徑查詢圖中任意兩個景點(diǎn)間的所有路徑查詢游覽景點(diǎn)的最佳線路Datastructures課程中心:自主學(xué)習(xí)&資料下載其他學(xué)習(xí)資源謝謝各位專家指導(dǎo)!