https://wiki.taigi.ima.org.tw/w/index.php?action=history&feed=atom&title=%E5%85%8B%E9%AD%AF%E6%96%AF%E5%85%8B%E7%88%BE%E6%BC%94%E7%AE%97%E6%B3%95
克魯斯克爾演算法 - 修訂紀錄
2026-05-19T11:30:50Z
本 wiki 上此頁面的修訂紀錄
MediaWiki 1.43.1
https://wiki.taigi.ima.org.tw/w/index.php?title=%E5%85%8B%E9%AD%AF%E6%96%AF%E5%85%8B%E7%88%BE%E6%BC%94%E7%AE%97%E6%B3%95&diff=444037&oldid=prev
TaiwanTonguesApiRobot：從 JSON 檔案批量匯入
2025-08-22T23:36:53Z
<p>從 JSON 檔案批量匯入</p>
<p><b>新頁面</b></p><div>'''Kruskal 演算法'''是一種用來走揣上小生成樹仔的演算法，由 Joseph Kruskal 佇咧一九五六年發表。用來解決仝款問題的猶閣有 Prim 演算法佮 Boruvka 演算法等。三種演算法攏是貪婪演算法的應用。和 Boruvka 演算法無仝的所在是，Kruskal 演算法佇圖中存在仝款權值的邊仔的時陣嘛有效。<br />
<br />
==撇步==<br />
<br />
一 . 新建圖 $ G $，$ G $ 中擁有原圖中相仝的節點，伊無邊二 . 共原圖中所有的那揤權值自細漢到大漢排序三 . 對權值上細漢的邊仔開始，若這條邊連接的兩个節點於圖 $ G $ 著無仝一个連通的量內底，則添加這條邊到圖 $ G $ 中四 . 重複三，直至圖 $ G $ 中所有的點仝款攏佇咧連通分開中<br />
<br />
==證明==<br />
<br />
一 . 這款的撇步保證矣選取的逐條邊攏是橋，所以圖 $ G $ 鹿仔成一个樹。<br />
二 . 為啥物這一定是上小生仔唅？關鍵猶閣是行三中對邊的選取。演算法中攏總選取矣 $ n 影一 $ 條邊，逐條邊咧選取的彼當陣，攏是連接兩个無仝的連通分量的權值上細的邊仔三 . 欲證明這條邊一定屬於上小生成樹，會當用反證法：若這條邊無佇細漢的樹仔內底，伊連接的兩个連通分開終猶是愛連起來的，通過其他的連法，遮另外一種連法佮這條邊仔一定構成矣環，若環中一定有一條權值大過這條邊的邊仔，用這條邊仔共換掉，猶原保持連通，但是總權值減細矣。也就是講，若無選這條邊，落尾手構成的成樹的總權值一定袂是上細的。<br />
<br />
==時間複雜度==<br />
<br />
通過使用路徑壓縮的併查集，平均時間複雜度做 $ O ( | E | \ log | V | ) $，其中 $ E $ 和 $ V $ 分別是圖的邊集佮點集。<br />
<br />
此外，若同時使用路徑壓縮佮揤秩合併，時間複雜度會當最佳化甲 $ O ( | E | \ alpha ( | V | ) ) $，其中 $ \ alpha $ 表示反阿克曼函數。<br />
<br />
==範例==<br />
<br />
==虛擬碼==<br />
<br />
` ` `<br />
KRUSKAL-FUNCTION ( G , w )<br />
一 F :=空集合二'''for each'''圖 G 中的頂點 v<br />
三'''do'''將 v 加入去森林 F<br />
四所有的邊 ( u , v ) ∈ E 依權重 w 遞增排序五'''for each'''邊 ( u , v ) ∈ E<br />
六'''do if'''u 和 v 無仝一欉樹仔七'''then'''F :=F ∪ { ( u , v ) }<br />
八將 u 和 v 所在的子樹合做伙<br />
` ` `<br />
<br />
==參考源程式==<br />
<br />
===C + + 實現===<br />
<br />
以下代碼基於路徑壓縮佮揤秩合併的併查集，時間複雜度 $ O ( | E | \ alpha ( | V | ) ) $。<br />
<br />
==參考文獻==<br />
<br />
[[分類: 待校正]]</div>
TaiwanTonguesApiRobot