1. 生成树与最小生成树
生成树：无向连通图 G 的一个子图如果是一棵包含 G 的所有顶点的树，则该子图称为 G 的生成树。生成树是连通图的极小连通子图。这里所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。
最小生成树：对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。
构造最小生成树的准则有三条：
- 必须只使用该网络中的边来构造最小生成树；
- 必须使用且仅使用 n-1 条边来连接网络中的 n 个顶点；
- 不能使用产生回路的边。
构造最小生成树的算法主要有：克鲁斯卡尔（Kruskal）算法、 Boruvka 算法和普里姆（Prim）算法，都得遵守以上准则。
2. Kruskal 算法思想
克鲁斯卡尔算法的基本思想是以边为主导地位，始终都是选择当前可用的最小权值的边。具体为：
- 设一个有 n 个顶点的连通网络为 G(V, E)，最初先构造一个只有 n 个顶点，没有边的非连通图 T = { V, Ø }，图中每个顶点自成一个连通分量。
- 当在 E 中选择一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则，即这条边的两个顶点落在同一个连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权值最小的边。
- 如此重复下去，直到所有顶点在同一个连通分量上为止。
如下图(a)所示的无向网，其邻接矩阵如图(b)所示。利用克鲁斯卡尔算法构造最小生成树的过程如图(c)所示，首先构造的是只有 7 个顶点，没有边的非连通图。剩下的过程为（图(c)中的每条边旁边的序号跟下面的序号是一致的）：
- 在边的集合 E 中选择权值最小的边，即(1, 6)，权值为 10；
- 在集合 E 剩下的边中选择权值最小的边，即(3, 4)，权值为 12；
- 在集合 E 剩下的边中选择权值最小的边，即(2, 7)，权值为 14；
- 在集合 E 剩下的边中选择权值最小的边，即(2, 3)，权值为 16；
- 在集合 E 剩下的边中选择权值最小的边，即(7, 4)，权值为 18，但这条边的两个顶点位于同一个连通分量上，所以要舍去；继续选择一条权值最小的边，即(4, 5)，权值为 22；
- 在集合 E 剩下的边中选择权值最小的边，即(7, 5)，权值为 24，但这条边的两个顶点位于同一个连通分量上，所以要舍去；继续选择一条权值最小的边，即(6, 5)，权值为 25。至此，最小生成树构造完毕，最终构造的最小生成树如图(d)所示，生成树的权为 99。
克鲁斯卡尔算法的伪代码为：
T = (V, φ);
while ( T 中所含边数 < n-1 )
{
从 E 中选取当前权值最小的边(u, v);
从 E 中删除边(u, v);
if(边(u, v)的两个顶点落在两个不同的连通分量上) {
将边(u, v)并入 T 中;
}
}Kruskal 算法在每选择一条边加入到生成树集合 T 时，有两个关键步骤：
- 从 E 中选择当前权值最小的边(u, v)，实现时可以用最小堆来存放 E 中所有的边；或者将所有边的信息（边的两个顶点、权值）存放到一个数组 edges 中，并将 edges 数组按边的权值从小到大进行排序，然后依先后顺序选用每条边。
- 选择权值最小的边后，要判断两个顶点是否属于同一个连通分量，如果是，则要舍去；如果不是，则选用，并将这两个顶点分别所在的连通分量合并成一个连通分量。在实现时可以使用并查集来判断两个顶点是否属于同一个连通分量、以及将两个连通分量合并成一个连通分量。