数据结构(C语言版)ppt课件

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)=,边的集合顶点关系 V

2、(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、出度：对有向图中某结点的弧尾数边的终点称为该结点的出度。7、途

3、径：在一图中假设从某个顶点VP出发，沿着一些边经过顶点V1，V2，,VM到达VG那么称顶点8、回路：从一顶点出发又回到该顶点，那么所经过的途径称为回路。 9、子图 假设G和G是两个图，且存在着V(G)V(G)和EGEG的关系，那么称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几点阐明

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

8、 : 1. 1.与邻接矩阵的每一行有一个线形链接表与邻接矩阵的每一行有一个线形链接表. .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.邻接的尚未被访问的一切邻接的尚未被访问的一切顶点顶点, ,再从这些顶点出发访问与它们相邻再从这些顶点出发访问与它们相邻接的尚未被访问的顶点接的尚未被访问的顶点, ,直到一切顶点均直到一切顶点均被访问过为止被访问过为止. . 顶点的访问序列

12、：V1V2V3V4V5V6V7V87.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 A

16、OV网网 有向无环图可以描画一个过程或一有向无环图可以描画一个过程或一个系统个系统.那么在一个过程或一个系统中又那么在一个过程或一个系统中又可以映射多个子过程或子系统可以映射多个子过程或子系统.比如我们比如我们熟习的教学方案熟习的教学方案,一个教学方案中又可以一个教学方案中又可以包含许多课程包含许多课程(子方案子方案),当这些子方案都当这些子方案都完成后完成后,整个教学方案方算完成整个教学方案方算完成.我们可以我们可以把每个子方案称为活动把每个子方案称为活动. 阐明：阐明： 在各个活动之间在各个活动之间,有些必需按规定的先后有些必需按规定的先后次序进展次序进展,有些那么没有次序要求有些那么没有

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的活动称为关键活动，由关键活