第七講 最小生成樹課件

《算法藝術與信息學競賽》

教學幻燈片算法圖論第七講最小生成樹第七講最小生成樹聲明本系列教學幻燈片屬于劉汝佳、黃亮著《算法藝術與信息學競賽》配套幻燈片本幻燈片可從本書blog上免費下載，即使您并未購買本書.若作為教學使用，歡迎和作者聯(lián)系以取得技術支持，也歡迎提供有不同針對性的修改版本，方便更多人使用有任何意見，歡迎在blog上評論Blog地址：第七講最小生成樹內容介紹一、最小生成樹問題二、Boruvka算法三、Prim算法四、Kruskal算法五、MST唯一性判定六、瓶頸生成樹第七講最小生成樹參考資料CLRSChapter23.MinimalSpanningTrees第七講最小生成樹一、最小生成樹問題(MST)第七講最小生成樹定義連接每個點的連通圖（一定是樹）權和盡量小第七講最小生成樹一般最小生成樹算法前提:無相等邊維護生成森林Fe為無用邊,若e的兩個端點在F的同一個分量中,但e不在F中對于F的每一個分量從它出去(即恰好有一個端點在此分量內)的最小邊為安全邊不同的分量可以有相同的安全邊結論:MST含有所有安全邊,不含無用邊.第七講最小生成樹一般最小生成樹算法結論:MST含有所有安全邊,不含無用邊.證明假設有一個分量(黃色),它的安全邊e不在T內.則u到v有唯一路徑,它經過e’,它恰好有一個端點在黃色分量中.由于e是安全邊,w(e)<w’(e),用e替換e’得到更小的T’,矛盾加入無用邊將形成環(huán)第七講最小生成樹練習證明最小邊屬于某棵MST中對于某環(huán)上的最大邊e,證明原圖中刪除e后的MST和原來的相同在圖中減小一個邊的權,求新的MST情況一:e在原MST中情況二:e不在原MST中第七講最小生成樹二、Borovka算法第七講最小生成樹Boruvka算法由Boruvka于1926年提出(早于圖論產生!)第七講最小生成樹Boruvka算法每個分量設置’leader’,用DFS在m時間內求出檢查每條邊一次以修正各分量的安全邊權第i次迭代每個分量大小至少為2i最多l(xiāng)ogV次迭代,總O(ElogV)第七講最小生成樹三、Prim算法第七講最小生成樹Prim算法Prim提出,但事實上Jarnik于1930于年更早提出只關心一棵樹T,每次加入T的安全邊用堆保存到每個頂點(而非邊)的安全邊Insert/ExtractMin調用V次,DecreaseKey調用E次二叉堆:O((E+V)logV),Fibonacci堆:O(E+VlogV)第七講最小生成樹第七講最小生成樹練習給定鄰接矩陣,設計一個O(V2)算法對于稀疏圖中,用k次Boruvka迭代可以加速MST計算.如何選取k,使得k次迭代以后調用Prim算法的時間復雜度變?yōu)镺(EloglogV)第七講最小生成樹四、Kruskal算法第七講最小生成樹Kruskal算法Kruskal,1956年提出把邊從小到大排序,每次填加一個安全邊如何知道邊是否安全?并查集,每次約O(1)總O(ElogE+Eα(V))第七講最小生成樹第七講最小生成樹第七講最小生成樹練習Kruskal返回的MST和邊排序結果有關.證明對于任何一個MST,都有一個排序方法使得Kruskal返回此MST如果邊權為1…|V|的整數,Kruskal的時間復雜度如何?如果邊權在[0,1)上均勻分布,Kruskal和Prim哪個算法更快?計算出MST后,如果加一個頂點和它所關聯(lián)的邊,如何快速更新MST?第七講最小生成樹五、MST唯一性判定第七講最小生成樹MST唯一性判定考慮一般最小生成樹算法每一個分量出發(fā)安全邊唯一,不特殊處理,否則若同時添加會形成環(huán),一定不唯一若同時添加不會形成環(huán),類似正確性證明,即:假設某邊e不在T中,對應的e’一定比e大而不可能相等第七講最小生成樹MST唯一性判定時間復雜度Boruvka:不變(只在和安全邊比較時修改)Prim:不變(只在判斷頂點標號時修改)Kruskal:不變(相等的邊時特殊處理)另一種思路:最小=第二小第七講最小生成樹六、瓶頸生成樹第七講最小生成樹基本問題邊的最大值最小的生成樹成為G的瓶頸生成樹(bottleneckspanningtree),把其中最大的邊稱為它的權.顯然,MST是一個瓶頸生成樹,但是瓶頸生成樹