|
|
|
|
一棵生成树的代价即树上各边的代价之和，如果该生成树的代价最小，则称该树为最小生成树（也称最小代价生成树）。
|
|
|
|
求图的最小生成树有着广泛的应用价值。例如，如何在n个城市之间建立通信联络网，并且连通n个城市只需要n-1条线路，而且通信代价最少。
|
|
|
|
构造最小生成树的算法主要有Prim（普里姆）算法和Kruskal（克鲁斯卡尔）算法两种。
|
|
|
|
|
|
Prim算法用于求无向图的最小生成树。N=(V,E)是连通网，V={V1, V2, …, Vn}是网的顶点集合，E是N上最小生成树中边的集合。引入顶点集合U和边的集合TE，U的初始状态为{V1}，它存放的是当前所得到的（还未完成的）最小代价生成树上的所有顶点，TE的初始状态为Ф。在Prim算法的每一步，都从所有的边{(u,v)|v∈V-U, u∈U}中找出所有代价最小的边(u,v)，同时将v并入U，(u,v)并入集合TE，直到U=V为止。此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。
|
|
|
|
Prim算法的时间复杂度为O(n2)。它适合稠密图。
|
|
|
|
|
|
Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。若G=(V, E)是一个连通的无向图，其中V={1,2,…,n}，引入辅助集合T，来存放当前所形成的最小生成树的所有边，其初始状态为空，则Kruskal算法是逐步给T添加不与T中的边构成回路的当前最小代价边。具体步骤如下。
|
|
|
|
|
|
|
|
|
|
（4）若(v,u)不和T中的边一起构成回路，则将边(v,u)并入T中。
|
|
|
|
（5）循环执行步骤（2）～（4），直到T中的所有顶点都在同一个连通图上且包含n-1条边为止。
|
|
|
|
若带权连通无向图G有e条边，则用Kruskal算法构造最小生成树的时间复杂度为O(elog2e)。它适用于稀疏图。
|
|
|
|
|
|
|
|
