搜索
1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。1.4解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中集合U（顶点集）用于存放G的最小生成树中的顶点，集合T（边集合）存放G的最小生成树中的边。T，U的初始状态：令集合U的初值为U＝{u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T＝{}。Prim算法的思想是：从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v）∈E，将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。（1）U＝{u1},T={};（2）while(U≠V)do(u，v)＝min{wuv；u∈U，v∈V－U}T＝T＋{(u，v)}U＝U＋{v}（3）结束。按照Prim方法，从顶点1出发，该网的最小生成树的产生过程如图：为实现Prim算法，需设置两个辅助closedge，用来保存U到集合V－U的各个顶点中具有最小权值的边的权值。对每个Vi∈（V-U）在辅助数组中存在一个相应的分量closedge[i-1],它包括两个域：typedefstructArcNode{intadjvex;//adjex域存储该边依附的在U中的顶点VrTypelowcost;//lowcost域存储该边上的权重}closedge[MAX_VERTEX_NUM];显然：初始状态时，U＝{v1}(u1为出发的顶点),则到V-U中各项中最小的边，即依附顶点v1的各条边中，找到一条代价最小的边（u0，v0）=（1，3）为生成树上一条边。同时将v0（=v3）并入集合U中。然后修改辅助数组的值。1）将closedge[2].lowcost=0；//表示顶点V3三已经并入U2)由于边（v2,v3）的权值小于closedge[1].lowcost，故需修改closedge[1]为边（v2,v3）及其权值，同理修改closedge[4]，closedge[5].closedge[1].adjvex=3.closedge[1].lowcost=5.closedge[4].adjvex=1.closedge[4].lowcost=5.closedge[5].adjvex=3.closedge[5].lowcost=6.以此类推，直至U=V;下图给出了在用上述算法构造网图7.16的最小生成树的过程中：Prim算法实现：按照算法框架:（1）U＝{u1},T={};（2）while(U≠V)do(u，v)＝min{wuv；u∈U，v∈V－U}T＝T＋{(u，v)}U＝U＋{v}（3）结束。当无向网采用二维数组存储的邻接矩阵存储时，Prim算法的C语言实现为：?12345678910//记录从顶点集U到V—U的代价最小的边的辅助数组定义：//struct{//VertexTypeadjvex；//VRTypelowcost；//}closedge[MAX_VERTEX_NUM]voidMiniSpanTree_PRIM(MGraphG，VertexTypeu){//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。k=LocateVex(G，u)；for(j=0；jG.vexnum；++j)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};//{adjvex,lowcost}closedge[k].lowcost=0；//初始，U={u}for(i=1；iG.vexnum；++i){//选择其余G.vexnum-1个顶点k=minimum(closedge)；11121314151617181920printf(closedge[k].adjvex,G.vexs[k]);//输出生成树的边//第k顶点并入U集closedge[k].lowcost=0;for(j=0;jG.vexnum;++j)if(G.acrs[k][j].adjclosedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};}//for}//MiniSpanTree假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。其中有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1；其二是重新选择具有最小代价的边，其频度为n。由此，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。2.克鲁斯卡尔（Kruskal）:由点到线，适合边稀疏的网。时间复杂度：O(e*loge)Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。基本思想是：1)设无向连通网为G＝（V，E），令G的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。2)在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量，则将此边加入到T中，否则舍弃此边而选择下一条边（若该边依附的两个顶点属于同一个连通分量，则舍去此边，以免造成回路）。依此类推，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。按照Kruskal方法构造最小生成树的过程如图所示：在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n－1条边，故反复上述过程，直到选取了n－1条边为止，就构成了一棵最小生成树。Kruskal算法的实现：算法的框架：构造非连通图T＝（V，{}）k=i=0；//k为边数while（k《n-1）{i++;检查边E中第i条边的权值最小边（u，v）若（u，v）加入T不是T产生回路，则（u，v）加入T，且k++}c语言实现：C语言实现Kruskal算法，其中函数Find的作用是寻找图中顶点所在树的根结点在数组father中的序号。需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。?123456typedefintelemtype;typedefstruct{elemtypev1;elemtypev2;intcost;}EdgeType;voidKruskal（EdgeTypeedges[]，intn）/*用Kruskal方法构造有n个顶点的图edges的最小生成树*/78910111213141516171819202122232425{intfather[MAXEDGE];inti,j,vf1,vf2;for(i=0;in;i++)father[i]=-1;i=0;j=0;while(iMAXEDGE&&jn-1){vf1=Find(father,edges[i].v1);vf2=Find(father,edges[i].v2);if(vf1!=vf2){father[vf2]=vf1;j++;printf(“%3d%3d\n”,edges[i].v1,edges[i].v2);}i++;}}//find函数intFind（intfather[]，intv）/*寻找顶点v所在树的根结点*/{intt;t=v;while(father[t]=0)t=father[t];return(t);2627282930313233}2.AOV网与拓扑排序：由偏序定义得到拓扑有序的操作便是拓扑排序。建立模型是AOV网2.1．AOV网(Activityonvertexnetwork)所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。若以图中的顶点来表示活动，有向边（弧）表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV网（ActivityOnVertexNetwork）。在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i的后继。若i,j是图中的弧，则称顶点i是顶点j的直接前驱，顶点j是顶点i的直接后驱。AOV网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应代号如表所示。课程之间的优先关系图：该图的拓扑有序系列：注意：在AOV-网中不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。2.2．拓扑排序离散数学基础知识：首先复习一下离散数学中的偏序集合与全序集合两个概念。若集合A中的二元关系R是自反的、非对称的和传递的，则R是A上的偏序关系。集合A与关系R一起称为一个偏序集合。若R是集合A上的一个偏序关系，如果对每个a、b∈A必有aRb或bRa，则R是A上的全序关系。集合A与关系R一起称为一个全序集合。直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。[例如]，图7.25所示的两个有向图，图中弧(x,y)表示x≤y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(TopologicalOrder)，而由偏序定义得到拓扑有序的操作便是拓扑排序。2.3拓扑排序算法对AOV网进行拓扑排序的方法和步骤是：1、从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；2、从网中删去该顶点，并且删去从该顶点发出的全部有向边；3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路；另一种就是网中顶点未被全