| 对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两种常用的求最小生成树的算法。
|
|
|
|
|
| 假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从顶点集合U=｛u0｝（u0∈V）、边的集合TE=｛｝开始，重复执行下述操作：在所有u∈U，ν∈V-U的边（u，ν）∈E中找一条代价最小的边（u0，ν0），把这条边并入集合TE，同时将ν0并入集合U，直至U=V时为止。此时TE中必有n-1条边，则T=（V，｛TE｝）为N的最小生成树。
|
|
|
| 由此可知，普里姆算法构造最小生成树的过程是以一个顶点集合U=｛u0｝作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U=V时为止。
|
|
|
|
|
|
|
|
|
|
|
| 克鲁斯卡尔求最小生成树的算法思想为：假设连通网N=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。
|
|
|
|
|
|
|
|
|
| 克鲁斯卡尔算法的时间复杂度为O（eloge）（e为网中的边数），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
