数据结构演示稿

数据结构演示稿第1页，课件共52页，创作于2023年2月

第7章图

内容7.1图的概念7.2图的存贮结构7.3图的遍历7.4图的最小生成树7.5拓扑排序7.6关键路径7.7最短路径第2页，课件共52页，创作于2023年2月7.1图的概念7.1.1图的定义每个结点有任意多个前驱和后继结点.图也可以二元组表示:

定义Graph=(v,E)v:表示元素集合E:元素之间的关系

现举两个例子，如下图：[例一][例二]

无向图中（1，2）和（2，1）代表同一边

有向图中<1,2>和<2,1>表示两个不同的方向边

以<1,2>为例，在<1,2>中：

1称为此边的起点或尾（弧尾）

2称为此边的终点或头（弧头）

边的方向规定为弧尾——〉弧头第3页，课件共52页，创作于2023年2月V(G1)={1,2,3,4}顶点集合;

E(G1)={<1,2>,<1,3>,<3,4>,<4,1>}边的集合（顶点关系）V(G2)={1,2,3,4,5}顶点集合;

E(G2)={(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}边的集合

第4页，课件共52页，创作于2023年2月7.1.2图的基本术语1、完全图：在一个有N个顶点的图中，若每个顶点到其它（N-1）顶点都有一条边，则图中有N个顶点且有（N*（N-1）/2）条边的图称为完全图。

2、邻接点：对无向图G=（V，E），若有（V1，V2）属于E则称V1和V2互为邻接点。

3、相关边：两个相邻接的点连成的边叫做这两个结点的相关边。第5页，课件共52页，创作于2023年2月4、度：与每个顶点相连的边的数叫该点的度。5、入度：对有向图中某结点的弧头数（边的终点）称为该结点的入度。6、出度：对有向图中某结点的弧尾数（边的终点）称为该结点的出度。7、路径：在一图中若从某个顶点VP出发，沿着一些边经过顶点V1，V2，…,VM到达VG则称顶点

8、回路：从一顶点出发又回到该顶点，则所经过的路径称为回路。

第6页，课件共52页，创作于2023年2月9、子图

若G和G'是两个图，且存在着V(G')≤V(G)和E（G’）≤E（G）的关系，则称G’是G的子图10、有关连通的概念连通：在无向图中，若从顶点VI到顶点VJ之间有路径则称此二顶点是连通的。连通图：如果图中任意一对顶点之间都是连通的，则称此图为连通图。强连通：对于有向图，若从顶点VI到顶点VJ到顶点VI之间都有路径，则称这两点是强连通的。强连通图：图中任何一对顶点都是强连通的，则此图叫强连通图。第7页，课件共52页，创作于2023年2月连通分量：非连通图中的每一个连通部分叫连通分量。强连通分量：有向图中极大强连通子图称为有向图的强连通分量。11、生成树一个连通的生成树，它含有图中全部顶点，但只有足以构成树的N-1条边（N顶点个数）如图P159第8页，课件共52页，创作于2023年2月12.权、网权：有些图对应每条边有一相应的数值。这个数值叫该边的权。网：这种带权的图叫网。注：不同网络的权有不同的意义：电网络权可以是阻抗，运输网络中的权可以是路程长度，运费等。

第9页，课件共52页，创作于2023年2月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,则函数值为零.……P156第10页，课件共52页，创作于2023年2月7.2图的存贮结构7.2.1邻接矩阵表示法(数组表示法)邻接矩阵表示法--表示各顶点之间的邻接关系可以借助二维数组作为存贮结构,故又称为数组表示法.

第11页，课件共52页，创作于2023年2月7.2.2邻接表邻接表是由邻接矩阵改造而来的一种链接结构,它只考虑非零元素,因而节省了零元素所占的存贮空间.

逆邻接表

链表中每个结点表示邻接矩阵中该顶点的列中每个非零元素

第12页，课件共52页，创作于2023年2月图的存贮结构说明邻接矩阵是一个n*n的方阵n为图的顶点数

矩阵每一行分别对应图的各个顶点

矩阵的每一列分别对应图的各个顶点1规定矩阵元素aij=0第13页，课件共52页，创作于2023年2月几点说明:

1.如果图的各边是带权的,也可以用邻接矩阵来表示,只需将矩阵中1元素换成相应边的权值.

2.邻接矩阵表示法对于以图的顶点为主的运算比较适用.

3.除完全图外,其他图的邻接矩阵有许多零元素,特别是当n值较大,而边数又少是,则此矩阵称为"稀疏矩阵".浪费存储空间.

第14页，课件共52页，创作于2023年2月邻接表与邻接矩阵的关系:1.与邻接矩阵的每一行有一个线形链接表.

2.链接表的表头对应着邻接矩阵该行的顶点.

3.链接表中的每个结点对应着邻接矩阵正中该行的一个非零元素

无向图:一个非零元素表示与该行顶点相邻接的另一个顶点

有向图:非零元素则表示该行顶点为起点的一条边的终点第15页，课件共52页，创作于2023年2月几点说明:1.在邻接表中的每个线性链接表中各结点的的顺序是任意的.

2.邻接表中的各个线性链接表不说明它们顶点之间的邻接关系.

3.对于无向图:

某顶点的度数=该顶点对应的线性链表的结点数

对于有向图:

某顶点的"出度"数=该顶点对应的线性链表的结点数

第16页，课件共52页，创作于2023年2月逆邻接表链表中每个结点表示邻接矩阵中该顶点的列中每个非零元素

第17页，课件共52页，创作于2023年2月7.3图的遍历什么叫图的遍历

从图的任意点出发沿着一些边访问图中的所有顶点,且使每个顶点仅被访问一次,这就叫图的遍历.

第18页，课件共52页，创作于2023年2月图的遍历的两种方法

深度优先搜索dfs

广度优先搜索bfs

第19页，课件共52页，创作于2023年2月1.深度优先搜索dfs

方法:

从图中指定的起点v0出发(先访问v)访问它的任意相邻接的顶点w1,再访问w1的任一个未访问的相邻接顶点w2,如此下去,直到某顶点已无被访问过的顶点,则返回一步找前一个顶点的其他沿未被访问的邻接顶点,重复以上过程直到所有的顶点都被访问

第20页，课件共52页，创作于2023年2月例：顶点的访问序列：V1V2V4V8V5V3V6V7第21页，课件共52页，创作于2023年2月2.广度优先搜索bfs

方法:

从图指定的起点v0出发,访问与它相邻的所有顶点w1,w2,.....然后再依次访问w1,w2......邻接的尚未被访问的所有顶点,再从这些顶点出发访问与它们相邻接的尚未被访问的顶点,直到所有顶点均被访问过为止.

第22页，课件共52页，创作于2023年2月例：顶点的访问序列：V1V2V3V4V5V6V7V8第23页，课件共52页，创作于2023年2月7.4图的最小生成树

7.4.1无向图的连通分量和生成树

1.连通分量

非连通图的每一个连通部分叫连通分量.

第24页，课件共52页，创作于2023年2月P159G3图7.3(a)邻接表第25页，课件共52页，创作于2023年2月说明：该图中包括三个连通分量，若按dfs分别从三个顶点（I，D，B）出发可得到三个连通分量的顶点序列：

I，G，K，H

D，E

B，M，L，J，A，F，C

第26页，课件共52页，创作于2023年2月2.图的生成树

图中全部顶点和搜索过程所经过的边,构成该连通图的生成树.

例如上图搜索遍历后得到的三棵树

第27页，课件共52页，创作于2023年2月

由此可以总结生成树的特点:

任意两个顶点之间有且仅有一条路径如再增加一条边,就会出现一条回路,如果去掉一条边此子图就会变成非连通图.

第28页，课件共52页，创作于2023年2月7.4.2最小生成树

1什么叫最小生成树

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.

2.求最小生成树的算法

克鲁斯卡尔算法普里姆算法第29页，课件共52页，创作于2023年2月例：第30页，课件共52页，创作于2023年2月克鲁斯卡尔算法方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)

分析：该方法对于边相对比较多的不是很实用,浪费时间.

第31页，课件共52页，创作于2023年2月普里姆算法

方法:从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树.第32页，课件共52页，创作于2023年2月7.5有向无环图及其应用

有向无环图:是一个无环的有向图.简称DAG图.

有向无环图的作用:常用来描述一个工程或一个系统的进行的过程.第33页，课件共52页，创作于2023年2月7.5.1AOV网

有向无环图可以描述一个过程或一个系统.那么在一个过程或一个系统中又可以映射多个子过程或子系统.比如我们熟悉的教学计划,一个教学计划中又可以包含许多课程(子计划),当这些子计划都完成后,整个教学计划方算完成.我们可以把每个子计划称为活动.

第34页，课件共52页，创作于2023年2月说明：在各个活动之间,有些必须按规定的先后次序进行,有些则没有次序要求.

把这种活动之间的次序要求,可用一个有向图来表示.

图中每个顶点代表一个活动.如果从顶点vi到顶点vj之间存在有向边<vi,vj>则表示活动i必须先于活动j进行.这种图中用顶点表示活动的网络称为AOV网.

AOV网的特点:在网中一定不能有有向回路.

检测网中是否存在环,可用拓扑排序的方法.第35页，课件共52页，创作于2023年2月7.5.2拓扑排序

1.什么叫拓扑排序

将AOV网中各个顶点排列成一个有序序列,使得所有前驱和后继关系都能得到满足,而那些没有次序的顶点,在拓扑排序的序列中可以插到任意位置.也可说拓扑排序是对非线形结构的有向图进行线形化的重要手段.第36页，课件共52页，创作于2023年2月2.拓扑排序的方法

由AOV网选取某个没有前驱的顶点,排到序列中,凡取出某顶点,即将它与它相关联的边从图中删掉,随着边的删除,又会有无前驱的顶点,重复如此进行,直到全部顶点都排到序列中去.例：如图P181图7.27第37页，课件共52页，创作于2023年2月7.6关键路径

AOE网(ActivityOnEdgenetwork)，即边表示活动的网络，与AOV网相对应的是。它通常表示一个工程的计划或进度。AOE网是一个有向带权图，图中的：

边：表示活动(子工程)，

边上的权：表示该活动的持续时间，即完成该活动所需要的时间；

顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。第38页，课件共52页，创作于2023年2月

其中有两个特殊的顶点(事件)，一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余顶点都既有入边，也有出边，是入边活动和出边活动的转接点。第39页，课件共52页，创作于2023年2月

在一个AOE网中，若包含有n个事件，通常令源点为第0个事件，汇点为第n-1个事件，其余事件的编号(即顶点序号)分别为1~n-2。

一个AOE网如图，该网中包含有活动和事件。如图P183图7.29一个AOV网11项9个第40页，课件共52页，创作于2023年2月

对于一个AOE网，待研究的问题是：

(1)整个工程至少需要多长时间完成?

(2)哪些活动是影响工程进度的关键?

第41页，课件共52页，创作于2023年2月1．事件的最早发生时间与活动的最早开始时间的关系

在AOE网中，一个顶点事件的发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后，即只要有一个入边活动没有完成，该事件就不可能发生。所以：

一个事件的最早发生时间是它的所有入边活动，或者说最后一个入边活动刚完成的时间。

一个活动的开始必须在它的起点事件发生之后，也就是说，一个顶点事件没有发生时，它的所有出边活动(或称后继活动)都不可能开始，所以：

一个活动的最早开始时间是它的起点事件的最早发生时间。若用ve[j]表示顶点vj事件的最早发生时间，用e[i]表示vj一条出边活动ai的最早开始时间，则有e[i]=ve[j]。

第42页，课件共52页，创作于2023年2月2．求事件的最早发生时间

对于源点事件来说，因为它没有入边，所以随时都可以发生，整个工程的开始时间就是它的发生时间，亦即最早发生时间，通常把此时间定义为0，从此开始推出其他事件的最早发生时间。

例：分析图7.29

第43页，课件共52页，创作于2023年2月3．事件的最迟发生时间与活动的最迟开始时间的关系

事件的最迟发生时间：在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而允许向后推迟一些时间发生，我们把最晚必须发生的时间叫做该事件的最迟发生时间。

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

第44页，课件共52页，创作于2023年2月4．求事件的最迟发生时间

dut(<j，k>)表示边<j，k>上的权

5．根据AOE网中每个事件的最早发生时间和最迟发生时间计算出每个活动的最早开始时间和最迟开始时间。

第45页，课件共52页，创作于2023年2月关键路径有些活动的开始时间余量不为0，表明这些活动不在最早开始时间开始，至多向后拖延相应的开始时间余量所规定的时间开始也不会延误整个工程的进展。如对于活动a5，它最早可以从整个工程开工后的第4天开始，至多向后拖延两天，即从第6天开始。

有些活动的开始时间余量为0，表明这些活动只能在最早开始时间开始，并且必须在持续时间内按时完成，否则将拖延整个工期。我们把开始时间余量为0的活动称为关键活动，由关键活动所形成的从源点到汇点的每一条路径称为关键路径。

第46页，课件共52页，创作于2023年2月

关键路径实际上就是从源点到汇点具有最长路径长度的那些路径，即最长路径。这很容易理解，因为整个工程的工期就是按照最长路径长度计算出来的，即等于