图的最小生成树.doc

图的最小生成树如果用一个连通网表示n个居民点和各个居民点之间可能架设的通讯线路，则网中每一条边上的权值表示架设这条线路所需经费。由于在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低?类似此类的问题很多，如第1章中的铺设煤气管道问题等。这些问题均等价于，在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。一、克鲁斯卡尔(Kruskal)算法思想克鲁斯卡尔算法的基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选，那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。具体实现方法是以双亲表示法来表示树，并以各棵树的根结点作树的代号。克鲁斯卡尔(Kruskal)算法typedef structVertexType vex1；VertexType vex2；VRType weight；EdgeType；typedef ElemType EdgeType；typedef struct/有向网的定义VertexType vexsMAX_VERTEX_NUM；/顶点信息EdgeType edgeMAX_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 G.vexnum)e=G.edgei；/取第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 structVertexType adjvex；VRType lowcost；closedgeMAX_VERTEX_NUM；假设cost(u,w)表示边(u,w)上的权值，则对于集合V-U中每个顶点w，closedgeLocateVex(G,w).lowcost=Mincost(u,w)|uUvoid MiniSpanTree_PRIM(MGraph G,VertexType u,SqList&MSTree)/G为数组存储表示的连通网，按普里姆算法从顶点u出发构造G的最小生成树，顺序表MSTree中记录生成树的各条边k=LocateVex(G,u)；InitList(MSTree,G.vexnum)；/初始化生成树为空树for(j=0；j G.vexnum；+j)/辅助数组初始化if(j！=k)closedgej=u,G.arcskj.adj；/adjvex,lowcostclosedgek.lowcost=0；/初始状态，U=ufor(i=1；i G.vexnum；+i)/选择其余G.vexnum-1个顶点k=minimum(closedge)；/求出T的下一个结点图中第k顶点/此时closedgek.lowcost=Minclosedgevi.lowcost|closedgevi.lowcost 0,viV-Ue.vex1=closedgek.adjvex；e.vex2=G.vexsk；e.weight=closedgek.lowcost；b=ListInsert(MSTree,i,e)；/e为生成树的一条边closedgek.lowcost=0；/第k顶点并入U集for(j=0；j G.vexnum；+j)if(G.arcskj.