【教学课件】第七章图(Graphs).ppt

《【教学课件】第七章图(Graphs).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第七章图(Graphs).ppt（45页珍藏版）》请在三一办公上搜索。

1、第七章 图（Graphs),本章主要内容7.1 图的基本概念7.2 图的存储表示7.3 图的遍历 7.4 最小生成树7.5 有向无环图及其应用7.6 最短路径中国网页设计,7.3 图的遍历,图的遍历：从某个结点出发，访问图的每个结点恰好一次。,设v的邻接点是w1,w2,wm.1）访问v,2）从v的邻接点w1开始深度优先遍历；3）从一个未访问邻接点的wk开始深度优先遍历,直至所有与v连通的结点均被访问过。,从v开始深度优先遍历：,7.3 图的遍历广度优先遍历,基本思想访问v1;访问v1的邻接点w1,w2,wm;依次访问w1,w2,的未被访问的邻接点，如此进行下去，直至访问完所有结点。,算法的实现

2、需要设置一个数组visited标记结点是否访问过；设置一个队列纪录当前层访问的结点以备访问下一层结点。,7.4 最小生成树,问题：设在n个城市间建立通信网络，要求建设费用尽可能低。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。在此网络的生成树中找出建设费用最小的生成树。,7.4 最小生成树,设G是一个带权的无向图（网络），则G的生成树可能有多个，生成树各边的权之和称为生成树的权。网络G的具有最小权的生成树称为G的最小生成树。,7.4 最小生成树-Prim算法,假设N=(V，E)是连通网，T=(U,TE)表示下列算法构造的N上最小生成树。算法从U=u0(u0V)，TE=开始;重

3、复执行下述操作,直至U=V为止：在所有 uU，vV-U的边(u，v)E中找一条权最小的边(u，v)，将v并入U，同时边(u，v)并入集合TE。,设N有n个结点.则算法结束时,T中必有n个结点,n-1条边.在2中,如果有相同权的边,可任选一条,故最小生成树不唯一.,7.4 最小生成树-Prim算法,例:求下图的最小生成树,初始状态:U=v0,循环:对于每个结点viU，在vi与U中所有结点的邻接边中找出权最小的边ei=(vi,uk),并在这些边ei中求出权最小的边,设为(vi,uk).将uk并入U,(vi,uk)并入构造中的生成树。,最小生成树,普里姆算法,图7-21 按prime算法从v2出发构

4、造最小生成树的过程,7.4 最小生成树-Prim算法,7.4 最小生成树-Kruskal算法,克鲁斯卡尔基本思想：考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法:先构造一个只含 n 个顶点的而无边的子图SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,最小生成树,2克鲁斯卡尔算法,7.4 最小生成树-Kruskal算法,7.4 最小生成树-Kruskal算法,（2）两种算法比较：,e为边数,7.5 有向无环图及其应用-拓扑排序,一个工程(project)可分为若干

5、个称作活动(activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。,计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,C1 高等数学 C2 程序设计基础 C3 离散数学 C1,C2 C4 数据结构 C2，C3 C5 高级语言程序设计 C2 C6 编译方法 C4，C5 C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8,7.5 有向无环图及其应用-拓扑排序,这样的工程流程图可以用一个有向图表

6、示：,顶点表示活动，有向边(u,v)表示u必须先于v完成。这种图称为顶点表示活动的网（Activity on Vertices Network），或者AOV网络.,C1 高等数学 C2 程序设计基础 C3 离散数学 C1,C2 C4 数据结构 C2，C3 C5 高级语言程序设计 C2 C6 编译方法 C4，C5,C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8,7.5 有向无环图及其应用-拓扑排序,7.5 有向无环图及其应用-拓扑排序,AOV网是否存在有向环可以通过检查有向图是否存在一个拓扑排序。,AOV活动能够顺利进行的条件是不存在有向环;,工程能否顺利进行呢?,7.

7、5 有向无环图及其应用-拓扑排序,拓扑排序方法：(1)在有向图中选一个没有前驱的顶点输出；(2)从图中删除该顶点和所有以它为始点的边。(3)重复上述两步，直至 全部顶点均已输出，排序完成；当前图中不存在无前驱的顶点，则有向图中存在环。,上述AOV网的一个拓扑排序是：C1,C2,C3,C4,C5,C6,C8,C9,C7如果一个学生每学期只能修一门课，则必须按照上述顺序进行。,如果AOV网络存在一个拓扑序列，则该AOV网络中必定不会出现有向环 相反，如果不存在拓扑序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。,7.5 有向无环图及其应用-拓扑排序,v5,v6-v1-v4-

8、v3-v2-v5,7.5 有向无环图及其应用-关键路径,关键路径：估算工程的完成时间（1）问题的提出 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。,7.5 有向无环图及其应用-关键路径,（2）相关术语源点/汇点（开始点完成点）源点指网中入度为0的点，通常只有一个入度为0的点；汇点指评审图中出度为0的点，表示所有工程均结束。,顶点表示事件，弧表示活动，权表示活动持续的时间。完成工程的最短时间是从源点到汇点的最长路径长度。路径长度最长的路径叫做关键路径。,7.5 有向无环图及其应用-关键路径,如何找

9、关键路径,事件（顶点）的最早开始时间：ve(i)=从源点到顶点i的最长路径长度。事件（顶点）的最晚开始时间：vl(i)=从顶点i到汇点的最短路径长度。关键活动：e(i)=l(i)的活动叫做关键活动。,7.5 有向无环图及其应用-关键路径,（3）举例,P186 图7.30,7.6 最短路径,7.6 最短路径,问题的提出如前面所示的交通网络图，顶点表示城市，边表示城市间的交通联系，而边上的权值可以表示为里程数（也可以表示通行费用或所需时间）问题的提出：一位旅客要从A城到B城 1、如何选择一条最短的路径；2、如何选择一条费用最小的路线；3、如何选择一条最快的路线。,7.6 最短路径,这些问题均是带权

10、图上的最短路径问题。,7.6 最短路径,设G是带权有向图，最短路径问题：如果从图中某一顶点出发到达另一顶点的路径可能不止一条，如何找到一条长度最小的路径。,单源最短路径问题：设G是带权(=0)有向图，给定一个顶点v，求v到其余顶点的最短距离。,7.6 最短路径-Dijkstra算法,Dijkstra算法基本思想:如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。按路径长度的递增次序，逐步产生最短路径.设源点为v0首先求出v0为源点长度最短的一条路径，即具有最小权的边;求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短

11、路径（v0v)和边构成；重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。,7.6 最短路径-Dijkstra算法,求解过程举例：v0到各终点的最短路径的求解过程如下所示,7.6 最短路径-Floyd算法,问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求出vi 与vj之间的最短路径和最短路径长度。,Floyd算法思想：先求只经过顶点v0的最短路径，再求只经过v0，v1的最短路径，一直到可以经过所有的顶点。一般地，设P1=(vi,vk),P2=(vk,vj)是只经过v0，.,v(k-1)的最短路径，则vi到vj的只经过v0,vk的最短路径或者是已求得的只经过v

12、0,v(k-1)的最短路径，或者是P1+P2.,7.6 最短路径-Floyd算法,每一对顶点的最短路径(Floyd算法)求解过程：其中：D(1)表示从vi到vj的中转顶点的序号不大于1（可以等于1）的最短路径长度，同理D(0)，D(2),随堂练习：,1、设无向图的顶点个数为n，则该图最多有（）条边。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.0 E.n22、一个n个顶点的连通无向图，其边的个数至少为（）。An-1 Bn Cn+1 Dnlogn；3要连通具有n个顶点的有向图，至少需要（）条边。An-l Bn Cn+l D2n,B,A,B,4n个结点的完全有向图含有边的数目（）An

13、*n n（n）Cn2 Dn*（nl）5一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A0 B1 Cn-1 Dn6.在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A1/2 B2 C1 D4,D,D,B,B,C,7、下面结构中最适于表示稀疏无向图的是（C），适于表示稀疏有向图的是（BE）。A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表 E邻接表 8、下列哪一种图的邻接矩阵是对称矩阵？（）A有向图 B无向图 CAOV网 DAOE网,B,9、下列说法不正确的是（C）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程,10、无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b,D,更多教程请查看：,