《教学课件第七章图Graphs》由会员分享，可在线阅读，更多相关《教学课件第七章图Graphs（45页珍藏版）》请在金锄头文库上搜索。
1、第七章 图（Graphs)本章主要内容7.1 图的基本概念7.2 图的存储表示7.3 图的遍历 7.4 最小生成树7.5 有向无环图及其应用7.6 最短路径中国网页设计 7.3 图的遍历图的遍历：图的遍历：从某个结点出发，访问图从某个结点出发，访问图的每个结点恰好一次。的每个结点恰好一次。设设v v的邻接点是的邻接点是w1,w2,wm.w1,w2,wm.1 1）访问）访问v,v,2 2）从）从v v的邻接点的邻接点w1w1开始开始深度优先深度优先遍历；遍历；3 3）从一个未访问邻接点的）从一个未访问邻接点的wkwk开始开始深度深度优先遍历优先遍历, , 直至所有与直至所有与v v连通的结点均连
2、通的结点均被访问过。被访问过。从从v开始开始深度优先遍历：深度优先遍历：v8v5v4v6v7v1v3v27.3 图的遍历广度优先遍历基本思想基本思想访问访问v1;访问访问v1的邻接点的邻接点w1,w2,wm;依次访问依次访问w1, w2, 的未被访问的邻接点，的未被访问的邻接点，如此进行下去，直至访问完所有结点。如此进行下去，直至访问完所有结点。v8v5v4v6v7v1v3v2算法的实现需要算法的实现需要设置一个数组设置一个数组visitedvisited标记结点是否访问过；标记结点是否访问过；设置一个队列纪录当设置一个队列纪录当前层访问的结点以备访前层访问的结点以备访问下一层结点。问下一层结
3、点。7.4 最小生成树问题问题：设在：设在n个城市间建立通信网络，要求个城市间建立通信网络，要求建设费用尽可能低。建设费用尽可能低。模型模型：n个结点的图，结点连线的权表示建设个结点的图，结点连线的权表示建设两点间通信线路的费用。在此网络的生成树两点间通信线路的费用。在此网络的生成树中找出建设费用最小的生成树。中找出建设费用最小的生成树。7.4 最小生成树 设设G是一个带权的无向图（网络），则是一个带权的无向图（网络），则G的生的生成树可能有多个，生成树各边的权之和称为生成成树可能有多个，生成树各边的权之和称为生成树的权。树的权。 网络网络G的具有最小权的生成树称为的具有最小权的生成树称为G的
4、最小生的最小生成树成树。7.4 最小生成树-Prim算法 假设假设N=(VN=(V，E)E)是连通网，是连通网，T=(U,TE)T=(U,TE)表示下列算表示下列算法构造的法构造的N N上最小生成树。上最小生成树。1.1.算法从算法从U=uU=u0 0(u(u0 0VV) )，TE= TE= 开始开始; ;2.2.重复执行下述操作重复执行下述操作, , 直至直至U=VU=V为止：在所有为止：在所有3.3. u uU U，v vV-V-U U的边的边(u(u，v)v)EE中找一条权最小的中找一条权最小的边边(u(u，v)v)，将，将v v并入并入U U，同时边同时边(u(u，v)v)并入集合并入
5、集合TETE。设设N N有有n n个结点个结点. . 则算法结束时则算法结束时, T, T中必有中必有n n个个结点结点, n-1, n-1条边条边. .在在2 2中中, , 如果有相同权的边如果有相同权的边, ,可任选一条可任选一条, , 故故最小生成树不唯一最小生成树不唯一. .7.4 最小生成树-Prim算法例: 求下图的最小生成树5v5v4v2v3v1v065 1536642初始状态初始状态: U=v0循环循环: 对于每个结点对于每个结点v vi i U U，在，在v vi i与与U U中所有结点的邻接边中找出中所有结点的邻接边中找出权最小的边权最小的边e ei i=(v=(vi i,
6、u,uk k), ), 并在这并在这些边些边e ei i中求出权最小的边中求出权最小的边, , 设为设为(v(vi i, u, uk k). ). 将将u uk k并入并入U, (vU, (vi i, u, uk k) )并入构造中的生成树。并入构造中的生成树。最小生成树普里姆算法v1v3v2v4v54857121136(a)v2v45(b)(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45图图7-21 按按prime算法从算法从v2出发构造最小生成树的过程出发构造最小生成树的过程7.4 最小生成树-Prim算法 7.4 最小生成树-Kruskal算法克鲁斯卡
7、尔基本思想基本思想： 考虑问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 具体做法具体做法: 先构造一个只含 n 个顶点的而无边的子图SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。最小生成树2克鲁斯卡尔算法7.4 最小生成树-Kruskal算法 7.4 最小生成树-Kruskal算法（2）两种算法比较：e为边数7.5 有向无环图及其应用-拓扑排序 一个工程一个工程(project)(project)可分为若干个称作活可分为若干个称作活动动(activity
8、)(activity)的子工程，而这些子工程之间，的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。的开始必须在另一些子工程完成之后。 计算机专业学生的学习就是一个工程，每一门计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。之间有领先关系，有的课程可以并行地学习。 C C1 1 高等数学高等数学高等
9、数学高等数学 C C2 2 程序设计基础程序设计基础程序设计基础程序设计基础 C C3 3 离散数学离散数学离散数学离散数学 C C1 1, C, C2 2 C C4 4 数据结构数据结构数据结构数据结构 C C2 2 ，C C3 3 C C5 5 高级语言程序设计高级语言程序设计高级语言程序设计高级语言程序设计 C C2 2 C C6 6 编译方法编译方法编译方法编译方法 C C4 4 ，C C5 5 C C7 7 操作系统操作系统操作系统操作系统 C C4 4, C, C9 9 C C8 8 普通物理普通物理普通物理普通物理 C C1 1 C C9 9 计算机原理计算机原理计算机原理计算机
10、原理 C C8 8 7.5 有向无环图及其应用-拓扑排序这样的工程流程图可以用一个有向图表示：这样的工程流程图可以用一个有向图表示： 顶顶点点表示表示活动活动， 有向边有向边(u, v)(u, v)表示表示u u必须先于必须先于v v完成完成。 这种图称为这种图称为顶点表示活动的网顶点表示活动的网（Activity on Activity on Vertices NetworkVertices Network），或者），或者AOV网络网络. .C2C1C3C4C5C8C9C7C6 C C1 1 高等数学高等数学高等数学高等数学 C C2 2 程序设计基础程序设计基础程序设计基础程序设计基础 C
11、 C3 3 离散数学离散数学离散数学离散数学 C C1 1, C, C2 2 C C4 4 数据结构数据结构数据结构数据结构 C C2 2 ，C C3 3 C C5 5 高级语言程序设计高级语言程序设计高级语言程序设计高级语言程序设计 C C2 2 C C6 6 编译方法编译方法编译方法编译方法 C C4 4，C C5 5, , C C7 7 操作系统操作系统操作系统操作系统 C C4 4, C, C9 9 C C8 8 普通物理普通物理普通物理普通物理 C C1 1 C C9 9 计算机原理计算机原理计算机原理计算机原理 C C8 8 7.5 有向无环图及其应用-拓扑排序7.5 有向无环图及
12、其应用-拓扑排序AOV网是否存在有向环可以通过检查有向图是否存在一个拓扑排序。C2C1C3C4C5C8C9C7C6 AOV活动能够顺利进行的条件是不存在有向环活动能够顺利进行的条件是不存在有向环; ;工程能否顺利工程能否顺利进行呢进行呢?7.5 有向无环图及其应用-拓扑排序拓扑排序方法：(1)在有向图中选一个没有前驱的顶点输出；(2)从图中删除该顶点和所有以它为始点的边。(3)重复上述两步，直至 全部顶点均已输出，排序完成；全部顶点均已输出，排序完成； 当当前前图图中中不不存存在在无无前前驱驱的的顶顶点点，则则有有向图中存在环。向图中存在环。上述上述AOV网的一个拓扑排序是：网的一个拓扑排序是
13、： C1, C2, C3, C4, C5, C6, C8, C9, C7如果一个学生每学期只能修一门课，则必须如果一个学生每学期只能修一门课，则必须按照上述顺序进行。按照上述顺序进行。C2C1C3C4C5C8C9C7C6 如果AOV网络存在一个拓扑序列，则该AOV网络中必定不会出现有向环 相反，如果不存在拓扑序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。7.5 有向无环图及其应用-拓扑排序v2v5v5v1v2v3v5v4v6v4v1v5v3v2v4v5v3v2v3v5v2v6 - v1 - v4 - v3 - v2 - v57.5 有向无环图及其应用-关键路径关键路径
14、：估算工程的完成时间（1）问题的提出 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。 问：哪些子工程项是“关键工程”？ 即：哪些子工程项将影响整个工程的完成期限的。7.5 有向无环图及其应用-关键路径（2）相关术语源点源点/ /汇点（开始点汇点（开始点完成点）完成点） 源点源点指网中入度为0的点，通常只有一个入度为0的点；汇点汇点指评审图中出度为0的点，表示所有工程均结束。V1V2V3V5a1= 5a2= 4a4= 2a5= 1顶点表示事件，弧表示活动，权表示活动持续的时间。完成工程的最短时间是从源点到汇点的最长路径长度。路径长度最长的路径路径长度最长的路径叫做关键路径。
15、7.5 有向无环图及其应用-关键路径 如何找关键路径事件（顶点）的最早开始时间：ve(i) = 从源点到顶点i的最长路径长度。 事件（顶点）的最晚开始时间：vl(i) = 从顶点i到汇点的最短路径长度。 关键活动：e(i)=l(i)的活动叫做关键活动。7.5 有向无环图及其应用-关键路径（3）举例P186 图7.307.6 最短路径7.6 最短路径问题的提出问题的提出如前面所示的交通网络图，顶点表示城市，边表示城市间的交通联系，而边上的权值可以表示为里程数（也可以表示通行费用或所需时间）问题的提出问题的提出：一位旅客要从一位旅客要从A城到城到B城城 1、如何选择一条最短的路径；、如何选择一条最
16、短的路径； 2、如何选择一条费用最小的路线；、如何选择一条费用最小的路线； 3、如何选择一条最快的路线。、如何选择一条最快的路线。7.6 最短路径v5v4v3v2v1v0 100 6030101020 5 50这些问题均是带权图上的最短路径问题。这些问题均是带权图上的最短路径问题。7.6 最短路径设设G G是是带权有向图带权有向图，最最短短路路径径问问题题：如如果果从从图图中中某某一一顶顶点点出出发发到到达达另另一一顶顶点点的的路路径径可可能能不不止止一一条，如何找到一条长度最小的路径。条，如何找到一条长度最小的路径。单源最短路径问题单源最短路径问题单源最短路径问题单源最短路径问题： 设设设设
17、GG是带权是带权是带权是带权(=0)(=0)有向图，给定一个顶点有向图，给定一个顶点有向图，给定一个顶点有向图，给定一个顶点v v， 求求求求v v到其余顶点的最短距离。到其余顶点的最短距离。到其余顶点的最短距离。到其余顶点的最短距离。7.6 最短路径-Dijkstra算法Dijkstra算法基本思想: 如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。按路径长度的递增次序，逐步产生最短路径. 设源点为v01.首先求出v0为源点长度最短的一条路径， 即具有最小权的边;2.求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的
18、最短路径（v0v)和边构成；3.重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。7.6 最短路径-Dijkstra算法求解过程举例：v0到各终点的最短路径的求解过程如下所示v5v4v3v2v1v0 100 6030101020 5 507.6 最短路径-Floyd算法问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求出vi 与vj之间的最短路径和最短路径长度。FloydFloyd算法思想算法思想： 先求只经过顶点先求只经过顶点v v0 0的最短路径，的最短路径，再求只经过再求只经过v v0 0，v v1 1的最短路径，的最短路径， ， 一直到可以一直到可以经
19、过所有的顶点。经过所有的顶点。 一般地，设一般地，设P P1 1=(v=(vi i,v,vk k),P),P2 2=(v=(vk k,v,vj j) )是只是只经过经过v v0 0，.,v.,v(k-1)(k-1)的最短路径，则的最短路径，则v vi i到到v vj j的只经过的只经过v v0 0,v,vk k的最短路径或者是已求得的只经过的最短路径或者是已求得的只经过v v0 0,v,v(k-1)(k-1)的最短路径，或者是的最短路径，或者是P P1 1+P+P2 2. .7.6 最短路径-Floyd算法每一对顶点的最短路径(Floyd算法)求解过程：其中：D(1)表示从vi到vj的中转顶点
20、的序号不大于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 D2nBAB4n个结点的完全有向图含有边的数目（ ）An*n n（n） Cn2 Dn*（nl）5一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。A0 B1 Cn-1 Dn6.在一个无向图中，所有顶点的度数
21、之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。A1/2 B2 C1 D4DDBBC7、下面结构中最适于表示稀疏无向图的是（C ），适于表示稀疏有向图的是（BE ）。A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表 E邻接表 8、下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网B9、下列说法不正确的是（ 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,bD更多教程请查看：
