[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第7章(已改無(wú)錯(cuò)字)
2023-02-19 14:46:10 本頁(yè)面
【正文】 網(wǎng)中用權(quán)值表示，一個(gè)生成樹的代價(jià)就是生成樹各邊的代價(jià)之和。 最小生成樹有重要的研究意義，例如，要在 n各城市建立一個(gè)交通圖，就是要在 n(n1)/2條線路中選擇 n1條代價(jià)最小的線路，在這里可以將各個(gè)城市看成圖的頂點(diǎn)，城市的線路看成邊。 40 最小生成樹 1．普里姆算法 2．克魯斯卡爾算法 41 普里姆 (Prim)算法 基本思想：假設(shè) G＝ (V, E)是連通網(wǎng)， T＝(U, TE)為欲構(gòu)造的最小生成樹。 (1)初始時(shí)令 U={1}(即構(gòu)造最小生成樹時(shí)，從頂點(diǎn) 1出發(fā) )， TE=Ф。 (2)從所有 u∈ U， v∈ VU的邊中，選取具有最小權(quán)值的邊 (u, v)，將頂點(diǎn) v加入集合 U中，將邊 (u, v)加入集合 TE中。 (3)重復(fù) (2)，直到 U＝ V為止。 42 圖 716 Prim 算法構(gòu)造最小生成樹的過程示意圖 A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D (a) (b) (c) (d) (e) (f) 6 8 12 14 16 17 5 15 6 6 6 6 6 8 8 8 8 8 12 12 12 14 14 5 43 克魯斯卡爾 (Kruskal)算法 克魯斯卡爾算法構(gòu)造最小生成樹的基本思想是：假設(shè)G＝ (V, E)是連通網(wǎng)， T＝ (U, TE)為欲構(gòu)造的最小生成樹。 (1)初始時(shí)令 U＝ V， TE＝ Φ，即最小生成樹 T由圖 G中的 n個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間沒有一條邊，這樣 T中各頂點(diǎn)各自構(gòu)成一個(gè)連通分量。 (2)把 G的邊按權(quán)值升序排列。 (3)從中選取權(quán)值最小邊 (u, v)，若 (u, v)連接 T中兩個(gè)不同的連通分量，則將 (u, v)并入 T中。 (4)重復(fù) (3)直到 T中只有一個(gè)連通分量為止。 44 圖 717 Kruskal 算法構(gòu)造最小生成樹的過程示意圖 A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D (a) (b) (c) (d) (e) (f) 6 8 12 14 16 17 5 15 5 6 6 6 6 8 8 8 5 12 12 5 5 14 5 45 最 短 路 徑 單源最短路徑 單源最短路徑是指在有向網(wǎng)中，以某個(gè)頂點(diǎn) v0作為源點(diǎn)，從 v0出發(fā)，到其余各個(gè)頂點(diǎn)的最短路徑。 圖 718是個(gè)有向網(wǎng)，圖 cost，表 ，以 1為源點(diǎn)，應(yīng)用迪杰斯特拉算法求 1到其余各頂點(diǎn)的最短路徑的全過程及各數(shù)據(jù)結(jié)構(gòu)的變化情況。 46 23 451 01 0 03 05 02 06 01 011 0 3 050c o s t 102 0 6 0???????????∞ ∞ 100∞ ∞ ∞ ∞∞ ∞ ∞ ∞∞ ∞ ∞∞ ∞ ∞ ∞ ∞ 表 71 圖 719 有向網(wǎng)的鄰接矩陣 循環(huán) S W dist[2] dist[3] dist[4] dist[5] pre[2] pre[3] pre[4] pre[5] 初始化 {1} 10 ∞ 30 100 1 1 1 1 1 {1,2} 2 10 60 30 100 1 2 1 1 2 {1,2,4} 4 10 50 30 90 1 4 1 4 3 {1,2,4,3} 3 10 50 30 60 1 4 1 3 4 {1,2,3,4,5} 5 10 50 30 60 1 4 1 3 圖 718 有向網(wǎng)示意圖 47 每一對(duì)頂點(diǎn)之間的最短路徑 求每一對(duì)頂點(diǎn)之間的最短路徑，可以通過兩種方法： 一是每次以圖中的一個(gè)頂點(diǎn)作為源點(diǎn)，調(diào)用 n次Dijkstra算法，便可求得圖中每一對(duì)頂點(diǎn)間的最短路徑。 另一種方法是采用弗洛伊德 (Floyd)算法，此算法比較簡(jiǎn)單，易于理解和編程。 48 每一對(duì)頂點(diǎn)之間的最短路徑 圖 ，按照弗洛伊德算法求每對(duì)頂點(diǎn)間的最短路徑，矩陣 D和 path的變化情況如圖 。 38712 342 co st= ∞ 7 2 3 ∞ 8
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1