一个连通图可能有多棵生成树，而最小生成树是一副连通加权无向图中一颗权值最小的生成树，它可以根据prim算法和kruskal算法得出，这两个算法分别从点和边的角度来解决。
输入：一个加权连通图，其中顶点集合为v，边集合为e；
初始化：vn = {x}，其中x为集合v中的任一节点（起始点），enew = {}；
重复下列操作，直到vn = v：（在集合e中选取权值最小的边（u, v），其中u为集合vn中的元素，而v则是v中没有加入vn的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将v加入集合vn中，将（u, v）加入集合en中；）
输出：使用集合vn和en来描述所得到的最小生成树。
以下面这张图作为例子，表格中的vertex、kown、cost、path分别表示顶点信息、是否访问过，权值，到达路径；
我们随机的选择顶点0作为起点，其执行步骤为：
步骤
选中结点
顶点0作为起始点
根据(6, 7, 8)的方案选中6
1
根据顶点1能够到达的权值(7, 4, 3)和顶点0能够到达的权值(7, 8)中选择3
5
根据顶点5能够到达的权值(8)和根据顶点1能够到达的权值(7, 4)和顶点0能够到达的权值(7, 8)中选择4
6
根据顶点6能够到达的权值(6, 7)和顶点0能够到达的权值(7)中选择6
2
根据顶点0能够到达的权值(7)和顶点6能够到达的权值(7)中选择7
4
根据顶点6能够到达的权值(7)选择7
7
根据顶点7能够到达的权值(2)选择2
3
全部结点都访问过，退出
最终得到下面的结果，其中path中的-1表示其作为起始点；
根据前面的那幅图来实现，如下：
path结果为：[-1, 0, 6, 7, 0, 1, 1, 6]
构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树的根节点，则它是一个含有n棵树的森林 。之后，从图的边集中选取一条权值最小的边，若该边的两个顶点分属不同的树 ，则将其加入子图，也就是这两个顶点分别所在的 两棵树合成一棵树；反之，若该边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林只有一棵树。kruskal算法能够在并查集的基础很快的实现。
以下面这张图作为例子，其中左边的表格是一个并查集，表示可以连通的结点。我们首先要根据权值对每条边进行排序，接着开始处理每一条边的情况。
最终得到下面的结果图：
因为我们要处理边，所以需要建立边的数据结构，并且要从给定的图中获取每一条边的数据。
接下来就是kruskal函数：
其中union打印出来的结果和图中是一致的，为[3, 3, 5, 6, 6, 6, -8, 3]。