数据结构课件第七章.pptx

《数据结构课件第七章.pptx》由会员分享，可在线阅读，更多相关《数据结构课件第七章.pptx（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 第第7 7章章 图图本章主题：本章主题：图图教学目的：教学目的：教学重点：教学重点：图的各种存储方式及其运算 教学难点：教学难点：图结构存储方式的选择，几种经典图算法的实现本章内容：本章内容：图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径第1页/共98页2基本内容：7.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第2页/共98页3图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。在线性结构中，结点之间的关系是线性

2、关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。第3页/共98页4ADTGraph数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR；VR=|v,wV 且 P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息.7.1图及其基本运算7.1.1图的抽象数据类型定义第4页/共98页57.1.

3、2 图的基本术语1.弧、弧头、弧尾、有向图若 VR,则表示从顶点v到顶点w的一条弧。称顶点w为弧头，称顶点v为弧尾。弧头:弧的终点弧尾:弧的起点弧 弧尾V 弧头w由顶点集和弧集构成的图称为有向图。ABCDE第5页/共98页62.边、无向图若 VR 必有 VR,则称（v,w）为顶点v和顶点w之间存在一条边。由顶点集和边集构成的图称为无向图。ABCDEF双向的两条弧构成一条边第6页/共98页7权权 某某些些图图的的边边或弧具具有有与与它它相相关关的的数数,称称之之为为权权。权可以代表一个顶点到另一个顶点的距离，耗费等。3.网弧或边带权的图分别称为有向网或无向网。第7页/共98页84.子图设有两个图

4、G(V,E)和G(V,E)。若V V 且E E,则称图G是图G的子图。子图：第8页/共98页95.完全图、稀疏图、稠密图假设图中有n个顶点，e条边，则 含有e=n(n-1)/2条边的无向图称作 完全图；含有e=n(n-1)条弧的有向图称作 有向完全图；除此之外：若边或弧的个数enlogn,则称作 稀疏图，否则称作 稠密图。第9页/共98页10例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n n(n n-1)/2-1)/2条边条边n n(n n-1)-1)条边条边G1的顶点集合为V(G1)=0,1,2,3边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3)

5、,(2,3)完全图完全图第10页/共98页116.邻接点、度、入度、出度u 对于无向图来说，假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，边 （v,w）和顶点v,w相关联。与顶点v相关的边或弧的数目称作顶点v的度。u 对有向图来说，从从x x到到y y有一条弧，则有一条弧，则y y邻接自邻接自x x，但但x x邻接到邻接到y y。x y x y 以顶点v为弧尾的弧的数目定义为顶点的出度；以顶点v为弧头的弧的数目定义为顶点的入度。度（TD)=出度（OD）+入度（ID)第11页/共98页127.路径、路径长度、简单路径、简单回路在图G=（V,VR)中若存在一个顶点序列Vp,Vi1，V

6、i2，Vin，Vq,，使得每相邻两个顶点一定有一条边（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)（或弧）均属于VR，则称从顶点Vp到顶点Vq之间存在一条路径，路径上边（或弧）的数目称作路径长度。若序列中的顶点不重复出现，则称作简单路径；若Vp=Vq，则称这条路径为回路。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路。第12页/共98页13第13页/共98页148 8连通图与连通分量连通图与连通分量在无向图中在无向图中,若从顶点若从顶点v v1 1到顶点到顶点v v2 2有路径有路径,则称顶点则称顶点v v1 1与与v v2 2是连通的。如果图中任意是连通的

7、。如果图中任意一对顶点一对顶点vi和vj（vi，vjV）都是连通的都是连通的,则称此图是则称此图是连通图连通图。若图为。若图为非连通图，非连通图，则图则图中各个中各个极大连通子图极大连通子图叫叫做连通分量做连通分量。在非连通图中一定存在若干个极大连通子图（连通分量)，每个子图一定是一个连通图。这几个连通分量之间是互相独立，互不相关的。DEGHIKABLMCFJABLMCFDEGHKJIV1V2V3V4V5第14页/共98页159 9强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若对于每一对顶点若对于每一对顶点v vi i和和v vj j,都存在一条从都存在一条从v vi i到

8、到v vj j和从和从v vj j到到v vi i的路径的路径,则称则称此图是此图是强连通图强连通图。非强连通图的。非强连通图的极大强连通子图极大强连通子图叫做叫做强连通分量强连通分量。v1vV3V4vv1V3V4第15页/共98页1610.生成树、生成森林 假设一个连通图有n个顶点和e条边，其中n个顶点和n-1条边构成一个极小连通子图，称该极小连通子图为此连通图的生成树。极小连通子图的特点：在n-1条边中，去掉一条边，图就不是连通图；增加一条边，必然存在回路。第16页/共98页17ABLMCFDEGHKJIABLMCFJABLMCFJ 一个连通图，可以存在若干极小连通子图或生成树。一个非连通

9、图，存在若干个连通分量，每个连通分量的生成树的集合为此非连通图的生成森林。ABLMCFJDEGHIK第17页/共98页187.1.3 7.1.3 图的基本运算图的基本运算 图的基本运算也包括查找、插入和删除。（1）顶点定位运算 确定顶点v在图中的位置；（2）取顶点运算 求取图中第i个顶点；（3）求第一个邻接点运算 求图中顶点v的第一个邻接点；（4）求下一个邻接点运算 已知w为图中顶点v的某个邻接点，求顶点w的下一个邻接点；（5）插入顶点运算 在图中增添一个顶点v作为图的第n+1个顶点，其中n为插入该顶点前图的顶点个数；（6）插入弧运算 在图中增添一条从顶点v到顶点w的弧。（7）删除顶点运算 从

10、图中删除顶点v以及所有与顶点v相关联的弧。（8）删除弧运算 从图中删除一条从顶点v到顶点w的弧。第18页/共98页197.2 7.2 图的存储结构图的特点：非线性结构（图的特点：非线性结构（m:n m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法V1V2V3V4V5V6第19页/共98页20一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法用两个数组分别表示数据元素的（顶点）的信息和（弧）的信息。设图设图 A=(A=(V V,E E)有有 n n 个顶

11、点，个顶点，则图的用于表示数据元素之间关系的邻接矩阵是一个则图的用于表示数据元素之间关系的邻接矩阵是一个二维数组二维数组 A.EdgennA.Edgenn，定义为：，定义为：例例1 1（无向图邻接矩阵）：（无向图邻接矩阵）：v1v2v3v5v4v4AA.Edge=（v1v2v3v4v5）v1v2v3v4v5000000000000000000000000001010101010101110101011100101010101010111010101110顶点表：顶点表：无权图第20页/共98页21分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：对于无向图来说

12、，：对于无向图来说，顶点顶点i i 的的度度第第 i i 行行(列列)中中11的个数的个数；特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为0 0，其余全，其余全1 1。例例1 1：v1v2v3v5v4v4AA.Edge=（v1v2v3v4v5）v1v2v3v4v5000000000000000000000000001010101010101110101011100101010101010111010101110顶点表：顶点表：第21页/共98页22例2：有向图的邻接矩阵分析分析1 1：有向图的邻接矩阵可能是不对称的。分析分析2 2：顶点的出度=第i行元素之和，OD(V

13、i)=A.Edge i j 顶点的入度=第i列元素之和。ID(Vi)=A.Edge j i 顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4A A邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01100000000110000110000000011000第22页/共98页23邻接矩阵：A.Edge=顶点表：V0 v1 v2 v3 v4 v50 0 0 0 0 0 v0 1

14、0 0 1 0 0 v10 1 0 0 0 1 v20 0 1 0 1 1 v31 0 0 0 0 0 v41 1 0 0 1 0 v5第23页/共98页24 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。特别讨论：网（即有权图）的邻接矩阵定义为：A.Edgeij=Wij或（vi,vj）VR无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：N.Edge=(v1v2v3v4v5v6)邻接矩阵法优点：邻接矩阵法缺点：顶点表：57489565315

15、748956531第24页/共98页25二、邻接表（链式）表示法二、邻接表（链式）表示法 邻接表是图的一种链式存储结构，它对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧），每个结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点，数据域（info）存储和边或弧相关的信息（如权值）。第25页/共98页26例例例例1 1：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该

16、网络。8064125当邻接表的存储结构形成后，图便唯一确定！第26页/共98页27例例例例1 1：无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表v1v2v3v5v4v4邻接表0123413341420例例2 2：有向图的邻接表有向图的邻接表邻接表(出边)V4V3V2V10230逆邻接表(入边)注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v1v2v3v42301V4V3V2V13 第27页/共98页28分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e

17、)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点：分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：需遍历全表邻接表的优点：TD(Vi)=单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数ID(Vi)邻接点为Vi的弧个数TD(Vi)=OD(Vi)+I D(Vi)空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的

18、单链表，没有邻接矩阵方便。第28页/共98页29讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2)第29页/共98页30三、三、十字链表十字链表（适用于有向图）适用于有向图）第30页/共98页31它是有向图的另一种链式结构。思路：将邻接

19、矩阵用链表存储，是邻接表、逆邻接表的结合。1、每条弧对应一个结点(称为弧结点，设5个域）2、每个顶点也对应一个结点（称为顶点结点，设3个域）tailvexheadvexHlinktlinkinfo顶点结点弧结点三、十字链表三、十字链表tailvex:弧尾顶点位置 headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息n个顶点用顺序存储结构data:存储顶点信息。Firstin:以顶点为弧头的第一条弧结点。Firstout:以顶点为弧尾的第一条弧结点。dataFirstinFirstout适用于有向图第31页/共98页320v11v22v33

20、v4v1v2v3v40 1022 023例：画出有向图的十字链表。例：画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。303132数组下标不属结点分量第32页/共98页33v1v2v3v5v4v4邻接表0123413341420v1v2v3v4v5231420邻接表(出边)V4V3V2V10230逆邻接表(入边)v1v2v3v42301V4V3V2V13 第33页/共98页340v11v22v33v4v1v2v3v40 1022 023303132数组下标不属结点分量第34页/共98页35一、深度优先搜索二、广度优先搜

21、索 7.3 图的遍历图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历，它是，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组 visitedn，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visitedi为1，防止它被多次访问。图常用的遍历：怎样避免重复访问？第35页/共98页36一、深度优先搜索一、深度

22、优先搜索一、深度优先搜索一、深度优先搜索(DFSDFSDFSDFS)基本思想：仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFSDFS结果结果例例1 1：v2v4v8v5v3v6v7例例2 2：v2v1v3v5v2v1v3v5DFSDFS结果结果v4v4v6v6起点起点遍历步骤第36页/共98页37深度优先搜索（遍历）步骤：简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。第37页/共98页38讨论讨论1 1：计算机如何实现计算机如何实现DFSDFS？1 2345610 000

23、002 20 0000030 0000040 0000050 0000060 0000000000012345601000011 100001 11 110001 11 11 10101 11 11 111 101 11 11 11 11 11DFSDFS结果结果邻接矩阵A辅助数组 visitedn起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组 visitedn！例：1 23 456101 11 11 1002 21 1 00 01 1031 1 00 01 1041 1 00 001 1501 11 1 00060 001 100第38页/共98页39讨论讨论2 2：DFSD

24、FS算法如何编程？算法如何编程？可以用递归算法！void DFSTraverse(Graph G,Status(*Visit)(int v)/算法7.4/对图G作深度优先遍历。VisitFunc=Visit;/使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0;vG.vexnum;+v)visitedv=false;/访问标志数组初始化 for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)/对v的尚未访问的邻接顶点w递归调用DFS DFS(G,w);123456780 00 00 00 00 00 00 00 01 10 00 00

25、00 00 00 00 01 11 10 00 00 00 00 00 01 11 10 01 10 00 00 00 01 11 10 01 10 00 00 01 11 11 10 01 11 10 00 01 11 11 11 11 11 10 01 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 01 1第40页/共98页41讨论讨论3 3：在图的邻接表中如何进行在图的邻接表中如何进行DFSDFS？v0v1v2v3v0v1v2v3DFSDFS结果结果00000123辅助数组 visitedn1000110011101111例：照样借用visit

26、edn！起点0123注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。第41页/共98页42DFS DFS 算法效率分析算法效率分析算法效率分析算法效率分析:（设图中有设图中有 n n 个顶点，个顶点，e e 条边条边）n如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。n如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e 个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。第42页/共98页43二、广度优

27、先搜索二、广度优先搜索二、广度优先搜索二、广度优先搜索(BFS BFS BFS BFS)基本思想：仿树的层次遍历过程。Breadth_FirstSearchv1v1v2v3v8v7v6v4v5BFSBFS结果结果例例1 1：v2v3v4v5v6v7v8例例2 2：v3v3BFSBFS结果结果v4v4 v5v5起点遍历步骤起点v2v1v6v2v1v6v9v8v7v9v8v7第43页/共98页44广度优先搜索（遍历）步骤：简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问

28、一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。第44页/共98页45讨论1：计算机如何实现BFS？邻接表除辅助数组visitedn外，还需再开一辅助队列！例：起点辅助队列v2已访问过了BFSBFS遍历结果遍历结果入队！初始f=n-1,r=0第45页/共98页46讨论2：BFS算法如何编程？层次遍历应当用队列！void BFSTraverse(Graph G,Status(*Visit)(int v)/算法7.6 /按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。for(v=0;vG.vexnum;+v)visited

29、v=FALSE;InitQueue(Q);/置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)/u的尚未访问的邻接顶点w入队列Q visitedw=TRUE;Visit(w);EnQueue(Q,w);/if /while /if /BFSTraverse第46页/共98页47v1v2v3v8v7v6v4v5123456780 00 00 00 00 00 00 00 01 10 00 00 00 00 00 00 0v1 u=v11 11 10 00 00 00 00 00 0v21 11 11 10 00 00 00 00 0v31

30、11 11 11 10 00 00 00 0u=v21 11 11 11 11 10 00 00 01 11 11 11 11 11 10 00 0v4v5u=v31 11 11 11 11 11 11 10 0u=v41 11 11 11 11 11 11 11 1v8v6v7u=v5u=v6u=v7u=v8第47页/共98页487.4图的连通性问题1.1.无向图的连通分量无向图的连通分量 图遍历时，u对于连通图，无论是广广度度优优先先搜搜索索还是深深度度优优先先搜搜索索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。u对于非连通图，则需要多次调用搜索过程，而每次调用

31、得到的顶点访问序列恰为各连通分量中的顶点集。7.4.1 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树第48页/共98页49ALMJBFC;DE;GKHI;第49页/共98页502.2.无向图的生成树无向图的生成树 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。设G=(V,E)为连通图,设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T和B,其中T是遍历图过程中走过的边的集合,B是剩余的边的集合：TB=,TB=E(G)。显然,G=(V,T)是G的极小连通子图,即G是G的一棵生成树。第50页/

32、共98页51起始点ABLMCFJ第51页/共98页52由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。对于非连通图,每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树,各个连通分量的生成树组成非连通图的生成森林。第52页/共98页53深度优先生成森林广度优先生成森林第53页/共98页547.4.3 7.4.3 7.4.3 7.4.3 求最小生成树求最小生成树求最小生成树求最小生成树目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。应用：n个城市建网，可以设置n(n-1

33、)/2条线路，如何在这些可能的线路中选择n1条线路，使总费用最少？vKruskal（克鲁斯卡尔）算法vPrim（普里姆）算法算法：归并边归并顶点第54页/共98页55最小生成树有如下重要性质(MST性质)：设N=(V,E)是一连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中uU，vV-U，则存在一棵包含边（u,v）的最小生成树。最小生成树性质：最小生成树性质：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 2第55页/共98页56用反证法来证明这个MST性质：假设不存在这样一棵包含边（u,v）的最小生成树。任取一棵最小生

34、成树T，将（u,v）加入T中。根据树的性质，此时T中必形成一个包含（u,v）的回路，且回路中必有一条边（u,v）的权值大于或等于（u,v）的权值。删除（u,v），则得到一棵代价小于等于T的生成树T，且T为一棵包含边（u,v）的最小生成树。这与假设矛盾，故该性质得证。利用MST性质来生成一个连通网的最小生成树。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法便是利用了这个性质。第56页/共98页57l普里姆算法(Prim算法,又称边割法)1957年由Prim提出假设N=(V,E)是连通网，TE为最小生成树中边的集合。Step1:初始U=u0(u0V),TE=；Step2:在所有uU,vV

35、-U的边中选一条代价最小的边(u0,v0)并入集合TE，同时将v0并入U；Step3:重复Step2，直到U=V为止。此时，TE中必含有n-1条边，则T=(V,TE)为N的最小生成树。第57页/共98页58例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1注：在最小生成树的生成过程中，所选的边都是 一端在V-U中，另一端在U中。第58页/共98页59l克鲁斯卡尔算法（避圈法）Kruskal于1956年提出假设G=(V,E)是一个具有n个顶点的带权连通无向图,令最小生成树的初始状态为只有n个顶点而无边的非连通图

36、T=（V，），图中每个顶点自成一个连通分量。则构造最小生成树的步骤如下：Step1:在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入TE；否则舍弃,而选择下一条代价最小的边；Step2:若T中有n-1条边，结束；否则转step1.从一个零图开始，克鲁斯卡尔算法逐步增加生成树的边，与普里姆算法相比，可称为“加边法”。第59页/共98页60KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6第

37、60页/共98页61我们经常用AOV网来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。7.57.5有向无环图及其应用有向无环图及其应用 用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网(ActivityOnVertexNetwork)，简称为AOV-网。第61页/共98页627.57.5有向无环图及其应用有向无环图及其应用 1.拓扑排序（TopologicalSort）简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。偏序：指集

38、合中仅有部分成员之间可比较。全序：指集合中全体成员之间均可比较。第62页/共98页63 更直观地，一个偏序可以是一个流程图，表示完成某项任务过程中各个步骤之间的次序关系，拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。排序依赖的原则就是各个步骤之间的优先关系。拓扑排序得到的序列不一定是唯一的，因为某些步骤间没有规定优先关系（这就是偏序的特点），在拓扑排序的时候人为的加入一些规则，使得到的序列为满足偏序关系的一个全序。第63页/共98页64第64页/共98页65如何进行拓扑排序？方法一：（从图中顶点的入度考虑）从有向图中选择一个没有前驱(即入度为0)的顶点并且输出

39、它。从网中删去该顶点和所有以它为尾的弧；重复上述两步,直到图全部顶点输出；或当前图中不再存在没有前驱的顶点。v1，v6，v4，v3，v2，v5或v1，v3，v2，v6，v4，v5第65页/共98页66拓扑序列：C1,C2,C3,C4,C5,C8,C9,C7,C6。拓扑序列：C1,C2,C3,C8,C4,C5,C9,C7,C6。第66页/共98页67方法二：（从图中顶点的出度考虑，得到逆拓扑序列）从有向图中选择一个出度为0的顶点并且输出它。从网中删去该顶点和所有以它为头的弧；重复上述两步,直到图全部顶点输出；或当前图中不再存在出度为0的顶点。第67页/共98页68u AOE网u 图的关键路径、事

40、件的最早、最迟发生时间、活动的最早、最迟开始时间2、关键路径第68页/共98页69一些基本概念：AOE网，即边表示活动的网络，与AOV相对应的是，它通常表示一个工程的计划或进度。AOE网是一个有向带权图，图中的：边：表示活动（子工程）。边上的权：表示该活动的持续时间，即完成该活动所需要的时间；顶点：表示事件，每个事件是活动之间的转结点，即表示它的所有入边活动到此完成，所有出边活动从此开始。第69页/共98页70一个AOE网如图，该网中包含有11项活动和9个事件。例如，边表示活动a1，持续时间（即权值）为6，假定以天为单位，即a1需要6天完成，它以v1事件为起点，以v2事件为终点；边和分别表示活

41、动a7和a8,他们的持续时间分别为9天和7天，它们均以v5事件为起点，以v7，v8事件为终点。该网中的源点和汇点分别为第1个事件v1和最后一个事件v9，它们分别表示整个工程的开始和结束。v1v6v4v3v2v5v8v7v9a1=6a2=4a3=5a4=1a5=1a7=9a10=2a6=2a9=4a8=7a11=4第70页/共98页71 其中有两个特殊的顶点（事件），一个称作源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；另一个称为汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有 入边，没有出边，除这两个顶点外，其余顶点都既有入边，也有出边，是入边活动和出边活

42、动的转接点。第71页/共98页72（1）整个工程至少需要多长时间完成？（2）哪些活动是影响工程进度的关键？能够从图中分辨出来哪些是关键活动，哪些是非关键路径。什么是关键路径？AOE网和AOV网的比较：（1）都是工程建模的工具；（2）AOV网是顶点表示活动的网，只描述了活动之间的制约关系；（3）AOE网是边表示活动的网，边上的权值表示活动的持续事件，AOE网进一步回答：如果活动之间的制约关系没有矛盾，则：第72页/共98页73完成整个工程的最短时间是从始点到终点的最大路径长度，要缩短整个工期，必须加快关键活动的进度。例如在右图中，整个工程的最短工期是最大路径长度为12，而不是最短路径长度，活动a

43、1和a3是关键活动，如果活动a1和a3不能按时完成，则会影响整个工期，而缩短活动a2和a4的时间不能缩短整个工期。v2v1v3v4a1=6a2=4a3=6a4=1第73页/共98页74AOE网具有一下两个性质：（1)只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；（2）只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。第74页/共98页75要找出关键路径，必须先出关键活动。为了在AOE网中找出关键路径，需要定义如下几个参量：（1）事件的最早发生时间vek:事件vk的最早发生时间。（2）事件的最迟发生时间vlk：在不推迟整个工期的前提下，事件vk允许的最晚发生时间。（

44、3）活动ai的最早开始时间ei：活动ai能够开工的最早时间。（4）活动ai的最晚开始时间li：在不推迟整个工期的前提下，活动ai必须开始的最晚时间。然后计算各个活动的时间余量lk-ek，时间余量为0者即为关键活动，关键活动确定之后，关键活动所在的路径是关键路径。第75页/共98页76（1）事件的最早发生时间vek从始点到顶点vk的最大路径长度决定了所有从顶点vk发出的活动能够开工的最早时间。根据AOE网的性质，只有进入vk的所有活动都结束时，vk代表的事件才能发生；而活动的最早结束时间为vej+len。所以计算vk的最早发生时间的方法如下：Ve1=0Vek=maxvej+len(pk)其中，p

45、k表示所有到达vk的有向边的集合；len为有向边上的权值。第76页/共98页77（2）事件的最迟发生时间vlk若有向边代表从vk出发的活动，为了不拖延整个工期，事件vk的最迟发生时间必须保证不推迟从事件vk出发的所有活动的终点vj的最迟时间vlj。vlk的计算方法如下：Vln=venVlk=minvlj-lensk其中，sk为所有从vk发出的有向边的集合。第77页/共98页78v1v6v4v3v2v5v8v7v9a1=6a2=4a3=5a4=1a5=1a7=9a10=2a6=2a9=4a8=7a11=4计算事件的最早发生时间是按拓扑序列的顺序，而计算事件的最迟发生时间是按逆拓扑序列的顺序。第7

46、8页/共98页79（3）活动ai的最早开始时间ei若活动ai是由弧表示，根据AOE网的性质，只有事件vk发生了，活动ai才能开始。也就是说，活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：ei=vek(4)活动ai的最晚开始时间li若活动ai由有向边表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，应该有：li=vlj-len第79页/共98页80v1v6v4v3v2v5v8v7v9a1=6a2=4a3=5a4=1a5=1a7=9a10=2a6=2a9=4a8=7a11=4最后，比较ei和li的值可判断出a1,a4,a7,a8,a10,a11是关键活动，构成两条

47、关键路径：（v1,v2,v5,v7,v9)和（v1,v2,v5,v8,v9)第80页/共98页81邻接矩阵？0v11v22v33v4v1v2v3v40 1022 023303132第81页/共98页82例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1第82页/共98页83Kruskal（克鲁斯卡尔）算法例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6第83页/共98页84一顶点到其余各顶点3

48、.3.求最短路径求最短路径两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）任意两顶点之间第84页/共98页85一、单源最短路径一、单源最短路径 (Dijkstra算法算法)目的：设一有向图G=（V,E），已知各边的

49、权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。例1：源点从FA的路径有4条：FA：24 FBA：518=23 FBCA：5+7+9=21 FDCA：25+12+9=36又：从FB的最短路径是哪条？从FC的最短路径是哪条？第85页/共98页86v0(v0,v1)10源点终点最短路径路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3)30 v1 v2 v3 v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：60012345090 70讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60第86页/共98

50、页871.1.迪杰斯特拉算法迪杰斯特拉算法u 求一个顶点到其他各顶点的最短路径。u 算法：算法：初始化：用起点v到该顶点w的直接边(弧)初始化最短 路径，否则设为；从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；修改最短路径：计算u的邻接点的最短路径，若 (v,u)+(u,w)(v,w)，则以(v,u,w)代替。重复(b)-(c)，直到求得v到其余所有顶点的最短路径。u 特点：总是按照从小到大的顺序求得最短路径。vuw第87页/共98页88顶点A到其他顶点的最短路径ABCDEF68461523328ACFDE7ACFD6ACB5ACF2AC最短路径5ACF6AFF8A