|
|
|
|
|
设图G=(V,E)是个连通图，当从图中任一个顶点出发遍历图G时，将边集E(G)分为两个集合，即A(G)和B(G)。其中A(G)是遍历时所经过的边的集合，B(G)是遍历时未经过的边的集合。G1=(V,A)是图G的子图，称子图G1为连通图G的生成树。
|
|
|
|
图的生成树不是唯一的。选择不同的存储方式，从不同的顶点出发，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，如果把生成树各边的权值总和称为生成树的权，则把权值最小的生成树称为最小生成树。
|
|
|
|
构造生成树有多种算法，其中多数算法利用了最小生成树的MST性质：假设G=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条最小权值的边，其中u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。
|
|
|
|
①普里姆算法。它的时间复杂度为O(n2)，与图中的边数无关，因此该算法适合于求边稠密的网中的最小生成树。
|
|
|
|
②克鲁斯卡尔算法。它的时间复杂度为O(elog2e)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
