数据结构演示稿7ppt课件

1、第第7章图章图 内容内容7.1 图的概念图的概念7.2 图的存贮结构图的存贮结构7.3 图的遍历图的遍历7.4 图的最小生成树图的最小生成树7.5 拓扑排序拓扑排序7.6 关键路径关键路径7.7 最短路径最短路径7.1.1图的定义 每个结点有任意多个前驱和后继结点.图也可以二元组表示:定义Graph=(v,E) v:表示元素集合 E:元素之间的关系现举两个例子，如下图：例一例二无向图中1，2和2，1代表同一边有向图中和表示两个不同的方向边以为例，在中：1称为此边的起点或尾弧尾）2称为此边的终点或头弧头）边的方向规定为弧尾弧头 V(G1)=1,2,3,4顶点集合;E(G1)=,边的集合顶点关系）

2、 V(G2)=1,2,3,4,5顶点集合;E(G2)=(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)边的集合 7.1.2图的基本术语 1、完全图：在一个有N个顶点的图中，若每个顶点到其它N-1顶点都有一条边，那么 图中有N个顶点且有N*（N-1）/2条边的图称为完全图。 2、邻接点：对无向图G=（V，E），若有V1，V2属于E则称V1和V2互为邻接点。 3、相关边：两个相邻接的点连成的边叫做这两个结点的相关边。4、度：与每个顶点相连的边的数叫该点的度。5、入度：对有向图中某结点的弧头数边的终点称为该结点的入度。6、出度：对有向图中某结点的弧尾数边的终点称为该结点的出度。

3、7、途径：在一图中若从某个顶点VP出发，沿着一些边经过顶点V1，V2，,VM到达VG则称顶点8、回路：从一顶点出发又回到该顶点，则所经过的路径称为回路。 9、子图 若G和G是两个图，且存在着V(G)V(G)和EG）EG的关系，则称G是G的子图10、有关连通的概念连通：在无向图中，若从顶点VI到顶点VJ之间有路径则称此二顶点是连通的。连通图：如果图中任意一对顶点之间都是连通的，则称此图为连通图。强连通：对于有向图，若从顶点VI到顶点VJ到顶点VI之间都有路径，则称这两点是强连通的。强连通图：图中任何一对顶点都是强连通的，则此图叫强连通图。连通分量：非连通图中的每一个连通部分连通分量：非连通图中的

4、每一个连通部分叫连通分量。叫连通分量。强连通分量：有向图中极大强连通子图称强连通分量：有向图中极大强连通子图称为有向图的强连通分量。为有向图的强连通分量。1111、生成树、生成树一个连通的生成树，它含有图中全部顶点，一个连通的生成树，它含有图中全部顶点，但只有足以构成树的但只有足以构成树的N-1N-1条边条边N N顶点个顶点个数）数）如图如图P159P15912. 12. 权、网权、网权：权： 有些图对应每条边有一相应的数值。有些图对应每条边有一相应的数值。这个数值叫该边的权。这个数值叫该边的权。网：网： 这种带权的图叫网。这种带权的图叫网。 注：不同网络的权有不同的意义：电注：不同网络的权有

5、不同的意义：电网络权可以是阻抗，运输网络中的权可网络权可以是阻抗，运输网络中的权可以是路程长度，运费等。以是路程长度，运费等。 7.1.3 图的几种基本操作 (1) LOC_VERTEX(G,v)顶点定位函数 顶点函数: 确定顶点在图G中的位置.若图中无此顶点，则函数值为零.(2) GET_VERTEX(G,i)取顶点函数 取点函数:求图G中第i个顶点.若i图G中顶点数则函数值为零. (3) FIRST_ADJ(G,v)求第一个邻接点函数 求第一个邻接点函数:求图G中顶点V的第一个邻接点.若v没有邻接点或图G中无顶点v,则函数值为零.P1567.2.1 邻接矩阵表示法(数组表示法)邻接矩阵表示

6、法-表示各顶点之间的邻接关系 可以借助二维数组作为存贮结构,故又称为数组表示法. 7.2.2 7.2.2 邻接表邻接表 邻接表是由邻接矩阵改造而来的一邻接表是由邻接矩阵改造而来的一种链接结构种链接结构, ,它只考虑非零元素它只考虑非零元素, ,因而节因而节省了零元素所占的存贮空间省了零元素所占的存贮空间. . 逆邻接表逆邻接表 链表中每个结点表示邻接矩阵中该链表中每个结点表示邻接矩阵中该顶点的列中每个非零元素顶点的列中每个非零元素 邻接矩阵是一个n*n的方阵 n为图的顶点数矩阵每一行分别对应图的各个顶点矩阵的每一列分别对应图的各个顶点 1 规定矩阵元素aij= 0几点说明几点说明: :1.1.

7、如果图的各边是带权的如果图的各边是带权的, ,也可以用邻接也可以用邻接矩阵来表示矩阵来表示, ,只需将矩阵中只需将矩阵中1 1元素换成相元素换成相应边的权值应边的权值. . 2. 2.邻接矩阵表示法对于以图的顶点为主的邻接矩阵表示法对于以图的顶点为主的运算比较适用运算比较适用. . 3. 3.除完全图外除完全图外, ,其他图的邻接矩阵有许多其他图的邻接矩阵有许多零元素零元素, ,特别是当特别是当n n值较大值较大, ,而边数又少是而边数又少是, ,则此矩阵称为则此矩阵称为 稀疏矩阵稀疏矩阵.浪费存储空间浪费存储空间. . 邻接表与邻接矩阵的关系邻接表与邻接矩阵的关系: : 1. 1.与邻接矩阵

8、的每一行有一个线形链接表与邻接矩阵的每一行有一个线形链接表. .2.2.链接表的表头对应着邻接矩阵该行的顶点链接表的表头对应着邻接矩阵该行的顶点. .3.3.链接表中的每个结点对应着邻接矩阵正中链接表中的每个结点对应着邻接矩阵正中该行的一个非零元素该行的一个非零元素无向图无向图: :一个非零元素表示与该行顶点相邻一个非零元素表示与该行顶点相邻接的另一个顶点接的另一个顶点有向图有向图: :非零元素则表示该行顶点为起点的非零元素则表示该行顶点为起点的一条边的终点一条边的终点几点说明几点说明: : 1. 1.在邻接表中的每个线性链接表中各结在邻接表中的每个线性链接表中各结点的的顺序是任意的点的的顺序

9、是任意的. .2.2.邻接表中的各个线性链接表不说明它邻接表中的各个线性链接表不说明它们顶点之间的邻接关系们顶点之间的邻接关系. .3.3.对于无向图对于无向图: : 某顶点的度数某顶点的度数= =该顶点对应的线性链该顶点对应的线性链表的结点数表的结点数 对于有向图对于有向图: : 某顶点的某顶点的 出度出度 数数= =该顶点对应的线该顶点对应的线性链表的结点数性链表的结点数 逆邻接表逆邻接表 链表中每个结点表示邻接矩阵中该链表中每个结点表示邻接矩阵中该顶点的列中每个非零元素顶点的列中每个非零元素 什么叫图的遍历什么叫图的遍历 从图的任意点出发沿着一些边访问从图的任意点出发沿着一些边访问图中的

10、所有顶点图中的所有顶点, ,且使每个顶点仅被访问且使每个顶点仅被访问一次一次, ,这就叫图的遍历这就叫图的遍历. .l深度优先搜索深度优先搜索dfs dfs l广度优先搜索广度优先搜索bfs bfs 方法方法: : 从图中指定的起点从图中指定的起点v0v0出发出发( (先访问先访问v)v)访问它的任意相邻接的顶点访问它的任意相邻接的顶点w1,w1,再访问再访问w1w1的任一个未访问的相邻接顶点的任一个未访问的相邻接顶点w2,w2,如此下如此下去去, ,直到某顶点已无被访问过的顶点直到某顶点已无被访问过的顶点, ,则则返回一步找前一个顶点的其他沿未被访返回一步找前一个顶点的其他沿未被访问的邻接顶

11、点问的邻接顶点, ,重复以上过程直到所有的重复以上过程直到所有的顶点都被访问顶点都被访问 顶点的访问序列：V1V2V4V8V5V3V6V7方法方法: : 从图指定的起点从图指定的起点v0v0出发出发, ,访问与它相访问与它相邻的所有顶点邻的所有顶点w1,w2,.w1,w2,.然后再依次访然后再依次访问问w1,w2.w1,w2.邻接的尚未被访问的所有邻接的尚未被访问的所有顶点顶点, ,再从这些顶点出发访问与它们相邻再从这些顶点出发访问与它们相邻接的尚未被访问的顶点接的尚未被访问的顶点, ,直到所有顶点均直到所有顶点均被访问过为止被访问过为止. . 顶点的访问序列：V1V2V3V4V5V6V7V8

12、7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树 1. 连通分量连通分量 非连通图的每一个连通部分叫连通分量非连通图的每一个连通部分叫连通分量. P159 G3 图7.3(a) 邻接表阐明：阐明： 该图中包括三个连通分量，若按该图中包括三个连通分量，若按dfs分分别从三个顶点别从三个顶点I，D，B出发可得到出发可得到三个连通分量的顶点序列：三个连通分量的顶点序列：I，G，K，HD，EB，M，L，J，A，F，C 2. 图的生成树图的生成树 图中全部顶点和搜索过程所经过的边图中全部顶点和搜索过程所经过的边,构成该连通图的生成树构成该连通图的生成树. 例如上图搜索遍历后得到的三棵树例如上

13、图搜索遍历后得到的三棵树 由此可以总结生成树的特点: 任意两个顶点之间有且仅有一条路径如再增加一条边,就会出现一条回路,如果去掉一条边此子图就会变成非连通图. 7.4.2 最小生成树最小生成树 1 什么叫最小生成树什么叫最小生成树 给定一个带权的无向连通图给定一个带权的无向连通图,如何选取如何选取一棵生成树一棵生成树,使树上所有边上权的总和使树上所有边上权的总和为最小为最小,这叫最小生成树这叫最小生成树. 2.求最小生成树的算法求最小生成树的算法 克鲁斯卡尔算法克鲁斯卡尔算法 普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法 方法方法: :将图中边按其权值由小到大的次将图中边按其权值由小到大

14、的次序顺序选取序顺序选取, ,若选边后不形成回路若选边后不形成回路, ,则保留则保留作为一条边作为一条边, ,若形成回路则除去若形成回路则除去. .依次选够依次选够(n-1)(n-1)条边条边, ,即得最小生成树即得最小生成树.(n.(n为顶点数为顶点数) ) 分析：该方法对于边相对比较多的不是很分析：该方法对于边相对比较多的不是很实用实用, ,浪费时间浪费时间. . 普里姆算法普里姆算法 方法方法: :从指定顶点开始将它加入集合从指定顶点开始将它加入集合中中, ,然后将集合内的顶点与集合外的顶点然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条所构成的所有边中选取权值最小的一

15、条边作为生成树的边边作为生成树的边, ,并将集合外的那个顶并将集合外的那个顶点加入到集合中点加入到集合中, ,表示该顶点已连通表示该顶点已连通. .再再用集合内的顶点与集合外的顶点构成的用集合内的顶点与集合外的顶点构成的边中找最小的边边中找最小的边, ,并将相应的顶点加入集并将相应的顶点加入集合中合中, ,如此下去直到全部顶点都加入到集如此下去直到全部顶点都加入到集合中合中, ,即得最小生成树即得最小生成树. . 有向无环图: 是一个无环的有向图.简称DAG图. 有向无环图的作用: 常用来描述一个工程或一个系统的进行的过程. 7.5.1 AOV网网 有向无环图可以描述一个过程或一有向无环图可以

16、描述一个过程或一个系统个系统.那么在一个过程或一个系统中又那么在一个过程或一个系统中又可以映射多个子过程或子系统可以映射多个子过程或子系统.比如我们比如我们熟悉的教学计划熟悉的教学计划,一个教学计划中又可以一个教学计划中又可以包含许多课程包含许多课程(子计划子计划),当这些子计划都当这些子计划都完成后完成后,整个教学计划方算完成整个教学计划方算完成.我们可以我们可以把每个子计划称为活动把每个子计划称为活动. 阐明：阐明： 在各个活动之间在各个活动之间,有些必须按规定的先后有些必须按规定的先后次序进行次序进行,有些则没有次序要求有些则没有次序要求. 把这种活动之间的次序要求把这种活动之间的次序要

17、求,可用一个有向可用一个有向图来表示图来表示. 图中每个顶点代表一个活动图中每个顶点代表一个活动.如果从如果从顶点顶点vi到顶点到顶点vj之间存在有向边之间存在有向边则表示则表示活动活动i必须先于活动必须先于活动j进行进行.这种图中用顶点表这种图中用顶点表示活动的网络称为示活动的网络称为AOV网网. AOV网的特点网的特点:在网中一定不能有有向回路在网中一定不能有有向回路. 检测网中是否存在环检测网中是否存在环,可用拓扑排序的方法可用拓扑排序的方法. 1.什么叫拓扑排序什么叫拓扑排序 将将AOV网中各个顶点排列成一个有序网中各个顶点排列成一个有序序列序列,使得所有前驱和后继关系都能得到满使得所

18、有前驱和后继关系都能得到满足足,而那些没有次序的顶点而那些没有次序的顶点,在拓扑排序的序在拓扑排序的序列中可以插到任意位置列中可以插到任意位置.也可说拓扑排序是也可说拓扑排序是对非线形结构的有向图进行线形化的重要手对非线形结构的有向图进行线形化的重要手段段. 2.拓扑排序的方法拓扑排序的方法 由由AOV网选取某个没有前驱的顶点网选取某个没有前驱的顶点,排到序列中排到序列中,凡取出某顶点凡取出某顶点,即将它与它相即将它与它相关联的边从图中删掉关联的边从图中删掉,随着边的删除随着边的删除,又会又会有无前驱的顶点有无前驱的顶点,重复如此进行重复如此进行,直到全部直到全部顶点都排到序列中去顶点都排到序

19、列中去. 例：如图例：如图P181图图7.27 AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应的是。它通常表示一个工程的计划或进度。 AOE网是一个有向带权图，图中的： 边：表示活动(子工程)， 边上的权：表示该活动的持续时间，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。 其中有两个特殊的顶点(事件)，一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出

20、边。除这两个顶点外，其余顶点都既有入边，也有出边，是入边活动和出边活动的转接点。 在一个AOE网中，若包含有n个事件，通常令源点为第0个事件，汇点为第n-1个事件，其余事件的编号(即顶点序号)分别为1n-2。 一个AOE网如图，该网中包含有 活动和 事件。 如图P183图7.29一个AOV网11项9个 (1)整个工程至少需要多长时间完成?(2)哪些活动是影响工程进度的关键? 在AOE网中，一个顶点事件的发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后，即只要有一个入边活动没有完成，该事件就不可能发生。所以： 一个事件的最早发生时间是它的所有入边活动，或者说最后一个入边活动刚完成的时间

21、。 一个活动的开始必须在它的起点事件发生之后，也就是说，一个顶点事件没有发生时，它的所有出边活动(或称后继活动)都不可能开始，所以： 一个活动的最早开始时间是它的起点事件的最早发生时间。若用vej表示顶点vj事件的最早发生时间，用ei表示vj一条出边活动ai的最早开始时间，则有ei=vej。 对于源点事件来说，因为它没有入边，所以随时都可以发生，整个工程的开始时间就是它的发生时间，亦即最早发生时间，通常把此时间定义为0，从此开始推出其他事件的最早发生时间。例：分析图7.29 事件的最迟发生时间：在不影响整个工程按时事件的最迟发生时间：在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时

22、完成的前提下，一些事件可以不在最早发生时间发生，而允许向后推迟一些时间发生，我们间发生，而允许向后推迟一些时间发生，我们把最晚必须发生的时间叫做该事件的最迟发生把最晚必须发生的时间叫做该事件的最迟发生时间。时间。 同样，在不影响整个工程按时完成的前提同样，在不影响整个工程按时完成的前提下，一些活动可以不在最早开始时间开始，而下，一些活动可以不在最早开始时间开始，而允许向后推迟一些时间开始，我们把最晚必须允许向后推迟一些时间开始，我们把最晚必须开始的时间叫做该活动的最迟开始时间。开始的时间叫做该活动的最迟开始时间。AOE网中的任一个事件若在最迟发生时间仍没有发网中的任一个事件若在最迟发生时间仍没

23、有发生或任一项活动在最迟开始时间仍没有开始，生或任一项活动在最迟开始时间仍没有开始，则必将影响整个工程的按时完成，使工期拖延。则必将影响整个工程的按时完成，使工期拖延。5根据根据AOE网中每个事件的最早发生时网中每个事件的最早发生时间和最迟发生时间计算出每个活动的最间和最迟发生时间计算出每个活动的最早开始时间和最迟开始时间。早开始时间和最迟开始时间。 有些活动的开始时间余量不为0，表明这些活动不在最早开始时间开始，至多向后拖延相应的开始时间余量所规定的时间开始也不会延误整个工程的进展。如对于活动a5，它最早可以从整个工程开工后的第4天开始，至多向后拖延两天，即从第6天开始。 有些活动的开始时间余量为0，表明这些活动只能在最早开始时间开始，并且必须在持续时间内按时完成，否则将拖延整个工期。我们把开始时间余量为0的活动称为关键活动，由关键活动所