869-数据结构（C语言版）第7章图.ppt

《869-数据结构（C语言版）第7章图.ppt》由会员分享，可在线阅读，更多相关《869-数据结构（C语言版）第7章图.ppt（52页珍藏版）》请在三一文库上搜索。

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

2、E(G1)=,边的集合 （顶点关系） 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、入度：对有向图中某结点的弧头数（边的终点 ）称为该

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

4、连通图：图中任何一对顶点都是强连 通的，则此图叫强连通图。 连通分量：非连通图中的每一个连通部分 叫连通分量。 强连通分量：有向图中极大强连通子图称 为有向图的强连通分量。 11、生成树 一个连通的生成树，它含有图中全部顶点 ，但只有足以构成树的N-1条边（N顶点 个数） 如图P159 12. 权、网 权： 有些图对应每条边有一相应的数值 。这个数值叫该边的权。 网： 这种带权的图叫网。 注：不同网络的权有不同的意义： 电网络权可以是阻抗，运输网络中的权 可以是路程长度，运费等。 7.1.3 图的几种基本操作 (1) LOC_VERTEX(G,v)顶点定位函数 顶点函数: 确定顶点在图G中的位

5、置.若图中 无此顶点，则函数值为零. (2) GET_VERTEX(G,i)取顶点函数 取点函数:求图G中第i个顶点.若i图G中顶 点数则函数值为零. (3) FIRST_ADJ(G,v)求第一个邻接点函数 求第一个邻接点函数:求图G中顶点V 的第一个邻接点.若v没有邻接点或图G中无顶 点v,则函数值为零. P156 7.2 图的存贮结构 7.2.1 邻接矩阵表示法(数组表示法) 邻接矩阵表示法-表示各顶点之间的邻接 关系 可以借助二维数组作为存贮结构, 故又称为数组表示法. 7.2.2 邻接表 邻接表是由邻接矩阵改造而来的一 种链接结构,它只考虑非零元素,因而节 省了零元素所占的存贮空间.

6、逆邻接表 链表中每个结点表示邻接矩阵中该 顶点的列中每个非零元素 图的存贮结构说明 邻接矩阵是一个n*n的方阵 ln为图的顶点数 l矩阵每一行分别对应图的各个顶点 l矩阵的每一列分别对应图的各个顶点 1 规定矩阵元素aij= 0 几点说明: 1.如果图的各边是带权的,也可以用邻 接矩阵来表示,只需将矩阵中1元素换成 相应边的权值. 2.邻接矩阵表示法对于以图的顶点为主 的运算比较适用. 3.除完全图外,其他图的邻接矩阵有许多 零元素,特别是当n值较大,而边数又少 是,则此矩阵称为“稀疏矩阵“.浪费存储 空间. 邻接表与邻接矩阵的关系: 1.与邻接矩阵的每一行有一个线形链接表. 2.链接表的表头

7、对应着邻接矩阵该行的顶 点. 3.链接表中的每个结点对应着邻接矩阵正 中该行的一个非零元素 无向图:一个非零元素表示与该行顶点相邻 接的另一个顶点 有向图:非零元素则表示该行顶点为起点的 一条边的终点 几点说明: 1.在邻邻接表中的每个线线性链链接表中各 结结点的的顺顺序是任意的. 2.邻邻接表中的各个线线性链链接表不说说明 它们顶们顶 点之间间的邻邻接关系. 3.对对于无向图图: 某顶顶点的度数=该顶该顶 点对应对应 的线线性 链链表的结结点数 对对于有向图图: 某顶顶点的“出度“数=该顶该顶 点对应对应 的 线线性链链表的结结点数 逆邻接表 链表中每个结点表示邻接矩阵中该 顶点的列中每个非

8、零元素 7.3 图的遍历 什么叫图的遍历 从图的任意点出发沿着一些边访问 图中的所有顶点,且使每个顶点仅被访 问一次,这就叫图的遍历. 图的遍历的两种方法 l深度优先搜索dfs l广度优先搜索bfs 1.深度优先搜索dfs 方法: 从图中指定的起点v0出发(先访问 v)访问它的任意相邻接的顶点w1,再访 问w1的任一个未访问的相邻接顶点w2, 如此下去,直到某顶点已无被访问过的 顶点,则返回一步找前一个顶点的其他 沿未被访问的邻接顶点,重复以上过程 直到所有的顶点都被访问 例： 顶点的访问序列： V1 V2 V4 V8 V5 V3 V6 V7 2.广度优先搜索bfs 方法: 从图指定的起点v0

9、出发,访问与它 相邻的所有顶点w1,w2,.然后再依 次访问w1,w2邻接的尚未被访问 的所有顶点,再从这些顶点出发访问与 它们相邻接的尚未被访问的顶点,直到 所有顶点均被访问过为止. 例： 顶点的访问序列： V1 V2 V3 V4 V5 V6 V7 V8 7.4 图的最小生成树 7.4.1 无向图的连通分量和生成树 1. 连通分量 非连通图的每一个连通部分叫连通分 量. P159 G3 图7.3(a) 邻接表 说明： 该图中包括三个连通分量，若按 dfs分别从三个顶点（I，D，B）出发可 得到三个连通分量的顶点序列： I，G，K，H D，E B，M，L，J，A，F，C 2. 图的生成树 图中

10、全部顶点和搜索过程所经过的 边,构成该连通图的生成树. 例如上图搜索遍历后得到的三棵树 由此可以总结生成树的特点: 任意两个顶点之间有且仅有一条路 径如再增加一条边,就会出现一条回路, 如果去掉一条边此子图就会变成非连通 图. 7.4.2 最小生成树 1 什么叫最小生成树 给定一个带权的无向连通图,如何 选取一棵生成树,使树上所有边上权的 总和为最小,这叫最小生成树. 2.求最小生成树的算法 l克鲁斯卡尔算法 l普里姆算法 例： 克鲁斯卡尔算法 方法:将图中边按其权值由小到大 的次序顺序选取,若选边后不形成回路, 则保留作为一条边,若形成回路则除去. 依次选够(n-1)条边,即得最小生成树 .

11、(n为顶点数) 分析：该方法对于边相对比较多的不是很 实用,浪费时间. 普里姆算法 方法:从指定顶点开始将它加入集 合中,然后将集合内的顶点与集合外的 顶点所构成的所有边中选取权值最小的 一条边作为生成树的边,并将集合外的 那个顶点加入到集合中,表示该顶点已 连通.再用集合内的顶点与集合外的顶 点构成的边中找最小的边,并将相应的 顶点加入集合中,如此下去直到全部顶 点都加入到集合中,即得最小生成树. 7.5 有向无环图及其应用 有向无环图: 是一个无环的有向图.简称DAG图. 有向无环图的作用: 常用来描述一个工程或一个系统的 进行的过程. 7.5.1 AOV网 有向无环图可以描述一个过程或一

12、 个系统.那么在一个过程或一个系统中 又可以映射多个子过程或子系统.比如 我们熟悉的教学计划,一个教学计划中 又可以包含许多课程(子计划),当这些子 计划都完成后,整个教学计划方算完成. 我们可以把每个子计划称为活动. 说明： 在各个活动之间,有些必须按规定的先 后次序进行,有些则没有次序要求. 把这种活动之间的次序要求,可用一个有 向图来表示. 图中每个顶点代表一个活动.如 果从顶点vi到顶点vj之间存在有向边 则表示活动i必须先于活动j进行.这种图中用 顶点表示活动的网络称为AOV网. AOV网的特点:在网中一定不能有有向回路 . 检测网中是否存在环,可用拓扑排序的方法 . 7.5.2 拓

13、扑排序 1.什么叫拓扑排序 将AOV网中各个顶点排列成一个有序 序列,使得所有前驱和后继关系都能得到满 足,而那些没有次序的顶点,在拓扑排序的 序列中可以插到任意位置.也可说拓扑排序 是对非线形结构的有向图进行线形化的重 要手段. 2.拓扑排序的方法 由AOV网选取某个没有前驱的顶 点,排到序列中,凡取出某顶点,即将它与 它相关联的边从图中删掉,随着边的删 除,又会有无前驱的顶点,重复如此进行, 直到全部顶点都排到序列中去. 例：如图P181 图7.27 7.6 关键路径 AOE网(Activity On Edge network) ，即边表示活动的网络，与AOV网相对 应的是。它通常表示一个

14、工程的计划或 进度。 AOE网是一个有向带权图，图中的： 边：表示活动(子工程)， 边上的权：表示该活动的持续时间 ，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动 之间的转接点，即表示它的所有入边活 动到此完成，所有出边活动从此开始。 其中有两个特殊的顶点(事件)，一 个称做源点，它表示整个工程的开始， 亦即最早活动的起点，显然它只有出边 ，没有入边；另一个称做汇点，它表示 整个工程的结束，亦即最后活动的终点 ，显然它只有入边，没有出边。除这两 个顶点外，其余顶点都既有入边，也有 出边，是入边活动和出边活动的转接点 。 在一个AOE网中，若包含有n个事 件，通常令源点为第0个事件

15、，汇点为 第n-1个事件，其余事件的编号(即顶点 序号)分别为1n-2。 一个AOE网如图，该网中包含有 活动和 事件。 如图P183 图7.29 一个AOV网 11项 9个 对于一个AOE网，待研究的问题是： (1)整个工程至少需要多长时间完成? (2)哪些活动是影响工程进度的关键? 1事件的最早发生时间与活动的最早开始时间的关系 在AOE网中，一个顶点事件的发生或出现必须 在它的所有入边活动(或称前驱活动)都完成之后，即 只要有一个入边活动没有完成，该事件就不可能发 生。所以： 一个事件的最早发生时间是它的所有入边活动， 或者说最后一个入边活动刚完成的时间。 一个活动的开始必须在它的起点事

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

17、件可以不在最早发生 时间发生，而允许向后推迟一些时间发生， 我们把最晚必须发生的时间叫做该事件的最迟 发生时间。 同样，在不影响整个工程按时完成的前提 下，一些活动可以不在最早开始时间开始， 而允许向后推迟一些时间开始，我们把最晚 必须开始的时间叫做该活动的最迟开始时间。 AOE网中的任一个事件若在最迟发生时间仍 没有发生或任一项活动在最迟开始时间仍没 有开始，则必将影响整个工程的按时完成， 使工期拖延。 4求事件的最迟发生时间 dut()表示边上的权 5根据AOE网中每个事件的最早发生 时间和最迟发生时间计算出每个活动 的最早开始时间和最迟开始时间。 关键路径 有些活动的开始时间余量不为0，

18、表明这 些活动不在最早开始时间开始，至多向后拖 延相应的开始时间余量所规定的时间开始也 不会延误整个工程的进展。如对于活动a5， 它最早可以从整个工程开工后的第4天开始， 至多向后拖延两天，即从第6天开始。 有些活动的开始时间余量为0，表明这些 活动只能在最早开始时间开始，并且必须在 持续时间内按时完成，否则将拖延整个工期 。我们把开始时间余量为0的活动称为关键活 动，由关键活动所形成的从源点到汇点的每 一条路径称为关键路径。 关键路径实际上就是从源点到汇点具有 最长路径长度的那些路径，即最长路径。这 很容易理解，因为整个工程的工期就是按照 最长路径长度计算出来的，即等于该路径上 所有活动的持

19、续时间之和。当然一条路径上 的活动只能串行进行，若最长路径上的任一 活动不在最早开始时间开始，或不在规定的 持续时间内完成，都必然会延误整个工期， 所以每一项活动的开始时间余量为0，故它们 都是关键活动。 6求出关键路径的意义 可通过加快关键活动(即缩短它的持 续时间)来实现缩短整个工程的工期。 但并不是加快任何一个关键活动都 可以缩短整个工程的工期。只有加快那 些包括在所有关键路径上的关键活动才 能达到这个目的。 7.7 最短路径 什么是最短路径 ？ 设一个带权的图表示一个交通运输 网络,图中各顶点可以表示城市之间的 交通运输线,边上的权值可表示运输线 路中的各种不同信息.如:可以表示两城 市之间距离,表示所用时间,表示所需的 费用等等.对不同的人所关心的信息也 不同,但都希望所付出的代价是最小. 最短路径的问题常见两种: l 从某源点到其余各顶点之间的最短路径 (要求) l 每一对顶点之间的最短路径 (不要求) 7.7.1 从某源点到其余各顶点之间的最短路径 注:最短路径并不一定是经过边数最少的路径 1.迪杰斯特拉算法思路 思路:按路径由小到大的次序逐步得到由给 定源点到图的其余各顶点的最短路径.