最小生成树问题（Minimum Spanning Tree - MST）

Minimum Spanning Trees —— 最小生成树

树是特殊的图（树不能有回路，必须是连通图），就像之前说的，关于树的题都可以通过图的解题思路去做。
* Trees are connected(连通的) acyclic(无环的) undirected(无向的) graphs *** 树的性质：
**一个n节点的树，一定有n-1条边。当边数大于n-1，那么图一定有环存在；当边数小于n-1，那么图一定不连通

## 生成树 输入：一个连通的无向图
求：图中包含的子图，

1. 子图必须包含图中所有n个节点，
2. 但是只保留n-1条边，
3. 这些边要使这个图具有连通性。

此时得到的子图就是生成树

最小生成树算法

在上述生成树中，图四是最小生成树，而大部分时候，我们需要求的就是最小生成树，它的实际应用可以在工程修路中体现，例如我们需要在土路的基础上修高速以到达每个城市，但是每个城市之间有很多条土路，那么最小生成树就是总距离最短的修建方案。 目前常见的有prim算法以及kruscal算法

具体算法详见其分文档

• 图论
• 最小生成树
• mst
• prim
• kruskal
• 并查集
• 贪心算法