【在廚房想30天的演算法】Day 20 演算法: 最小生成樹MST ...

克魯斯克爾演算法Kruskal's algorithm ... 克魯斯克爾演算法的方式是，先將所有邊的權重做排序，並從小到大開始選擇，比對是否行程迴圈，若無則放入最小生成 ... 2021iThome鐵人賽 DAY 20 0 SoftwareDevelopment 少女人妻在廚房裡想不通的演算法系列第 20篇 【在廚房想30天的演算法】Day20演算法:最小生成樹MSTKruskal、Prim 13th鐵人賽 少女人妻Uerica 團隊一隻狗狗發大財 2021-10-0518:45:50489瀏覽 Aloha！又是我少女人妻Uerica！終於來到第20天了(歡呼)，已經過了三分之二了～人說頭過身就過，看來我們現在已經過到屁股啦！真是太棒了～ 生成樹SpanningTree 前面有提到，樹為圖形結構的一種，在圖形結構中，我們會看到每個節點會有多個邊相連，就像地圖上A點到B點會有很多路徑可到達。

而生成樹的意思是將圖形上每個節點與節點間只有一個邊，且沒有環的情況下相連，若有n個節點，那生成樹則會有n-1個邊。

生成樹的權重為每條邊的權重總和。

最小生成樹MinimumSpanningTree,MST 最小生成樹意思是取權重最小的邊來連接節點，如上述所提到，地圖上有很多個點，點與點之間也有多個路徑可前往，而用最短的路徑通往所有點，且不重複，就是最小生成樹的概念。

以下就來說明哪些演算法可以用來尋找最小生成樹。

常見尋找MST的演算法 某天灰姑娘搬到新城鎮，最近跟王子談戀愛的灰姑娘，因為午夜12點總是被自動卸妝跟打回原形，所以只好把常去的地點及路線時間都標出來，為的就是找出點與點之間最近的路線，之後不管在哪個地方約會，都能在眉毛跟胸墊被消失前躲到其他的建築物去XD！每天都跟王子玩午夜躲貓貓～ 克魯斯克爾演算法Kruskal'salgorithm 克魯斯克爾演算法的方式是，先將所有邊的權重做排序，並從小到大開始選擇，比對是否行程迴圈，若無則放入最小生成樹的集合中。

首先將所有路線時間從小到大排序好 從最短時間的路徑開始選擇，地圖上最短路線是Castle到Bar 第二個最短時間路線是Store到Home 第三個最短時間路線是Shop到Stroe 第四個最短時間路線是Bar到Stroe 再來第五個最短時間路線是Home到Shop，但此時已經形成環所以不考慮這條路線。

於是再下一個最短時間路線是Home到Bank 其他的路線都會形成環，所以不考慮 最後的路線是這樣，太棒了～以後灰姑娘不管在哪裡被打回原形，都能快速的跑到其他的建築物躲起來了！ 普林演算法Prim'salgorithm 普林演算法的方式是，隨意選定一個節點當頂點，從頂點開始延伸選擇最小的邊連接的節點放入最小生成樹的集合中，再將形成的生成樹所連接到的節點，選擇最小的邊所連接的節點，一直反覆操作並比對是否形成迴圈，直到最小生成樹確實放入所有節點為止。

隨機選擇一個根節點當出發點，這邊就選灰姑娘的家Home吧 從Home可以走到的地方有Bank、Store、Shop，三個地方 選擇當中最短時間路線，Home到Store 再來標出Stroe可以走到的所有路線，有Bank、Bar、Castle、Shop 再從標出的路線選出最短時間路線，如下圖選了Shop到Store 在把Shop可以到的路線標示出 再選擇最短時間路線，Bar到Store 再選擇最短時間路線，Home到Shop的路線因爲會形成環所以不考慮 下一個最短時間路線是Home到Bank 其他路線因為都會形成環所以不考慮 若權重都不同，結果是一樣的，只有唯一一個最小生成樹 參考資料： 最小生成樹演算法【圖解】--一文帶你理解什麼是Prim演算法和Kruskal演算法 演算法筆記：SpanningTree MinimumSpanningTree：Prim'sAlgorithm 好啦！今天就先到這邊了，感謝閱讀！大家明天見啦～掰掰 留言 追蹤 檢舉 上一篇 【在廚房想30天的演算法】Day19演算法:圖形搜尋graphsearch廣度搜尋、深度搜尋 下一篇 【在廚房想30天的演算法】Day21演算法:最短路徑ShortestPathDijkstra演算法 系列文 少女人妻在廚房裡想不通的演算法 共30篇 目錄 RSS系列文 訂閱系列文 12人訂閱 26 【在廚房想30天的演算法】Day26資訊安全與演算法:混成金鑰密碼系統 27 【在廚房想30天的演算法】Day27資訊安全與演算法:迪菲-赫爾曼密鑰交換 28 【在廚房想30天的演算法】Day28資訊安全與演算法:訊息鑑別碼 29 【在廚房想30天的演算法】Day29資訊安全與演算法:數位簽章 30 【在廚房想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}} 關閉