ACM培训资料数据结构与算法.ppt

1、,数据结构 (DATA STRUCTURE),计算机科学与工程系,0,2,第七章 图,图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络,0,3,7.1 图的基本概念,图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y V 顶点 v 的出度是以 v 为始点(弧尾)的有向边的条数, 记作 OD(v)。 路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1

2、, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应是属于E 的边。,0,7,路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。 简单路径 若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 简单回路 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路,0,8,

3、路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1,0,9,7.2 图的存储结构,1）存储特点 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表； 还有一个表示各个顶点之间关系的邻接矩阵。 2）邻接矩阵 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 Ann，定义：,7.2.1 邻接矩阵(Adjacency Matrix)表示法,0,1

4、0,0,11,网络的邻接矩阵,0,12,3）数据类型描述,#define MaxVNum 100 /*最大顶点数设为100*/ typedef XXX VertexType; /*顶点类型*/ 邻接矩阵类型： typedef int EdgeType; /*边的权值设为整型*/ typedef struct ArcCell VertexType adj; InfoType *Info; / 存弧相关信息 ArcCell,AdjMatrixMaxVNumMaxVNum 图类型： typedef struct VertexType vexsMaxVNum; /*顶点表*/ AdjMatrix ar

5、cs; /*邻接矩阵，即边表*/ int vexnum,arcnum; /*图的顶点数和边数*/ Mgragh; /*Maragh是以邻接矩阵存储的图*/,0,13,4）图的创建,思路：,0,14,7.2.2 邻接表 (Adjacency List),1) 存储特点 对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个单链表，这个单链表称为顶点vi的邻接表； 将所有点的邻接表表头放到数组中，就构成了图的邻接表,0,15,特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：

6、有向图中对每个结点建立以Vi为头的弧的单链表,0,16,0,17,2）数据类型描述,define MaxVerNum 100 /*最大顶点数为100*/ 邻接表类型 ： typedef struct ArcNode int adjvex; /*邻接点域*/ InfoType *Info; /*表示边上信息的域info*/ struct ArcNode * next; /*指向下一个邻接点的指针域*/ ArcNode ; 表头结点类型 ： typedef struct Vnode VertexType vertex; /*顶点域*/ ArcNode * firstedge; /*边表头指针*/

7、Vnode,AdjList MaxVertexNum; 图的类型 ： typedef struct AdjList vertices; /*邻接表*/ int vexnum,arcnum; /*顶点数和边数*/ ALGraph; /*ALGraph是以邻接表方式存储的图类型*/,0,18,7.2.3 十字链表 (Orthogonal List),十字链表是有向图的另一种链式存储结构，它实际上是邻接表与逆邻接表的结合 1) 存储特点 图中每一条弧有一个结点，把弧头相同的弧连在同一链表上,弧尾相同的弧也连在同一链表上。结点结构为： 顶点结点为链表头结点，其结构为：,0,19,7.2.4 邻接多重表

8、(Adjacency Multilist),邻接多重表是无向图的另一种链式存储结构 1) 存储特点 图中每一条边用一个边结点表示，其结构为： 每个顶点用一个结点表示，其结构为：,0,20,在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 邻接多重表的结构,0,21,7.3 图的遍历与连通性,从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，叫做图的遍历 ( Graph Traversal )。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 vi

9、sited i 为 1，防止它被多次访问。,0,22,7.3.1 深度优先搜索DFS,1）基本思想： 任选图中一个顶点 v , 访问此顶点, 并作访问标记。 从 v 出发，访问它的任一未被访问过的邻接顶点 w ，作访问标记，并以 w 为新的出发点，继续进行深度优先搜索。 当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点k，从k的另一个没有被访问的邻接顶点出发进行深度优先搜索。 重复上述过程, 直到图中所有顶点都被访问过为止,0,23,深度优先搜索的示例,例,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,例,深度遍历：V1 V2 V4 V8 V3 V6 V7 V5,

10、0,24,深度优先搜索的示例,遍历结果：A、B、D、C,例,0,25,2）算法实现,难点： 如何标记已访问结点v ? 如何查找 v 的所有邻接点？ 解决办法： 设置一个布尔向量数组visitedn，初值为0。若序号为 i 的结点已被访问过，则visitedi=1。 根据图的存储方式不同，采取相应方法查找： 邻接矩阵：vi 的邻接点是邻接矩阵中第i 行上非0元素对应的列值，若Aij0，则vj为vi邻接点。 邻接表：是以G.verticesi为表头结点的单链表上的所有结点。,0,26,例,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,0,27,3）算法分析,图中有 n 个顶

11、点，e 条边。 由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。,0,28,7.3.2 广度优先搜索 BFS,1）基本思想： 任选图中一个顶点 v ，访问此顶点，并作访问标记。 从 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, , wt，并作访问标记。 然后再顺序访问 w1, w2, , wt 的所有还未被访问过的邻接顶点，并作访问标记。 如此做下去,直到图中所有顶点都被访问到为止,

12、0,29,广度优先搜索的示例,例,例,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V6 V7 V8 V5,0,30,广度优先搜索的示例,遍历结果：A、B、C、D,例,0,31,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。,2）算法实现,0,32,BFS,0,33,如果使用邻接表表示图，则循环的总时间代价为 d1 + d2 + + dn = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。,3）算

13、法分析,0,34,7.4 图的连通性与生成树,7.4.1 图的连通性问题 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,0,35,连通图,强连通图,非连通图 连通分量,0,36,7.4.2 最小生成树,1）图的生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树（所有顶点均由边连接在

14、一起，但不存在回路,有n-1条边），则该子图称为G的生成树。 生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。 使用不同的遍历图的方法，可以得到不同的生成树,0,37,说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,例,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：

15、V1 V2 V3 V4 V5 V6 V7 V8,0,39,例,0,40,问题提出 要在n个城市间建立通信联络网， 顶点 城市 权 城市间建立通信线路所需花费代价 生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。,2) 构造最小生成树,问题分析 n个城市间, 最多可设置n(n-1)/2条线路 n个城市间建立通信网, 只需n-1条线路 问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）最小,0,41,最小生成树的重要性质： 设 G =（V，E）是一个连通网络，U是顶点集V的一个真子集。若（u，v）是G中所有的一个顶点在U,另一个顶点不

16、在 U 的边中，具有最小权值的一条边，则一定存在 G 的一棵最小生成树包括此边。,0,42, 普里姆(Prim)算法,普里姆算法的基本思想： 假设图G = V, E ，所求最小生成树T=(U,TE), 其中U=V, TE E 从连通网络 G = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。 如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,0,43,算法实现: (略) 算法分析：,上述算法

17、的初始化时间是O(1)，k循环中有两个循环语句，其时间大致为：,令O(1)为某一正常数C，展开上述求和公式可知其数量级仍是 n 的平方。所以，整个算法的时间复杂性是O(n2),0,44, 克鲁斯卡尔 (Kruskal) 算法,克鲁斯卡尔算法的基本思想： 设有一个有 n 个顶点的连通网络 G = V, E ，最初先构造一个只有 n 个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。 在 E 中选取一条具有最小权值的边(u,v)，若该边的两个顶点落在两个不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。 如此上步，直到 T 中所有顶点在同一

18、个连通分量上为止。,0,45,应用克鲁斯卡尔算法构造最小生成树的过程,例,0,46,7.5 有向无环图及其应用,计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。,7.5.1 活动网络(Activity Network) 用顶点表示活动的网络 (AOV网络),0,47,C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5

19、, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8,课程代号,课程名称,先修课程,0,48,学生课程学习工程图,0,49,可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动间的优先关系，Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。 在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边， AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。,0

20、,50,检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 拓扑排序：从某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。,1） 拓扑排序,0,51,例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,0,52,2）进行拓扑排序的方法,输入AOV网络，令 n 为顶点个数 在AOV网络中

21、选一个没有直接前驱的顶点（即此顶点入度为0）, 并输出之； 从图中删去该顶点,同时删去所有它发出的有向边; 重复以上两步, 直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或 图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,0,53,例：拓扑排序的过程,(a) 有向无环图,(b) 输出顶点C4,(c) 输出顶点C0,(d) 输出顶点C3,0,54,(e) 输出顶点C2,(f) 输出顶点C1,C5,(g) 输出顶点C5,(h) 拓扑排序完成,0,55,AOV网络及其邻接表表示,在邻接表中增设

22、了一个count域，记录各个顶点入度。入度为零的顶点即无前驱的顶点。,0,56,3）拓扑排序算法,入度为0的顶点即为没有前驱的顶点。 删除顶点及相应弧的操作可转换为弧头顶点入度减1。 为避免重复检查入度为0 的顶点，在算法中使用一个链式栈将入度为 0 的顶点链接在一起，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。,0,57,算法描述,使用这种栈的拓扑排序算法可以描述如下： (1) 建立入度为零的顶点栈;输出顶点计数器=0 (2) 当入度为零的顶点栈不空时, 重复执行 从栈中取出顶点元素, 并输出之;计数器+1 从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减 1

23、; 如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈; (3) 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。,0,58,分析此拓扑排序算法可知，如果AOV网络有n 个顶点，e 条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有 n 个顶点，每个顶点进一次栈，出一次栈，共输出 n 次。顶点入度减一的运算共执行了 e 次。所以总的时间复杂度为O(n+e)。,4）算法分析,0,59,7.5.2 用边表示活动的网络(AOE网络),如果在无环的带权有向图中 用有向边表示一个工程中的活动(Activity) 用边上权值表示

24、活动持续时间(Duration) 用顶点表示事件 (Event) 则这样的有向图叫做用边表示活动的网络，简称 AOE (Activity On Edges) 网络。 AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设没有环)? (2) 为缩短完成工程所需的时间, 应当加快哪些活动?,0,60,在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需

25、的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,1）关键路径,0,61,要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。 关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径. 例如，下图就是一个AOE网。,0,62,2）如何求关键路径,定义几个与计算关键活动有关的量： 事件Vi 的最早发生时间Ve(i)是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟发生时间Vli是在保证汇点Vn 在Ven 时刻完成的前提下，事件Vi 的允许的最迟

26、开始时间。 活动ak 的最早开始时间ek：设活动ak 在边上，则ek是从源点V0到顶点Vi 的最长路径长度。因此, ek = Vei。 活动ak 的最迟开始时间lk 是在不会引起时间延误的前提下,该活动允许的最迟开始时间。 lk = Vlj - dur() 其中,dur()是完成 ak 所需的时间。,0,63,时间余量 lk - ek表示活动 ak 的最早开始时间和最迟开始时间的时间余量。lk = ek 表示活动 ak 是没有时间余量的关键活动。 为找出关键活动, 需要求各个活动的 ek 与 lk，以判别是否 lk = ek. 为求得 ek与 lk，需要先求得从源点 V0 到各个顶点 Vi 的

27、 Vei 和 Vli。,0,64,求Vei的递推公式 从 Ve1 = 0开始，向前递推 S2, j = 2, , n 其中 S2是所有指向顶点Vi 的有向边的集合 从Vln = Ven开始，反向递推 S1, j= n-1, n-2, ,1 其中 S1是所有从顶点Vi 发出的有向边的集合 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。,0,65,算法分析 在拓扑排序求Vei和逆拓扑有序求Vli时, 所需时间为O(n+e), 求各个活动的ek和lk时所需时间为O(e), 总共花费时间仍然是O(n+e)。,0,66,7.6 最短路径 (Shortest Path),问题提出: 用带

28、权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示沿此线路运输所花的时间或费用等 问题：从某顶点出发，沿图到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径 最短路径： 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。 问题解法 单源最短路径 Dijkstra算法 任意顶点对之间的最短路径 Floyd算法,0,67,7.6.1 单源最短路径问题,问题的提法： 给定一个带权有向图D与源点v，求从v 到 D 中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra 提出按路径长度的递增次序，逐步产生