圖形演算法-最小生成樹- 高中資訊科技概論教師黃建庭的教學網站

本節介紹Kruskal的最小生成樹演算法，因為這個演算法較容易實作，Kruskal演算法由最小的邊出發，找出最小不形成循環的邊，直到邊的個數為點的個數少1，就找到最小生成 ... 高中資訊科技概論教師黃建庭的教學網站搜尋這個協作平台 黃建庭的教學網站新版黃建庭教學網站高三資訊課程108資訊科技基礎C++與PythonPython程式設計Python與資料分析C++演算法解題(1)C++演算法解題(2)機器學習教學平台ZSOJ資訊能力競賽考古題資訊能力檢定APCSRaspberry樹莓派ArduinoArduino與Scratch2FreeBSD/Linux筆記網管筆記AppInventor2Scratch2PHP程式設計JavaScript程式設計107資訊科技概論程式設計--使用機器人micro:bitAmeba3D列印JetBotDjangoLXR軟體使用心得相簿學生榮譽榜學經歷與著作與我聯絡連結高中生程式解題系統(zerojudge)UvaOnlineJudge資訊之芽(fb)Bebras系統管理新聞協作平台地圖最新協作平台活動 FreeHitCounter 版權宣告學校上課使用，可不標記作者 黃建庭的教學網站‎>‎C++演算法解題(2)‎>‎ 圖形演算法-最小生成樹 最小生成樹(MinimumSpanningTree) 在無向圖有權重的連通圖中找尋可以連接所有點的邊且不形成循環，且這些邊的權重和最小，可以連通所有點且不形成循環，一定會形成樹，這樣的問題稱作最小生成樹(MinimumSpanningTree)。

本節介紹Kruskal的最小生成樹演算法，因為這個演算法較容易實作，Kruskal演算法由最小的邊出發，找出最小不形成循環的邊，直到邊的個數為點的個數少1，就找到最小生成樹。

使用Kruskal演算法找出最小生成樹 以下圖為例，進行Kruskal演算法的解說。

如何判斷是否選取的邊形成循環？這時需要使用集合的概念，剛開始每一個點都是一個集合，每個集合都只有一個元素，當加入最小生成樹的邊，邊的兩端點節點屬於同一個集合，就會形成循環，該邊不能是最小生成樹的邊。

Step1)將最小邊(3,5)加入最小生成樹，將點3與點5屬於不同的集合，且都是只有一個元素的集合，所以{3}與{5}進行聯集形成一個新集合{3,5}。

Step2)將最小邊(1,2)加入最小生成樹，將點1與點2屬於不同的集合，且都是只有一個元素的集合，所以{1}與{2}進行聯集形成另一個集合{1,2}，目前集合有{3,5}與{1,2}。

Step3)將最小邊(0,2)加入最小生成樹，將點0與點2屬於不同的集合，所以{0}與{1,2}進行聯集形成另一個集合{0,1,2}，目前集合有{3,5}與{0,1,2}。

Step4)將最小邊(0,1)加入最小生成樹，點0與點1都屬於集合{0,1,2}，如果加入邊(0,1)則會形成循環，所以不能加入邊(0,1)，目前集合有{3,5}與{0,1,2}。

Step5)將最小邊(2,3)加入最小生成樹，點2與點3屬於不同的集合，所以{0,1,2}與{3,5}進行聯集形成另一個集合{0,1,2,3,5}，目前集合有{0,1,2,3,5}。

Step6)將最小邊(3,4)加入最小生成樹，點3與點4屬於不同的集合，所以{0,1,2,3,5}與{4}進行聯集形成另一個集合{0,1,2,3,4,5}，目前集合有{0,1,2,3,4,5}，到此完成 最小生成樹。

(一)最小生成樹 給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，每個邊的權重為正整數，相同起點與終點的邊只有一個，請找出最小生成樹的邊權重和。

輸入說明 輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊有三個數字，前兩個數字為邊的兩端點節點編號與最後一個數字為邊的權重，保證節點編號由0到(n-1)。

輸出說明 輸出最小生成樹的邊權重和。

範例輸入 69 016 025 0311 0416 123 237 2510 349 352 範例輸出 26 (a)解題想法 將所有邊的節點與權重，輸入到陣列edge，將陣列edge依照w由小到大排序，由小到大依序取出每一個邊，使用陣列parent記錄節點的上一層節點編號，有相同根節點的節點編號，表示同一個集合，若取出最小邊的兩端點，由陣列parent來判斷是否在同一個集合內，若有相同的根節點節點編號，表示同一個集合，加入此邊會形成循環，該邊不是最小生成樹的邊；若有不同的根節點節點編號，表示兩端點不在同一個集合內，加入此邊不會形成循環，該邊是最小生成樹的邊，接著更改陣列parent，集合元素個數越多者要放在上面，這樣由陣列parent往上找根節點才能在較少比較次數內完成，程式會有較佳的效率。

(b)程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include usingnamespacestd; structEdge{ intx; inty; intw; }; Edgeedge[5000]; intnum[100],parent[100]; boolcmp(Edgea,Edgeb){ returna.w>n>>m){ for(inti=0;i>edge[i].x>>edge[i].y>>edge[i].w; } for(inti=0;inum[b]){ parent[b]=a; num[a]+=num[b]; }else{ parent[a]=b; num[b]+=num[a]; } result+=edge[i].w; numEdge++; } } if(numEdge==(n-1))cout<編譯並執行」，結果顯示在螢幕如下。

(二)連接圖形所有點的最短距離 給定最多100個節點以內XY平面的點座標，表示一個國家的城市個數，假設要找出連接這些城市的道路，且道路可以取任兩點的直線距離進行建置，道路的成本與道路的距離成正比，請幫這個國家找出讓這些城市可以連接起來的道路最短距離。

輸入說明 輸入正整數n，表示有n個城市，接下來有n行，每一行有兩個數值，表示一個城市所在平面的X與Y座標值，座標值可以是浮點數。

輸出說明 輸出將n個城市連接起來的道路最短距離。

範例輸入 5 0.00.0 2.02.0 4.03.0 5.05.0 2.05.0 範例輸出 10.129 (a)解題想法 將所有邊的節點與權重，輸入到陣列edge，將陣列edge依照w由小到大排序，由小到大依序取出每一個邊，使用陣列parent記錄節點的上一層節點編號，有相同根節點的節點編號，表示同一個集合，若取出最小邊的兩端點，由陣列parent來判斷是否在同一個集合內，若有相同根節點的節點編號，表示同一個集合，加入此邊會形成循環，該邊不是最小生成樹的邊；若有不同的根節點節點編號，表示兩端點不在同一個集合內，加入此邊不會形成循環，該邊是最小生成樹的邊，最後更改陣列parent，集合元素個數越多者要放在上面，這樣由陣列parent往上找根節點才能在較少比較次數內完成。

(b)程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64#include #include #include usingnamespacestd; structEdge{ intx; inty; doublew; }; Edgeedge[5000]; doublex[100],y[100]; boolcompare(Edgea,Edgeb){ returna.w>n){ for(inti=0;i>x[i]>>y[i]; } s=0; for(inti=0;inum[b]){ parent[b]=a; num[a]+=num[b]; }else{ parent[a]=b; num[b]+=num[a]; } result+=edge[i].w; numEdge++; } } if(numEdge==(n-1)){ cout<編譯並執行」，結果顯示在螢幕如下。

Comments Signin|RecentSiteActivity|ReportAbuse|PrintPage|PoweredByGoogleSites