數(shù)據(jù)結(jié)構(gòu)的第八講ppt課件-資料下載頁
2025-01-08 00:30本頁面
【正文】 的得名源于覆蓋每個頂點（范圍）所必需的最少數(shù)量的構(gòu)造邊，而且說它是樹是因為結(jié)果圖是非循環(huán)的。需要牢記一個重要的內(nèi)容：一張圖可能包含多個最小生成樹。創(chuàng)建的最小生成樹完全依賴于初始頂點。 78 最小生成樹算法 79 畫出下圖的生成樹 0 2 1 3 0 2 1 3 最小生成樹 80 首先明確： ? 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。 ? 按照生成樹的定義， n 個頂點的連通網(wǎng)絡(luò)的生成樹有 n 個頂點、 n1 條邊。 即有權(quán)圖 目標(biāo)： 在網(wǎng)絡(luò)的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹。 構(gòu)造最小生成樹的準(zhǔn)則 ? 必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹； ? 必須使用且僅使用 n1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的 n個頂點； ? 不能使用產(chǎn)生回路的邊。 典型用途 81 欲在 n個城市間建立通信網(wǎng)，則 n個城市應(yīng)鋪 n1條線路；但因為每條線路都會有對應(yīng)的經(jīng)濟成本，而 n個城市可能有n(n1)/2 條線路，那么， 如何選擇 n–1條線路，使總費用最少？ 數(shù)學(xué)模型： 頂點 ———表示城市，有 n個； 邊 ————表示線路，有 n–1條； 邊的權(quán)值 —表示線路的經(jīng)濟代價； 連通網(wǎng) ——表示 n個城市間通信網(wǎng)。 顯然此連通網(wǎng)是一個 生成樹！ 問題抽象： n個頂點的生成樹很多，需要從中選一棵代價最小的生成樹，即該樹各邊的代價之和最小。此樹便稱為最小生成樹 MST(Minimum cost Spanning Tree) 如何求得最小生成樹 82 —— 有多種算法，但最常用的是以下兩種： 最小生成樹的 MST 性質(zhì)如下： ? Kruskal（克魯斯卡爾）算法 ? Prim（普里姆）算法 Kruskal算法特點： 將邊歸并 ，適于求 稀疏網(wǎng) 的最小生成樹。 Prime算法特點 : 將頂點歸并 ，與邊數(shù)無關(guān)，適于 稠密網(wǎng) 。 這兩個算法，都是利用 MST 性質(zhì)來構(gòu)造最小生成樹的。 若 U集是 V的一個非空子集，若 (u0, v0)是一條 最小權(quán)值的邊 ，其中 u0?U， v0?VU；則： (u0, v0)必在最小生成樹上。 克魯斯卡爾（ Kruskal）算法 83 步驟 ： (1) 首 先構(gòu)造一個只有 n 個頂點但沒有邊的非連通圖 T = { V, ? }, 圖中每個頂點自成一個連通分量。 (2) 當(dāng)在邊集 E 中選到一條具有最小權(quán)值的邊時 ,若該邊的兩個頂點落在 T中不同的連通分量上，則將此邊加入到生成樹的 邊集合 T 中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。 (3) 如此重復(fù)下去，直到所有頂點在同一個連通分量上為止。此時的 T即為所求（ 最小生成樹 ）。 設(shè) N = { V, E }是有 n 個頂點的連通網(wǎng)， Kruskal算法采用鄰接表作為圖的存儲表示 Kruskal算法 84 例 ： 1 4 6 5 2 3 1 5 6 5 5 4 6 3 6 2 1 5 4 3 2 1 3 5 2 4 6 初始連通分量： {1},{2},{3},{4},{5},{6} 反復(fù)執(zhí)行添加、放棄動作。條件：邊數(shù)不等于 n1時 邊 動作 連通分量 (1,3) 添加 {1,3},{4},{5},{6},{2} (4,6) 添加 {1,3},{4, 6},{2},{5} (2,5) 添加 {1,3},{4, 6},{2,5} (3,6) 添加 {1,3,4, 6},{2,5} (1,4) 放棄 因構(gòu)成回路 (3,4) 放棄 因構(gòu)成回路 (2,3) 添加 {1,3,4,5,6,2} 普里姆 (Prim)算法 ? 普里姆算法的 基本思想 ： 從連通網(wǎng)絡(luò) N = { V, E }中的某一頂點 u0 出發(fā) , 選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 ( u0, v ), 將其頂點加入到生成樹頂點集合 U中。 以后每一步從一個頂點在 U 中 ,而另一個頂點不在 U 中的各條邊中選擇權(quán)值最小的邊 (u, v), 把它的頂點加入到集合 U 中。 如此繼續(xù)下去 , 直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合 U 中為止。 ? 采用鄰接矩陣作為圖的存儲表示。 85 Prim算法 86 例： 1 4 6 5 2 3 1 5 6 5 5 4 6 3 6 2 3 6 4 2 5 1 [注 ]：在最小生成樹的生成過程中，所選的邊都是 一端在 VU中，另一端在 U中。 主要內(nèi)容 圖的定義 圖的存儲表示 圖的第一個應(yīng)用：拓?fù)渑判? 圖的搜索 最小生成樹 查找最短路徑 查找最短路徑 查找最短路徑 ? 最短路徑問題： 如果從圖中某一頂點 (稱為源點 )到達另一頂點 (稱為終點 )的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。 ? 問題解法 ? 邊上權(quán)值非負(fù)情形的單源最短路徑問題 — Dijkstra算法 ? 邊上權(quán)值為任意值的單源最短路徑問題 — Bellman和 Ford算法 ? 所有頂點之間的最短路徑 — Floyd算法 92 權(quán)值非負(fù)情形的單源最短路徑問題 ? 問題的提法： 給定一個帶權(quán)有向圖 D與源點 v，求從 v 到 D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于 0。 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。 93 舉例說明 94 迭代 S u dis[2] dis[3] dis[4] dis[5] 初始 {1} 10 ∞ 30 100 1 {1,2} 2 10 60 30 100 2 {1,2,4} 4 10 50 30 90 3 {1,2,4,3} 3 10 50 30 60 4 {1,2,4,3,5} 5 10 50 30 60 1 2 5 4 3 10 20 50 100 30 10 60 賦權(quán)圖 G 由數(shù)組 D[i]可知：從頂點 1到頂點 5的最短通路的長度分別為 50、 30和 60。 Dijkstra算法 ① 初始化： S ← { v 0 }。 dist[j] ← Edge[0][j], j = 1, 2, …, n 1。 // n為圖中頂點個數(shù) ② 求出最短路徑的長度： dist[k] ← min { dist[i] }, i ? V S 。 S ← S U { k }。 ③ 修改： dist[i] ← min{ dist[i], dist[k] + Edge[k][i] }, 對于每一個 i ? V S 。 ④ 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) ② 。 95
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1