【文章內容簡介】 叉樹 T。 算法以 |C|個葉結點開始，執(zhí)行 |C|－ 1次的 “ 合并 ”運算后產生最終所要求的樹 T。 26 哈夫曼編碼 在書上給出的算法 huffmanTree中，編碼字符集中每一字符 c的頻率是 f(c)。 以 f為鍵值的優(yōu)先隊列 Q用在貪心選擇 時有效地確定算法當前要合并的 2棵具有最小頻率的樹。一旦 2棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的 2棵樹的頻率之和，并將新樹插入優(yōu)先隊列 Q。經過 n－ 1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹 T。 算法 huffmanTree用最小堆實現(xiàn)優(yōu)先隊列 Q。初始化優(yōu)先隊列需要 O(n)計算時間，由于最小堆的removeMin和 put運算均需 O(logn)時間， n－ 1次的合并總共需要 O(nlogn)計算時間。因此，關于 n個字符的哈夫曼算法的 計算時間 為 O(nlogn) 。 27 哈夫曼編碼 哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有 貪心選擇性質 和 最優(yōu)子結構性質 。 (1)貪心選擇性質 (2)最優(yōu)子結構性質 28 單源最短路徑 給定帶權有向圖 G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定 V中的一個頂點，稱為 源 ?，F(xiàn)在要計算從源到所有其它各頂點的 最短路長度 。這里路的長度是指路上各邊權之和。這個問題通常稱為 單源最短路徑問題 。 算法基本思想 Dijkstra算法是解單源最短路徑問題的貪心算法。 29 單源最短路徑 其 基本思想 是，設置頂點集合 S并不斷地作 貪心選擇來擴充這個集合。一個頂點屬于集合 S當且僅當從源到該頂點的最短路徑長度已知。 初始時， S中僅含有源。設 u是 G的某一個頂點，把從源到 u且中間只經過 S中頂點的路稱為從源到 u的特殊路徑，并用數(shù)組 dist記錄當前每個頂點所對應的最短特殊路徑長度。 Dijkstra算法每次從 VS中取出具有最短特殊路長度的頂點 u，將 u添加到 S中，同時對數(shù)組 dist作必要的修改。一旦 S包含了所有 V中頂點， dist就記錄了從源到所有其它頂點之間的最短路徑長度。 30 單源最短路徑 例如 ，對右圖中的有向圖，應用 Dijkstra算法計算從源頂點 1到其它頂點間最短路徑的過程列在下頁的表中。 31 單源最短路徑 迭代 S u dist[2] dist[3] dist[4] dist[5] 初始 {1} 10 maxint 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 Dijkstra算法的迭代過程： 32 單源最短路徑 算法的正確性和計算復雜性 (1)貪心選擇性質 (2)最優(yōu)子結構性質 (3)計算復雜性 對于具有 n個頂點和 e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么 Dijkstra算法的主循環(huán)體需要 時間。這個循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時間。算法的其余部分所需要時間不超過 。 )(nO)( 2nO)( 2nO33 最小生成樹 設 G =(V,E)是無向連通帶權圖，即一個 網絡 。 E中每條邊 (v,w)的權為 c[v][w]。如果 G的子圖 G’是一棵包含 G的所有頂點的樹，則稱 G’為 G的生成樹。生成樹上各邊權的總和稱為該生成樹的 耗費 。在 G的所有生成樹中，耗費最小的生成樹稱為 G的 最小生成樹 。 網絡的最小生成樹在實際中有廣泛應用。 例如 ，在設計通信網絡時，用圖的頂點表示城市，用邊 (v,w)的權c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網絡的最經濟的方案。 34 最小生成樹 最小生成樹性質 用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的 Prim算法和 Kruskal算法 都可以看作是應用貪心算法設計策略的例子。盡管這 2個算法做貪心選擇的方式不同，它們都利用了下面的 最小生成樹性質 ： 設 G=(V,E)是連通帶權圖， U是 V的真子集。如果(u,v)?E，且 u?U， v?VU，且在所有這樣的邊中，(u,v)的權 c[u][v]最小，那么一定存在 G的一棵最小生成樹，它以 (u,v)為其中一條邊。這個性質有時也稱為MST性質 。 35 最小生成樹 Prim算法 設 G=(V,E)是連通帶權圖， V={1,2,… ,n}。 構造 G的最小生成樹的 Prim算法的 基本思想 是：首先置 S={1}，然后，只要 S是 V的真子集，就作如下的 貪心選擇 ： 選取滿足條件 i?S， j?VS，且 c[i][j]最小的邊，將頂點 j添加到 S中。這個過程一直進行到 S=V時為止。 在這個過程中選取到的所有邊恰好構成 G的一棵 最小生成樹 。 36 最小生成樹 利用最小生成樹性質和數(shù)學歸納法容易證明，上述算法中的 邊集合 T始終包含 G的某棵最小生成樹中的邊 。因此，在算法結束時， T中的所有邊構成 G的一棵最小生成樹。 例如 ，對于右圖中的帶權圖，按 Prim算法 選取邊的過程如下頁圖所示。 37 最小生成樹 38 最小生成樹 在上述 Prim算法中，還應當考慮 如何有效地找出滿足條件 i?S,j?VS，且權 c[i][j]最小的邊 (i,