图的最小生成树

 

如果用一个连通网表示 n 个居民点和各个居民点之间可能架设的通讯线路，则网中每一条边上的权值表示架设这条线路所需经费。由于在 n 个居民点间构建通讯网只需架设 n-1 条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？类似此类的问题很多，如第1章中的铺设煤气管道问题等。这些问题均等价于，在含有 n 个顶点的连通网中选择 n-1 条边，构成一棵极小连通子图，并使该连通子图中 n-1 条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。

一、 克鲁斯卡尔(Kruskal)算法思想

克鲁斯卡尔算法的基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。

由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选，那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通？从生成树的构造过程可见，初始态为 n 个顶点分属 n 棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。

具体实现方法是以"双亲表示法"来表示树，并以各棵树的根结点作"树"的代号。

克鲁斯卡尔(Kruskal)算法

　　typedef struct {

　　　VertexType vex1;

　　　VertexType vex2;

　　　VRType weight;

　　}EdgeType;

 

　　typedef ElemType EdgeType;

　　typedef struct { 　　　　　　　　         // 有向网的定义

　　　VertexType vexs[MAX_VERTEX_NUM]; 　// 顶点信息

　　　EdgeType edge[MAX_EDGE_NUM]; 　　　// 边的信息

　　　int vexnum,arcnum;　　　　　　　　// 图中顶点的数目和边的数目

　　}ELGraph;

　　void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree)

　{

　　// G.edge 中依权值从小到大存放有向网中各边，按克鲁斯卡尔算法求得生成树的边存放在顺序表 MSTree 中

MFSet F;

　　InitSet(F, G.vexnum);　　　　　　　　　// 将森林F初始化为n棵树的集合

　　InitList(MSTree, G.vexnum);　　　　　　// 初始化生成树为空树

　　i=0; k=1;

while( k

e = G.edge[i];　　　　　　　　　　　     // 取第 i 条权值最小的边

r1 = fix_mfset(F, LocateVex(e.vex1));

　　　r2 = fix_mfset(F, LocateVex(e.vex2)); // 返回两个顶点所在树的树根

　　　if (r1 != r2) { 　　　　　　　　　　// 选定生成树上第k条边

　　　　if (ListInsert(MSTree, k, e)) k++;　// 插入生成树

　　　　mix_mfset(F, r1, r2);　　　　　　　// 将两棵树归并为一棵树

　　　} // if

　　　i++; 　　　　　　　　　　　　　　　// 继续考察下一条权值最小边

　　} // while

　　DestroySet(F);

　} // MiniSpanTree_Kruskal

克鲁斯卡尔(Kruskal)算法分析

该算法的时间复杂度为O(elge);Kruskal算法的时间主要取决于边数,它较适合于稀疏图。

二、普里姆（Prim）算法思想

普里姆算法则从另一个角度构造连通网的最小生成树。它的基本思想是：首先选取图中任意一个顶点 v 作为生成树的根，之后继续往生成树中添加顶点 w，则在顶点 w 和顶点 v 之间必须有边，且该边上的权值应在所有和 v 相邻接的边中属最小。在一般情况下，假设图 G=(V,E) 中已落在生成树上的顶点集为U，则尚未落在生成树上的顶点集为 V-U，则从 (V-U) 顶点集中选取加入生成树的顶点 w 应满足下列条件：它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值属最小。

从上述生成树的构造过程中回还可以发现一点，即每个顶点都是通过"一条边"加入到生成树上的，因此对集合 V-U 中的每个顶点，当它和集合 U 中的顶点有一条以上的边相连时，只需要保留一条权值最小的边即可。由此，在普里姆算法中需要附设一个辅助数组 closedge，以记录从集合 U 到集合 V-U 中每个顶点当前的权值最小边。

普里姆（Prim）算法代码：

　　typedef struct {

　　　VertexType adjvex;

　　　VRType lowcost;

}closedge[MAX_VERTEX_NUM];

 

　　假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，

　　　closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|u∈U}

 

　　void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)

　{

　　// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构造G的最小生成树，顺序表 MSTree 中记录生成树的各条边

　　k = LocateVex ( G, u );

　　InitList(MSTree, G.vexnum); 　　　// 初始化生成树为空树

　　for ( j=0; j　　 // 辅助数组初始化

　　　if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}

　　　closedge[k].lowcost = 0; 　　　 // 初始状态，U＝{u}

　　for (i=1; i　　  // 选择其余 G.vexnum-1 个顶点

　　　k = minimum(closedge);　　　　　// 求出T的下一个结点(图中第k顶点)

　　　// 此时closedge[k].lowcost =Min{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }

　　　e.vex1 = closedge[k].adjvex;

　　　e.vex2 = G.vexs[k];

　　　e.weight = closedge[k].lowcost;

　　　b = ListInsert (MSTree, i, e);　 // e 为生成树的一条边

　　　closedge[k].lowcost = 0; 　　　// 第 k 顶点并入U集

　　　for (j=0; j

　　　　if (G.arcs[k][j].adj < closedge[j].lowcost)

　　　　　　　　　　　　　　　　　　 // 新顶点并入U后重新选择最小边

closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

　　　} // for

　} // MiniSpanTree

 普里姆（Prim）算法分析:

该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。