|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，如果把生成树各边的权值总和称为生成树的权，则把权值最小的生成树称为最小生成树。
|
|
|
|
构造生成树有多种算法，其中多数算法利用了最小生成树的MST性质：假设G=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条最小权值的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。
|
|
|
|
①普里姆算法。它的时间复杂度为O(n2)，与图中的边数无关，因此该算法适合于求边稠密的网中的最小生成树。
|
|
|
|
②克鲁斯卡尔算法。它的时间复杂度为O(elog2e)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
|
|
|
|
|
|
|
