ACM培训数据结构与算法课件

1、01第七章 图图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络第1页，共72页。027.1 图的基本概念图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条通路。第2页，共72页。03 有向图与无向图完全图第3页，共72页。04 邻接顶点 如果 (u,

2、v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。子图 设有两个图G(V, E)和G(V, E), 若 V V 且 E E, 则称 图G 是图G 的子图。第4页，共72页。05顶点的度 一个顶点v 的度是与它相关联的边的条数，记作TD(v)。顶点 v 的入度 是以 v 为终点(弧头)的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点(弧尾)的有向边的条数, 记作 OD(v)。路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj )

3、为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应是属于E 的边。第5页，共72页。06路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径 若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。简单回路 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路 第6页，共72页。07例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路

4、径：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第7页，共72页。087.2 图的存储结构1）存储特点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表；还有一个表示各个顶点之间关系的邻接矩阵。2）邻接矩阵 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 Ann，定义：7.2.1 邻接矩阵(Adjacency Matrix)表示法第8页，共72页。09第9页，共72页。010 网络的邻接矩阵第10页

5、，共72页。0113）数据类型描述#define MaxVNum 100 /*最大顶点数设为100*/typedef XXX VertexType; /*顶点类型*/邻接矩阵类型： typedef int EdgeType; /*边的权值设为整型*/ typedef struct ArcCell VertexType adj; InfoType *Info; / 存弧相关信息 ArcCell,AdjMatrixMaxVNumMaxVNum 图类型： typedef struct VertexType vexsMaxVNum; /*顶点表*/ AdjMatrix arcs; /*邻接矩阵，即边表

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

7、表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext第14页，共72页。015第15页，共72页。0162）数据类型描述define MaxVerNum 100 /*最大顶点数为100*/邻接表类型 ： typedef struct ArcNode int adjvex; /*邻接点域*/ InfoType *Info; /*表示边上信息的域info*/ struct ArcNode * next; /*指向下一个邻接点的指针域*/ ArcNode ; 表头结点类型 ： typedef struct V

8、node VertexType vertex; /*顶点域*/ ArcNode * firstedge; /*边表头指针*/ Vnode,AdjList MaxVertexNum; 图的类型 ： typedef struct AdjList vertices; /*邻接表*/ int vexnum,arcnum; /*顶点数和边数*/ ALGraph; /*ALGraph是以邻接表方式存储的图类型*/第16页，共72页。0177.2.3 十字链表 (Orthogonal List) 十字链表是有向图的另一种链式存储结构，它实际上是邻接表与逆邻接表的结合1) 存储特点图中每一条弧有一个结点，把弧

9、头相同的弧连在同一链表上,弧尾相同的弧也连在同一链表上。结点结构为：顶点结点为链表头结点，其结构为：第17页，共72页。0187.2.4 邻接多重表(Adjacency Multilist) 邻接多重表是无向图的另一种链式存储结构1) 存储特点 图中每一条边用一个边结点表示，其结构为：每个顶点用一个结点表示，其结构为：mark ivex ilink jvex jlinkdata firstedge第18页，共72页。019 在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 邻接多重表的结构例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2第19页

10、，共72页。0207.3 图的遍历与连通性从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，叫做图的遍历 ( Graph Traversal )。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。第20页，共72页。0217.3.1 深度优先搜索DFS1）基本思想：任选图中一个顶点 v , 访问此顶点, 并作访问标记。从 v 出发，访问它的任一未被访问过的邻接顶点 w ，作访问标记，并以 w 为新的出发点，继续进行深度优

11、先搜索。当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点k，从k的另一个没有被访问的邻接顶点出发进行深度优先搜索。重复上述过程, 直到图中所有顶点都被访问过为止第21页，共72页。022深度优先搜索的示例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5第22页，共72页。023深度优先搜索的示例遍历结果：A、B、D、C例第23页，共72页。0242）算法实现难点：如何标记已访问结点v ?如何查找 v 的所有邻接点？解决办法：设置一个布尔向量数组v

12、isitedn，初值为0。若序号为 i 的结点已被访问过，则visitedi=1。根据图的存储方式不同，采取相应方法查找： 邻接矩阵：vi 的邻接点是邻接矩阵中第i 行上非0元素对应的列值，若Aij0，则vj为vi邻接点。 邻接表：是以G.verticesi为表头结点的单链表上的所有结点。第24页，共72页。025V1V2V4V5V3V7V6V8例1234V1V3V4V2vexdatafirstarc 2 7 8 3adjvexnext5V5 6 4 8 2V6V7V8678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V5第25页，共72页。0263）算法分析图中有 n 个顶点，e

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

14、，共72页。028广度优先搜索的示例例V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V6 V7 V8 V5第28页，共72页。029广度优先搜索的示例遍历结果：A、B、C、D例第29页，共72页。030为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。2）算法实现开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi=Vexnums结束NNYY第30页，共72页。031 BFS开始访问Vi,置标志求V邻接点WW存在吗V下一邻接点WW

15、访问过结束NYNY初始化队列Vi入队队列空吗队头V出队访问W,置标志W入队NaaY第31页，共72页。032如果使用邻接表表示图，则循环的总时间代价为 d1 + d2 + + dn = O(e)，其中的 di 是顶点 i 的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。3）算法分析第32页，共72页。0337.4 图的连通性与生成树7.4.1 图的连通性问题连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量

16、。强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。第33页，共72页。034连通图例245136强连通图356例非连通图连通分量例245136第34页，共72页。0357.4.2 最小生成树 1）图的生成树连通图G的一个子图如果是一棵包含G的所有顶点的树（所有顶点均由边连接在一起，但不存在回路,有n-1条边），则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。使用不同的遍历图

17、的方法，可以得到不同的生成树第35页，共72页。036说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKI第36页，共72页。V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度

18、遍历：V1 V2 V3 V4 V5 V6 V7 V8第37页，共72页。038例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林第38页，共72页。039 问题提出 要在n个城市间建立通信联络网， 顶点 城市 权 城市间建立通信线路所需花费代价 生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。2) 构造最小生成树 问题分析 n个城市间, 最多可设置n(n-1)/2条线路 n个城市间建立通信网, 只需n-1条线路 问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）最小1654327131791812752410第

19、39页，共72页。040最小生成树的重要性质： 设 G =（V，E）是一个连通网络，U是顶点集V的一个真子集。若（u，v）是G中所有的一个顶点在U,另一个顶点不在 U 的边中，具有最小权值的一条边，则一定存在 G 的一棵最小生成树包括此边。uvUVU第40页，共72页。041 普里姆(Prim)算法普里姆算法的基本思想： 假设图G = V, E ，所求最小生成树T=(U,TE), 其中U=V, TE E 从连通网络 G = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点不在U中的各

20、条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。 如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。第41页，共72页。042 算法实现: (略) 算法分析： 上述算法的初始化时间是O(1)，k循环中有两个循环语句，其时间大致为： 令O(1)为某一正常数C，展开上述求和公式可知其数量级仍是 n 的平方。所以，整个算法的时间复杂性是O(n2)第42页，共72页。043 克鲁斯卡尔 (Kruskal) 算法克鲁斯卡尔算法的基本思想：设有一个有 n 个顶点的连通网络 G = V, E ，最初先构造一个只有 n 个顶点，没有边的非连通图 T = V, , 图中每个顶点自成

21、一个连通分量。在 E 中选取一条具有最小权值的边(u,v)，若该边的两个顶点落在两个不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。如此上步，直到 T 中所有顶点在同一个连通分量上为止。第43页，共72页。044应用克鲁斯卡尔算法构造最小生成树的过程例165432651356642516543212345第44页，共72页。0457.5 有向无环图及其应用计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要

22、求先修课程，有些则不要求。7.5.1 活动网络(Activity Network) 用顶点表示活动的网络 (AOV网络)第45页，共72页。046 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 课程代号课程名称先修课程第46页，共72页。047学生课程学习工程图第47页，共72页。048可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动间的优先关系，Vi 必须先于活动Vj 进行。这种有向

23、图叫做顶点表示活动的AOV网络(Activity On Vertices)。 在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边， AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。第48页，共72页。049检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。拓扑排序：从某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。1） 拓扑排序

24、第49页，共72页。050例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6第50页，共72页。0512）进行拓扑排序的方法 输入AOV网络，令 n 为顶点个数在AOV网络中选一个没有直接前驱的顶点（即此顶点入度为0）, 并输出之；从图中删去该顶点,同时删去所有它发出的有向边;重复以上两步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们

25、都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。第51页，共72页。052C0C1C2C3C4C5例：拓扑排序的过程(a) 有向无环图(b) 输出顶点C4(c) 输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d) 输出顶点C3第52页，共72页。053C1C2C5(e) 输出顶点C2C5C1(f) 输出顶点C1C5(g) 输出顶点C5(h) 拓扑排序完成第53页，共72页。054AOV网络及其邻接表表示C0C1C2C3C4C5 dest next C0 C1 C2 C3 0 C4 C5 0012345count data adj 13010

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

27、出之;计数器+1从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减 1;如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈; (3) 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。第56页，共72页。057分析此拓扑排序算法可知，如果AOV网络有n 个顶点，e 条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有 n 个顶点，每个顶点进一次栈，出一次栈，共输出 n 次。顶点入度减一的运算共执行了 e 次。所以总的时间复杂度为O(n+e)。4）算法分析第57页，共72页。0587.5.2 用边表示活动的网络(A

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

29、成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。1）关键路径第59页，共72页。0601324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径. 例如，下图就是一个AOE网。第60页，共

30、72页。0612）如何求关键路径定义几个与计算关键活动有关的量：事件Vi 的最早发生时间Ve(i)是从源点V0 到顶点Vi 的最长路径长度。事件Vi 的最迟发生时间Vli是在保证汇点Vn 在Ven 时刻完成的前提下，事件Vi 的允许的最迟开始时间。活动ak 的最早开始时间ek：设活动ak 在边上，则ek是从源点V0到顶点Vi 的最长路径长度。因此, ek = Vei。活动ak 的最迟开始时间lk 是在不会引起时间延误的前提下,该活动允许的最迟开始时间。 lk = Vlj - dur() 其中,dur()是完成 ak 所需的时间。第61页，共72页。062时间余量 lk - ek表示活动 ak

31、的最早开始时间和最迟开始时间的时间余量。lk = ek 表示活动 ak 是没有时间余量的关键活动。为找出关键活动, 需要求各个活动的 ek 与 lk，以判别是否 lk = ek.为求得 ek与 lk，需要先求得从源点 V0 到各个顶点 Vi 的 Vei 和 Vli。第62页，共72页。063求Vei的递推公式从 Ve1 = 0开始，向前递推 S2, j = 2, , n 其中 S2是所有指向顶点Vi 的有向边的集合 从Vln = Ven开始，反向递推 S1, j= n-1, n-2, ,1 其中 S1是所有从顶点Vi 发出的有向边的集合这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下

32、进行。第63页，共72页。064 算法分析 在拓扑排序求Vei和逆拓扑有序求Vli时, 所需时间为O(n+e), 求各个活动的ek和lk时所需时间为O(e), 总共花费时间仍然是O(n+e)。第64页，共72页。0657.6 最短路径 (Shortest Path)问题提出: 用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示沿此线路运输所花的时间或费用等 问题：从某顶点出发，沿图到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径最短路径： 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。问题解法单源最短路径 Dijkstra算法任意顶点对之间的最短路径 Floyd算法第65页，共72页。0667.6.