【文章內(nèi)容簡介】 ?C。 /* 用 BUILDHEAP建立堆 */ 3. FOR i?1 To n1 Do 4. z?AllocateNode( )。 5. x?left[z]?ExtractMIN(Q)。 /* 堆操作 */ 6. y?right[z]?ExtractMIN(Q)。 /* 堆操作 */ 7. f(z)?f(x)+f(y)。 8. Insert(Q, z)。 /* 堆操作 */ 9. Return HIT CSamp。E ?設(shè) Q由一個堆實現(xiàn) ?第 2步用堆排序的 BUILDHEAP實現(xiàn) : O(n) ?每個堆操作要求 O(logn)， 循環(huán) n1次 : O(nlogn) ? T(n)=0(n)+0(nlogn) =0(nlogn) 復(fù)雜性分析 HIT CSamp。E 定理 . Huffman算法產(chǎn)生一個優(yōu)化前綴編碼樹 證 . 由于引理 引理 2成立 ,而且 Huffman算 法按照引理 2的 Greedy選擇性確定的規(guī) 則進行局部優(yōu)化選擇 ， 所以 Huffman算 法產(chǎn)生一個優(yōu)化前綴編碼樹 。 正確性證明 HIT CSamp。E Minimal spanning tree problem ?問題的定義 ?優(yōu)化解結(jié)構(gòu)分析 ? Greedy選擇性 ? Kruskal算法 ? 算法復(fù)雜性 ? 算法正確性證明 HIT CSamp。E 問題的定義 ?生成樹 ? 設(shè) G=(V, E)是一個邊加權(quán)無向連通圖 . G的生成 樹是無向樹 S=(V, T), T?E, 以下用 T表示 S. ? 如果 W: E?{實數(shù) } 是 G的 權(quán)函數(shù) , T的權(quán)值定 義為 W(T)=?(u,v)?TW(u,v). ? 最小生成樹 ? G的最小生成樹是 W(T)最小的 G之生成樹 . ? 問題的定義 輸入 : 無向連通圖 G=(V, E), 權(quán)函數(shù) W 輸出 : G的最小生成樹 HIT CSamp。E ?實例 B C A E D 70 60 80 50 90 75 300 200 B C A E D 70 50 90 300 B C A E D 70 80 50 300 B C A E D 70 60 80 50 HIT CSamp。E ?算法思想 B C A E D 70 60 80 50 90 75 300 200 B C A E D 70 60 80 50 HIT CSamp。E 定理 1. 設(shè) T是 G的最小生成樹 . 如果 T包含子樹 T1和 T2, T1是 G的子連通圖 G1的生成樹 ， T2是 G 的子連通圖 G2的生成樹 ， 則 T1是 G1的最小 生成樹 ， T2是 G2的最小生成樹 . 證 . 優(yōu)化解的結(jié)構(gòu)分析 u v T1 T2 T HIT CSamp。E Greedy選擇性 ? 一般算法 ? 初始 : A為空集合 ? 反復(fù)擴展邊集合 A, 直至 A成為最小生成樹 ? 循環(huán)不變命題 ?每次循環(huán)算法要保持下邊循環(huán)不變命題為真 “ 在每次循環(huán)前， A必是某個最小生成樹的子集” ? 在每次循環(huán)中 , 如果 A?{(u, v)}是 某個最小生成樹 的子集，則稱邊 (u, v)是 安全邊 HIT CSamp。E ? 一般算法的定義 GenericMST(G, W) 1. A=?。 /* 不變命題真 */ 2. While A 不是生成樹 Do /* 不變命題真 */ 3. 尋找一個安全邊 (u, v)。 4. A=A?{ (u, v) }。 5. Return A /* 不變命題真 */ 算法的關(guān)鍵是第三步 , 尋找安全邊 (u, v) HIT CSamp。E ? 尋找安全邊的規(guī)則 定義 1. 無向圖 G=(V, E)的一個 劃分 是 V的一個劃分 (S, VS). 定義 2. 如果 u?S, v?VS, 則邊 (u, v)稱為劃分 (S, VS) 的 交叉邊 . 定義 3. 如果邊集合 A中沒有邊是劃分 (S, VS)的交 叉邊 , 則稱劃分 (S, VS)尊重 A. 定義 4. 劃分 (S, VS)的交叉邊 (u, v)稱為 輕邊 , 如果在 所有 (S, VS)的交叉邊中 , (u, v)的權(quán)值最小 . 定義 5. 邊 (u, v)是 滿足某性質(zhì)的輕邊 , 如果在滿足該性 質(zhì)的邊中 , (u, v)的權(quán)值最小 . HIT CSamp。E ? 示例 d e f g c i h a b S VS 7 8 11 8 14 ? 紅結(jié)點集合是 S ? 淺藍結(jié)點集合是 VS ? 藍邊是交叉邊 , 權(quán)為 7的邊是輕邊 ? 紅邊集合是受尊重的邊集合 HIT CSamp。E 定理 1. 設(shè) G=(V, E)是具有邊加權(quán)函數(shù) W的無向連通圖 , A?E是包含在 G的某個最小生成樹中的邊集合 , (S,VS)是 G的尊重 A的任意劃分 , (u,v)是 (S,VS) 的交叉 輕 邊 , 則 (u, v)對 A是安全的 . 證 . 令 T是包含 A的最小生成樹 . 如果 (u, v)屬于 T, 則 (u, v)對 A是安全的 . 設(shè) (u, v)不屬于 T. 我們構(gòu)造一個 G的最小生成樹 T’, 使其包含 A?{(u, v)}, 從而證明 (u, v)安全 . HIT CSamp。E 由于 u和 v在劃分 (S, VS) 的兩邊 , T至少存在一條交叉邊在 p中 , 設(shè)為 (x, y). 由于劃分尊重 A, (x, y)不在 A中 . 刪除 p中的 (x, y), 增加 (u, v), 得到 T’=T {(x, y)} ?{(u, v)}. 往證 T’是最小生成樹 . 因為 (u, v)是輕交叉邊 , (x, y)是交叉邊 , W(u, v)?W(x, y). W(T’)=W(T)W(x,y)+W(u,v)?W(T) 由于 T是最小生成樹 , W(T’)=W(T). T’是最小生成樹 , A?{ (u,v) }?T’, (u, v)對于 A是安全的 . ? S=黃結(jié)點集合 ? VS=淺藍結(jié)點集合 ? A=紅邊集合 y x u v T p T’ HIT CSamp。E 推論 1. 設(shè) G=(V, E)是具有邊加權(quán)函數(shù) W的無向連通圖 , A?E是包含在 G的某個最小生成樹中的邊集合 , C=(VC , EC)是森林 GA=(V, A)中的樹 . 如果 (u, v) 是連接 C和 GA中另一個樹的交叉 輕 邊 , 則 (u, v) 對 A是安全的 . 證 . 劃分 (VC , VVC)尊重 A. (u, v)關(guān)于這個劃分的交叉輕邊 . 于是 , (u, v)對 A是安全的 . HIT CSamp。E Kruskal算法 MSTKruskal(G,W) 1. A=?。 2. For ?v?V[G] Do 3. MakeSet(v)。 /* 4. 按照 W值的遞增順序