搜索
5.4图的应用简介5.4.1最小生成树生成树：对图进行遍历的过程中，经过的边加上图的所有顶点构成的子图。深度优先生成树和广度优先生成树2134５2134５2134５无向图深度优先生成树广度优先生成树由n个顶点构成的连通图的生成树具有的特点：1）是一个最小的连通子图，含有全部顶点和n-1条边。2）任意两个顶点间只有唯一的一条路径，多一条边则够成回路，少一条边则非连通。3）连通图的生成树不唯一，从不同顶点出发进行遍历可以得到不同的生成树，对于带权图（网），生成树上的各边权值之和称为生成树的代价。最小的生成树是指代价最小的生成树。如下图所示：假设顶点表示城市，边表示在两城市间建立一通讯线路所花费的代价，那么要在5个城市之间建立通讯网络，则5个城市只需要5-1=4条线路，如何建立最经济。网2134５86967548上述问题即如何根据网构造最小的生成树。构造一个网络的最小生成树有两种方法：1.Prims算法2.Kruskal算法1．Prims(普里姆)算法普里姆算法的基本思想是：按照将顶点逐个连通的原则，把已连通的顶点加入到集合U中，这个集合U开始时为空集。首先任选一顶点加入U，然后从依附于该顶点的边中选取权值最小的边做为生成树的一条边，并将依附于该边且在集合U外的另一顶点加入到U。表示这两个顶点已通过权值最小的边连通了。以后，每次从一个顶点在集合U中而另一个顶点在U外的各条边中选取权值最小的一条，作为生成树的一条边，并把依附于该边且在集合U外的顶点并入U，依此类推，直到全部顶点都己连通(全部顶点加入到U)，即构成所要求的最小生成树。其算法描述如下：设G=V,E,⑴令U={v0},T={}.⑵对任意u∈U,v∈V-U,(u,v)∈E,找出权最小的边(u1,v1),令U=U∪{v1},T=T∪{(u1,v1)}⑶重复⑵，直至U=V.得到T就是最小生成树。T中共有n-1条边。按照上面的普里姆算法完成求图的最小生成树过程如图1-5-12所示：3764756267ABCDEF2ACA4E5326ABCDF5326ABCDF52ACF532ACDF2.Kruskal算法1）开始令最小生成树中只有n个顶点而无边的非连通图。2）从网中取一条权值最小的边加入到最小生成树中，看是否与树中的其他边构成了回路，如果构成了回路，则删除该边（即不加入）。3）重复2，直到最小生成树中含有n-1条边为止。注意：一个连通图的最小生成树不一定唯一，但最小生成树是指代价都相同。例：利用Kruskal算法构造最小生成树的过程：214５86785473214５3214５34577214５3457214５3457214５34网络（0）（1）（2）（3）（4）75.4.2.单源最短路径交通网络可以画成带权图。图中的顶点表示城市，边表示城市间的公路，边上的权值表示公路的长度。对于这样的交通网络常常提出这样的问题：1)两地之间是否有公路可通？2)在有路可通的情况下，则那一条路径最短，最短路径长度是多少。以上提出的问题就是在带权图中求最短路径问题，此时路径长度不是路径上的边数。而是路径上的边所带权值之和。5.4.3拓补排序用课程之间的次序关系引入拓补排序课程代号课程名称先修课程C1计算机导论无C2C语言C1C3离散数学C1C4汇编语言C2C5数据结构C2,C3C6编译方法C4,C5C7计算机原理C1C8操作系统C6,C7可用有向图表示课程之间先后次序：图中顶点表示要学习的课程，弧Vi,Vj表示Vi为Vj的先修课程。同样我们还可以把一个大工程的若干子工程之间的先后关系用有向图表示。AOV网C7C8C2C4C6C3C5C1在这种有向图中，若用顶点表示活动或任务，有向边表示活动或任务之间的先后关系，则称这样的有向图为顶点表示活动的网络，简称AOV网（ActivityOnVertexnetwork）。拓补排序是将无环有向图中的每个定点按先后顺序排成一个线性序列的过程。所得到的线性序列称为拓补序列（拓补序列不唯一）举例说明：C1,C2,C3,C4,C5,C6,C7,C8C1,C2,C3,C4,C5,C7,C6,C8拓补排序方法：1)在有向图中选一个入度为零的顶点且输出之。2)从图中删除该顶点和以它为尾的所有弧。3)重复1）2），直到所有顶点都被输出，即拓补排序完成；或者直到有向图中没有入度为零的顶点，说明此图是有环图，拓补排序不能在进行下去。5.4.4.关键路径(补充)把工程计划表示为有向图时，通常用顶点表示事件，用边表示活动，边上的权值表示完成活动所需要的时间，这样的有向图称为边表示活动的网络，简称AOE网（ActivityOnEdge）表示实际工程计划的AOE网应该是无环的，且存在唯一入度为0的开始顶点（源点）和唯一出度为0的完成顶点（汇点）。对于AOE网要研究的问题是：1)完成整个工程至少需要多少时间？2)那些活动是影响工程进度的关键？由于在AOE网中的某些活动可以并行进行，故完成整个工程的最少时间为从开始顶点到完成顶点的最长路径。具有最长的路径称为关键路径。②⑥①④⑤⑧③⑦a5=2a1=8a4=9a11=7a10=7a12=5a8=4a3=10a7=6a6=3a9=5a2=7关键路径有两条：(1)a3,a7,a9,a11(2)a3,a7,a10,a12关键活动：a3,a7,a9,a10,a11,a12