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

好啦！今天就先到这边了，感谢阅读！大家明天见啦～掰掰