-圖論與算法-第七講-最小生成樹PPT優(yōu)秀課件

1、1 算法藝術(shù)與信息學(xué)競賽 第七講 最小生成樹 2 聲明 本系列教學(xué)幻燈片屬于劉汝佳、黃亮著 算法藝術(shù)與信息學(xué)競賽配套幻燈片 本幻燈片可從本書blog上免費(fèi)下載，即使您 并未購買本書. 若作為教學(xué)使用，歡迎和作者聯(lián)系以取得 技術(shù)支持，也歡迎提供有不同針對性的修 改版本，方便更多人使用 有任何意見，歡迎在blog上評論 Blog地址：http:/ 3 內(nèi)容介紹 一、最小生成樹問題 二、Boruvka算法 三、Prim算法 四、Kruskal算法 五、MST唯一性判定 六、瓶頸生成樹 4 參考資料 CLRS Chapter 23. Minimal Spanning Trees 5 一、最小生成樹問題

2、一、最小生成樹問題(MST) 6 定義 連接每個點(diǎn)的連通圖（一定是樹） 權(quán)和盡量小 7 一般最小生成樹算法 前提: 無相等邊 維護(hù)生成森林F e為無用邊無用邊, 若e的兩個端點(diǎn)在F的同一個分 量中, 但e不在F中 對于F的每一個分量 從它出去(即恰好有一個端點(diǎn)在此分量內(nèi))的最 小邊為安全邊安全邊 不同的分量可以有相同的安全邊 結(jié)論: MST含有所有安全邊, 不含無用邊. 8 一般最小生成樹算法 結(jié)論: MST含有所有安全邊, 不含無用邊. 證明 假設(shè)有一個分量(黃色), 它的安全邊e不在T內(nèi). 則u到 v有唯一路徑, 它經(jīng)過e, 它恰好有一個端點(diǎn)在黃色分 量中. 由于e是安全邊, w(e)w(

3、e), 用e替換e得到更 小的T, 矛盾 加入無用邊將形成環(huán) 9 練習(xí) 證明最小邊屬于某棵MST中 對于某環(huán)上的最大邊e, 證明原圖中刪除e后 的MST和原來的相同 在圖中減小一個邊的權(quán), 求新的MST 情況一: e在原MST中 情況二: e不在原MST中 10 二、二、Borovka算法算法 11 Boruvka算法 由Boruvka于1926年提出(早于圖論產(chǎn)生!) 12 Boruvka算法 每個分量設(shè)置leader, 用DFS在m時間內(nèi)求出 檢查每條邊一次以修正各分量的安全邊權(quán) 第i次迭代每個分量大小至少為2i 最多l(xiāng)ogV次迭代, 總O(ElogV) 13 三、三、Prim算法算法 1

4、4 Prim算法 Prim提出, 但事實上Jarnik于1930于年更早提出 只關(guān)心一棵樹T, 每次加入T的安全邊 用堆保存到每個頂點(diǎn)(而非邊)的安全邊 Insert/ExtractMin調(diào)用V次, DecreaseKey調(diào)用E次 二叉堆: O(E+V)logV), Fibonacci堆: O(E+VlogV) 15 16 練習(xí) 給定鄰接矩陣, 設(shè)計一個O(V2)算法 對于稀疏圖中, 用k次Boruvka迭代可以加速 MST計算. 如何選取k, 使得k次迭代以后調(diào) 用Prim算法的時間復(fù)雜度變?yōu)镺(EloglogV) 17 四、四、Kruskal算法算法 18 Kruskal算法 Kruska

5、l, 1956年提出 把邊從小到大排序, 每次填加一個安全邊 如何知道邊是否安全? 并查集, 每次約O(1) 總O(ElogE + E(V) 19 20 21 練習(xí) Kruskal返回的MST和邊排序結(jié)果有關(guān). 證 明對于任何一個MST, 都有一個排序方法使 得Kruskal返回此MST 如果邊權(quán)為1|V|的整數(shù), Kruskal的時間復(fù) 雜度如何? 如果邊權(quán)在0, 1)上均勻分布, Kruskal和 Prim哪個算法更快? 計算出MST后, 如果加一個頂點(diǎn)和它所關(guān)聯(lián) 的邊, 如何快速更新MST? 22 五、五、MST唯一性判定唯一性判定 23 MST唯一性判定 考慮一般最小生成樹算法 每一個分量出發(fā)安全邊唯一, 不特殊處理, 否則 若同時添加會形成環(huán), 一定不唯一 若同時添加不會形成環(huán), 類似正確性證明, 即: 假設(shè)某邊e不在T中, 對應(yīng)的e一定比e大而不可能相等 24 MST唯一性判定 時間復(fù)雜度 Boruvka: 不變(只在和安全邊比較時修改) Prim: 不變(只在判斷頂點(diǎn)標(biāo)號時修改) Kruskal: 不變(相等的邊時特殊處理) 另一種思路: 最小=第二小 25 六、瓶頸生成樹六、瓶頸生成樹 26 基本問題 邊的最大值最小的生成樹成為G的瓶頸生成 樹(bottleneck spanning tree), 把其中最大 的邊稱為它的權(quán). 顯然, MST是一