Aloha！又是我少女人妻 Uerica！終於來到第 20 天了 (歡呼)，已經過了三分之二了～人說頭過身就過，看來我們現在已經過到屁股啦！真是太棒了～

生成樹 Spanning Tree

前面有提到，樹為圖形結構的一種，在圖形結構中，我們會看到每個節點會有多個邊相連，就像地圖上 A 點到 B 點會有很多路徑可到達。而生成樹的意思是將圖形上每個節點與節點間只有一個邊，且沒有環的情況下相連，若有 n 個節點，那生成樹則會有 n-1 個邊。生成樹的權重為每條邊的權重總和。

最小生成樹 Minimum Spanning Tree, MST

最小生成樹意思是取權重最小的邊來連接節點，如上述所提到，地圖上有很多個點，點與點之間也有多個路徑可前往，而用最短的路徑通往所有點，且不重複，就是最小生成樹的概念。以下就來說明哪些演算法可以用來尋找最小生成樹。

常見尋找 MST 的演算法

某天灰姑娘搬到新城鎮，最近跟王子談戀愛的灰姑娘，因為午夜 12 點總是被自動卸妝跟打回原形，所以只好把常去的地點及路線時間都標出來，為的就是找出點與點之間最近的路線，之後不管在哪個地方約會，都能在眉毛跟胸墊被消失前躲到其他的建築物去 XD！每天都跟王子玩午夜躲貓貓～

克魯斯克爾演算法 Kruskal's algorithm

克魯斯克爾演算法的方式是，先將所有邊的權重做排序，並從小到大開始選擇，比對是否行程迴圈，若無則放入最小生成樹的集合中。

• 首先將所有路線時間從小到大排序好

• 從最短時間的路徑開始選擇，地圖上最短路線是 Castle 到 Bar
  

• 第二個最短時間路線是 Store 到 Home
  

• 第三個最短時間路線是 Shop 到 Stroe
  

• 第四個最短時間路線是 Bar 到 Stroe
  

• 再來第五個最短時間路線是 Home 到 Shop，但此時已經形成環所以不考慮這條路線。
  

• 於是再下一個最短時間路線是 Home 到 Bank
  

• 其他的路線都會形成環，所以不考慮
  

• 最後的路線是這樣，太棒了～以後灰姑娘不管在哪裡被打回原形，都能快速的跑到其他的建築物躲起來了！
  

普林演算法 Prim's algorithm

普林演算法的方式是，隨意選定一個節點當頂點，從頂點開始延伸選擇最小的邊連接的節點放入最小生成樹的集合中，再將形成的生成樹所連接到的節點，選擇最小的邊所連接的節點，一直反覆操作並比對是否形成迴圈，直到最小生成樹確實放入所有節點為止。

• 隨機選擇一個根節點當出發點，這邊就選灰姑娘的家 Home 吧
  

• 從 Home 可以走到的地方有 Bank 、 Store 、 Shop，三個地方
  

• 選擇當中最短時間路線，Home 到 Store
  

• 再來標出 Stroe 可以走到的所有路線，有 Bank 、 Bar 、 Castle、Shop
  

• 再從標出的路線選出最短時間路線，如下圖選了 Shop 到 Store
  

• 在把 Shop 可以到的路線標示出
  

• 再選擇最短時間路線，Bar 到 Store
  

• 再選擇最短時間路線， Home 到 Shop 的路線因爲會形成環所以不考慮
  

• 下一個最短時間路線是 Home 到 Bank
  

• 其他路線因為都會形成環所以不考慮
  

• 若權重都不同，結果是一樣的，只有唯一一個最小生成樹
  

參考資料：
最小生成樹演算法【圖解】--一文帶你理解什麼是Prim演算法和Kruskal演算法

演算法筆記：Spanning Tree

Minimum Spanning Tree：Prim's Algorithm

好啦！今天就先到這邊了，感謝閱讀！大家明天見啦～掰掰