Day 23：最小生成樹(MST) - iT 邦幫忙

Kruskal演算法的方式是從所有邊中，反覆選擇最短的邊，它的步驟是： ... 如下圖，先將邊排序，依序選擇，其中邊be即是因為會形成環所以不選。

2021iThome鐵人賽 DAY 23 0 自我挑戰組 30天不怕演算法：白話文版系列第 23篇 Day23：最小生成樹(MST) 13th鐵人賽 演算法 salmon_simpson 2021-10-0612:37:56635瀏覽 貪婪演算法可以解決的一個問題就是找到一張圖中的最小生成樹(minimumspanningtree)。

樹、生成樹與最小生成樹 我們之前提到資料結構中的樹是有根樹(rootedtree)，也就是樹中有一個根節點。

但其實樹不一定都有根節點，只要任意兩節點都有(也只有)一條邊相連的圖就稱作樹。

圖片來源：維基百科 而一個圖中的生成樹(spanningtree)，就是指連接該圖所有節點的樹，一個圖可能有不只一個生成樹。

而最小生成樹就是指在有權圖中，權重總和最小的生成樹。

例如下圖中綠色的部分，就是這個圖的最小生成樹。

圖片來源：維基百科 那麼最小生成樹可以解決什麼問題呢？其中一種最直接的應用是線路設計，例如沿著街道(邊)為住家(節點)架設電纜的情境，最小生成樹可以作為成本最低的路徑。

另外，最小生成樹也可以用來作為困難問題的近似解，或間接應用在人臉或字跡辨識等技術中。

貪婪解法 有許多演算法可以找到一個圖中的最小生成樹，下面寫到的幾種都是屬於貪婪演算法。

這幾種方法雖然關注點或出發點不同，但同樣都是用貪婪策略，每一階段都選擇局部最佳解，以達到最終的整體最佳解。

也表現出之前提到的，一個問題可能以多種貪婪演算法解決。

Prim'salgorithm 普林演算法的策略與先前提到尋找最短路徑的Dijkstra演算法非常相似(事實上這個演算法也被Dijkstra再次發現與發表，所以也稱為Prim–Dijkstraalgorithm)，它的作法是： 先將任意節點加入到樹之中。

選擇與樹距離最近的節點，加入到樹中，反覆此步驟直到所有節點均在樹中，即為最小生成樹。

以上方的圖為例，如果一開始選擇G節點，接下來將最近的節點E加入樹中，接下來將與G或E最近的節點C加入...以此類推，也就是每一階段樹都會納入距離最近的節點、增加一條邊，直到連接所有的節點。

Kruskal'salgorithm Kruskal演算法的方式是從所有邊中，反覆選擇最短的邊，它的步驟是： 將所有的邊依照權重由小到大排序。

從最小開始，選擇不會形成環的邊，直到連接所有節點。

如下圖，先將邊排序，依序選擇，其中邊be即是因為會形成環所以不選。

圖片來源：維基百科 Borůvka'salgorithm Borůvka演算法則是利用節點的最短邊得出多棵樹，再將樹以最短邊相連： 找尋每個節點的最短邊，可以重複選擇(例如下圖AC同時是A節點和C節點的最短邊)，如此一來會形成幾個不相連的樹，如下圖中經過第一步驟後得到AC、BD、EF等不同的樹，以不同顏色標示。

以同樣的方式，反覆找尋每個樹的最短邊，每次操作樹的數量都會減少，直到最終只剩下一個樹即為最小生成樹。

圖片來源：維基百科 留言 追蹤 檢舉 上一篇 Day22：貪婪演算法(2) 下一篇 Day24：霍夫曼編碼(Huffmancoding) 系列文 30天不怕演算法：白話文版 共30篇 目錄 RSS系列文 訂閱系列文 5人訂閱 26 Day26：旅行推銷員問題(TSP) 27 Day27：碰到困難問題，演算法也救不了？ 28 Day28：Diffie–Hellman演算法 29 Day29：K-近鄰演算法(k-nearestneighbors) 30 Day30：寫在不怕演算法之後 完整目錄 尚未有邦友留言 立即登入留言 iT邦幫忙鐵人賽 參賽組數 1087組 團體組數 52組 累計文章數 20485篇 完賽人數 572人 鐵人賽最新文章 資料驗證(golang)(Day23) .NetCoreWebApi_筆記22_Swagger自訂文件並讀取API註解描述 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【Day31】新加坡工作後續的時程 重構原本的內容(golang)(Day22) Laravel-jQueryAJAX範例 2022/1/2更新 .NetCoreWebApi_筆記21_Swagger及OpenAPI介紹與配置使用方式_API管理與測試探討 .NetCoreWebApi_筆記20_api結合ADO.NET資料庫操作part8_新聞文章查詢 前往鐵人賽 技術推廣專區 [Day2]抓取每日收盤價 [Day1]基本工具安裝 利用python取得永豐銀行API的Nonce [Day03]tinyML開發板介紹 永豐金融API測試員 [Day01]在享受tinyML這道美食之前 [Day3]使用ta-lib製作指標 [Day4]函數打包與買進持有報酬率試算 計算API所需要的參數:HashID 計算API所需要的參數:IV 前往鐵人賽 熱門問題 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 40人小公司用的郵件伺服器 急救！將ImageView傳到另一個頁面 關於團隊合作 正航ERP相關問題 資安宣導文案 請問有哪位好心人能借一下百度帳號... 請教SQL大師，如何在GROUPBY分群裡找出組別最多筆數量的組別名稱 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) IT邦幫忙 站方公告 【2021iThome鐵人賽】登登登！究竟獎落誰家，2021iThome鐵人賽得獎名單正式揭曉 熱門tag 看更多 13th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 windows php python windowsserver linux c# 程式設計 資訊安全 css vue.js sql 分享 熱門回答 40人小公司用的郵件伺服器 關於團隊合作 資安宣導文案 SVN版本控制的選擇 python檔案計算問題 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) 正航ERP相關問題 為什麼Visualstudio查詢資料庫資料會顯示 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 熱門文章 【Day31】新加坡工作後續的時程 2021法遵科技與電腦稽核專題競賽-賀雲科大、逢甲、北商大、中正、致理科大、亞洲科大等學校隊伍獲獎，培育智慧法遵與AI稽核人才邁向國際~ Laravel-jQueryAJAX範例 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【徵才】台北中山區-知名航空貨運-資訊網管人員 重構原本的內容(golang)(Day22) 科學家與研究生的關係研究篇 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 30天Python自學:Day01 印表機維修五種常見故障，若遇到問題就能先自己排除了 一週點數排行 更多點數排行 海綿寶寶(antijava) Gary(mosbbs) raytracy(raytracy) 一級屠豬士(hitomitanaka) Samuel(kuanyu) ccenjor(ccenjor) 居然解出來了(partyyaya) horace_work(horace_work) 純真的人(jer5173) souda(souda) × At 輸入對方的帳號或暱稱 Loading 找不到結果。

標記 {{result.label}} {{result.account}} 關閉