详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）

《详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1•最小生成树:这篇文章主要介绍了图的应用（最小生成树、拓扑排序、关键路径、最短路径），需要的朋友可以参考下无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下姥立这个通信网。在每两个城市之间都可以设置-条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n（n-1）^条线路，那么，如何在这些可能的线路中选择条，以使总的耗费最少呢？1.2分析问题（建立模型）：可以用连通网來表示n个

2、城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市Z间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所冇顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图G5无向连通图的生成树为（a）、（b）和（c）图所示：G5G5的三棵生成树:可以证明，对于有n个顶点的无向连通图，无论英生成树的形态如何，所有生成树屮都有且仅有n—l条边。1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树屮必有棵

3、边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。最小生成树的性质：假设N=（V,{E}）是个连通网，U是顶点集合V的一个非空了集，若（u,v）是个一条具有故小权值（代价）的边，其中，uEU♦vGV—U则必存在一棵包含边（u,v）的最小生成树。1.4解决方案：两种常用的构造最小生成树的算法：nm'

4、，集合T（边集合）存放G的最小生成树中的边。T,U的初始状态：令集合U的初值为U={ul}（假设构造最小生成树时，从顶点ul出发），集合T的初值为T={}。Prim算法的思想是：从所有uWU,vGV-U的边中，选取具有最小权值的边（u,v）GE,将顶点v加入集合U中，将边（u,v）加入集合T中，如此不断重复，直到U=V时，故小生成树构造完毕，这时集合T中包含了最小生成树的所有边。Prim算法可用下述过程描述，其中WJwuv表示顶点u与顶点v边上的权值。⑴U={ul},T={}；（2）while（UHV）do（u»v）=min{wuv；u^U,V—U}T=T+{（u,v）}U=U+{v}（

5、3）结束。按照Prim方法，从顶点1出发，该网的最小生成树的产生过程如图:(d)(e)(f)图7.16普里姆算法构造最小生成树的过程为实现Prim算法，需设置网个辅助closedge,用来保存U到集合V—U的各个顶点中具有最小权值的边的权值。对每个ViW(V-U)在辅助数组中存在一个相应的分量closedgeli-l],它包括两个域：typedefstructArcNodeintadjvex;//adjex域存储该边依附的在U中的顶点VrTypelowcost;//lowcost域存储该边上的权重}closedge[MAX_VERTEX_NUM];口然closedge[i—1]・lowc

6、ost=Min{cost(Vj)®[uGU}初始状态时，U={vl}(ul为出发的顶点)，则到V-U中各项中最小的边，即依附顶点vl的各条边中，找到一条代价最小的边(u0,vO)=(1,3)为生成树上一条边。同吋将vO(=v3)并入集合U中。然后修改辅助数组的值。1）将closedge[2].lowcost=0；〃表示顶点V3三已经并入U2)由于边(v2,v3)的权值小于closedge

7、l].lowcost,故需修改closedge⑴为边(v2,v3)及其权值,同理修改closedge[4],closedge⑸.closedge[l].adjvex=3.closedge[l]」owco

8、st=5・closedge[4].adjvex=1.closedge[4].lowcost=5.closedge[5].adjvex=3.closedge

9、5].lowcost=6.以此类推，直至U=V;下图给出了在用上述算法构造网图7.16的最小生成树的过程中：closed12345uv-ukadjvcxlowcostV

10、6Vi1Vi5{y}(V2・V,tV

11、tV3・*}2adjvcxlowcost5

12、0V)5Vj6*34