文章首发于：My Blog 欢迎大佬们前来逛逛

最小生成树的定义 在一张带权无向图中，最小生成树是一棵生成树，它的边权值之和最小。

生成树是一颗包含原图中所有顶点的树，它的边集合是原图的一个子集，且任意两个顶点之间都有且仅有一条简单路径。

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

Kruskal算法 Kruskal算法的主要思想是按照边权值从小到大依次选择边，如果这条边的两个端点不在同一个连通块中，就把这条边加入到最小生成树的边集合中。 具体实现步骤：

（1）将所有边按照边权值从小到大排序。

（2）从小到大依次选择每一条边，如果这条边的两个端点不在同一个连通块中，就把这条边加入到最小生成树的边集合中，并合并这两个连通块。

（3）重复步骤（2），直到最小生成树中有n-1条边为止。 Kruskal算法的时间复杂度为O(mlogm)，其中m为图中的边数。

Kruskal算法存储每一条边（不是双向边），并且还需要对于每个节点的辅助数组，因此对于边和点的数据类型的范围应该这样定义：

Kruskal算法适合于稀疏图