数据结构-最小生成树算法

最小生成树算法是解决图的最小生成树问题的一种算法。最小生成树问题是指在一个连通无向图中找到一棵包含所有顶点的生成树，并且这棵树的边权之和最小。

最常用的两种最小生成树算法是Prim算法和Kruskal算法。

Prim算法从一个初始顶点开始，每次选择与当前生成树连接的权值最小的边所对应的顶点，并将其加入生成树。然后再从新加入的顶点开始，重复上述过程，直至所有顶点都加入生成树，形成最小生成树。

Kruskal算法则是先将所有边按权值从小到大排序，然后按顺序选取权值最小的边，如果这条边的两个顶点不在同一个连通分量中，则将这条边加入生成树，并将这两个连通分量合并。

最小生成树算法具有以下三个性质：
1. 最小生成树是树，边数等于顶点数减1，并且树内一定不会有环。
2. 对给定的图G(V, E)，其最小生成树可以不唯一，但其边权之和是唯一的。
3. 最小生成树是在无向图上生成的，因此其根节点可以是在这棵树上的任意一个顶点。