《图(基础知识)》由会员分享，可在线阅读，更多相关《图(基础知识)（74页珍藏版）》请在金锄头文库上搜索。
1、第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,（1）图：是由一个顶点集 V 和一个弧集（边集） R构成的数据结构。 表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。 （v,w）表示一条边。, 7.1 图的定义和术语,图的相关术语：,A B E C D,（2）有向图： “弧”是有方向的，由顶点集和弧集构成是有向图。,例如:,图G1,顶点集：A,B,C,D,E 弧 集:, , , , , , ,B C A D F E,（3）无向图：由顶点集和边集构成的图为无向图。,例如: 图G2 顶点集
2、：A, B, C, D, E, F 边 集：（A,B）, （A,E）, （B,E）, （C,D）, （D,F）, （B,F）, （C,F）,假设图中有n个顶点，则：,（4）完全图：含有n(n-1)/2 条边的无向图。,（5）有向完全图：含有n(n-1) 条弧的有向图。,（6）若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,15,9,7,21,11,2,（7）有向网：带权的有向图。 （8）无向网：带权的无向图。,3,B,（9）子图：设图G=(V,VR) 和 G=(V,VR)，且 VV, VRVR， 则称 G 为 G 的子图。,无向图来说： 假若顶点v 和顶点w 之间存在一条边，则称
3、顶点v 和w 互为邻接点，边(v,w) 和顶点v 和w 相关联。,例如:,TD(B) = 3,TD(A) = 2,顶点的度：和顶点v 关联的边的数目， 记为TD(v)。,顶点的出度: 以顶点v为弧尾的弧的数目。,有向图来说，,顶点的入度: 以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,设图G=(V,VR)中的一个顶点序列 (u=vi,0,vi,1, , vi,m=w)，其中(vi,j-1,vi,j)VR, 1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。,如:长度为3的
4、路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,在无向图G中，如果从顶点v到顶点v有一条路径，则说v和v是连通的； 若图G中任意两个顶点之间都有路径相通，则称此图为连通图。,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,对有向图，,否则，其各个强连通子图称作它的强连通分量。,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集
5、合为此非连通图的生成森林。,习题一（图的术语）,第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,7.3.1 深度优先搜索,7.3.2 广度优先搜索,从图中某个顶点V 出发，访问此顶点，然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V有路径相通的顶点都被访问到。,连通图的深度优先搜索遍历,7.3.1 深度优先搜索(DFS)遍历图,深度遍历： V1 V2 V4 V8 V5
6、V3 V6 V7,从图中的某个顶点V出发，并在访问此顶点之后依次访问V的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,7.3.2 广度优先搜索遍历图,广度遍历： V1 V2 V3 V4 V5 V6 V7 V8,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树,7.4.3 最小生成树,图的生成树：图中的所有顶点加上遍历过程中经过的边所构成的子图。,7.4.1 无向图的连通分量和生成树,深度优先生
7、成树 广度优先生成树,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,问题提出：,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,7.4.3 最小生成树,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,克鲁斯卡尔算法,该问题等价于：,普里姆算法,设N=(V,E)是连通网，T=(U,TE)为N的最小生成树。 (1) 初始令U=u,(u V), TE= 。 (2) 在所有uU,vV-U的边(u,
8、v)E中，找一条代价最小的边(u,v)。 (3) 将(u,v)并入集合TE，同时v并入U。 (4) 重复上述操作直至U=V为止。,普里姆算法方法：,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成树权值和：,14+8+3+5+16+21 = 67,具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树
9、中每一条边的权值尽可能地小。,克鲁斯卡尔方法：,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,习题二（图的遍历和生成树）,设有无向图G，要求给出用Prim法和Kruskal法构造最小生成树所走过的边的集合。,Prim法：,（1）,1,（2）,1,3,2,（3）,1,3,2,2,3,（4）,1,3,2,2,3,5,4,（6）,1,3,2,2,3,5,4,6,1,（5）,4,1,1,3,2,2,3,5,4,6,1,Kruscal法：,（1）,（4）,1,3,2,5,6,4
10、,1,（2）,1,3,2,5,6,4,1,1,2,（3）,1,3,2,5,6,4,1,1,2,3,（5）,1,3,2,5,6,4,1,1,2,3,4,1,3,2,5,6,4,1,1,第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,7.5.1 拓扑排序,7.5.2 关键路径,7.5有向无环图及其应用,7.5.1 拓扑排序,一、问题提出:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,例如：学生选修课程问题。 顶点表示课程，有向弧表示先决条件，若课程i是课程j的先决条件，则
11、图中有弧。 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业 拓扑排序。,二、定义 AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV网。 若是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后继。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件。,拓扑排序：把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。 由此所得顶点的线性序列称之为拓扑有序序列。,例如：对于下列有向图,B,D,A,C,可求得拓扑有序序列： A B C D 或 A C B D,
12、B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,三、如何进行拓扑排序？,（1）从有向图中选取一个没有前驱 的顶点，并输出之；,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,（2）从有向图中删去此顶点以及所 有以它为尾的弧；,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,7.5.2 关键路径,一、问题提出:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。 问题： (1) 完成整项工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键？,二、定义,AOE网(Activity On
13、Edge)：即边表示活动 的网。AOE网是一个带权的有向无环图， 其中顶点表示事件，弧表示活动，权表示 活动持续时间。,整个工程完成的时间：从源点到汇点的最长路径。 关键路径：路径长度最长的路径。 关键活动：关键路径上的活动。该弧上的权值增加将使有向图上的最长路径的长度增加。,三、如何求关键活动？,Ve(j)：表示事件Vj的最早发生时间。 Vl(j)：表示事件Vj的最迟发生时间。 e(i)：表示活动ai的最早开始时间。 l(i)：表示活动ai的最迟开始时间。 l(i)-e(i)：表示完成活动ai的时间余量。 关键活动：即l(i)=e(i)的活动。,1. 如何找e(i)=l(i)的关键活动？,设
14、活动ai用弧表示，其持续时间记为：dut() 则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),2. 如何求Ve(j)和Vl(j)？,(1) 从Ve(0)=0开始向前递推：,即：Ve(j)=从源点到顶点j的最长路径的长度。,2. 如何求Ve(j)和Vl(j)？,即：Vl(i)=从顶点i到汇点的最短路径的长度。,(2) 从Vl(n-1)=Ve(n-1)开始向后递推：,顶点,0,6,4,5,7,7,16,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,16,14,14,16,10,7,7,8,6,6,3,2,0,（1）e(i)=V
15、e(j) （2）l(i)=Vl(k)-dut(),习题三（图的拓扑和关键路径）,对下图，求每个活动的最早开始时间和最迟开始时间， 并确定关键活动及整个工程的最早结束时间。,0,19,15,29,38,43,43,38,37,19,15,0,0,0,19,19,15,15,29,38,38,37,15,19,27,27,0,17,第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,7.6 最短路径,用带权的有向图表示一个交通运输网，图中：顶点表示城市，弧表示城市间的交通联系，权表示此线路的长度或沿此线路运输所花的时间或费用等。 问题：从某顶点出发，沿图的弧到达另一顶点所经过的路径中，各弧上权值之和最小的一条路径最短路径。,问题提出：,7.6.1 从某个源点到其余各 顶点的最短路径,7.6.2 每一对顶点之间的最 短路径,7.6.1 从某个源点到其余各顶点的最短路径,无,（V0,V2） 10,（V0,V4,V3） 50,（V0,V4）
