数据结构 第7章图

1、.,1,数据结构课程的内容,多对多 （m:n),.,2,哥尼斯堡七桥问题 德国古城哥尼斯堡普雷格尔河七 桥问题：从任一桥头出发，依次走过每座 桥，每座桥只走一次，最后回到出发点。 一笔画问题,.,3,.,4,.,5,7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的连通性 7.5 图的应用,第7章 图,.,6,7.1 图的基本术语,其中：V 是G 的顶点集合，是有穷非空集； E 是G 的边集合，是有穷集。,问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。,有向图： 无向图： 完全图：,图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任

2、意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图,V=vertex E=edge,图：记为 G( V, E ),有向边(u, v)称为弧，边的始点u 叫弧尾，终点v 叫弧头。,.,7,例：判断下列4种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1) 条边,G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,.,8,证明：,证明：若是完全有向图，则

3、n个顶点中的每个顶点都有一条弧指向其它n-1个顶点, 因此总边数=n(n-1),证明：从可以直接推论出无向完全图的边数因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。, 完全无向图有n(n-1)/2 条边。, 完全有向图有n(n-1)条边。,.,9,稀疏图：稠密图：,设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。,子 图：,边较少的图。通常边数远少于nlogn 边很多的图。,无向图中，边数接近n(n-1)/2 有向图中，边数接近n(n-1),.,10,带权图：,即边上带权的图。其中权是指每条边可以标上具有某种含义的数

4、值（即与边相关的数）。,连通图：,在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。,带权图,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。,强连通图：,网 ：,非强连通图的极大强连通子图叫做强连通分量。,.,11,生成树：,是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。,若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。,有两类图形不在本章讨论之列：,图的基本术语(续),如果在生成树上添加

5、1条边，必定构成一个环。 若图中有n个顶点，却少于n-1条边，必为非连通图。,生成 森林：,.,12,邻接点：,有向边(u, v)称为弧，边的始点u 叫弧尾，终点v 叫弧头。,顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。,弧头和弧尾：,入度和出度：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,度：,顶点v 的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度

6、之和。,U 的入度=? U 的出度=?,答：是树！而且是一棵有向树！,.,13,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回路：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,路径：,在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条

7、数； 带权图的路径长度是指路径上各边的权之和。,图的术语（续）,.,14,ADT Graph 数据对象V： 数据关系 R： 基本操作P： ADT Graph,图的抽象数据类型,V是具有相同特性的数据元素的集合，称为顶点集。,R=VR；VR=|v,wV 且 P(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息,CreatGraph ( 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。,注意：V 的大小写含义不同！,InsertVex ( 初始条件：图G存在，v 和图中顶点有相同特征。 操作结果：在图G中添加新顶点。,（参见教材P156-25

8、7）,.,15,7.2 图的存储结构,图的特点：,链式存储结构：,顺序存储结构：,难！,（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）,可用多重链表,邻接矩阵(数组)表示法 邻接表(链式)表示法 十字链表表示法 邻接多重表表示法,但可用数组描述元素间关系。,非线性结构（m :n）,邻接矩阵,邻接表 十字链表 邻接多重表,各种表示法成立的原则：存入电脑后能惟一复原,.,16, 建立一个顶点表和一个邻接矩阵。,1. 邻接矩阵（数组）表示法,例1：,邻接矩阵：,A.Edge =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1

9、0 1 1 1 0 1 0 1 0 1 1 1 0,分析1：无向图的邻接矩阵是对称的； 分析2：顶点i 的度第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。,顶点表：,无向图的邻接矩阵如何表示？,记录各个顶点信息,表示各个顶点之间关系, 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn，定义为：,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,.,17,例2 ：有向

10、图的邻接矩阵如何表示？,分析1：有向图的邻接矩阵可能是不对称的。 分析2：顶点vi的出度=第i行元素之和，OD(vi )= A.Edge i j 顶点vi的入度=第i列元素之和。ID(vi )= A.Edge j i 顶点的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ),邻接矩阵：,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。,顶

11、点表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,.,18,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。,例3 ： 有权图（即网络）的邻接矩阵如何表示？,定义：,以有向网为例：,邻接矩阵：, ,N.Edge =,( v1 v2 v3 v4 v5 v6 ),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v

12、5 v6,对稀疏图而言尤其浪费空间。,.,19,注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, AG, AN GraphKind; /有向/无向图，有向/无向网,图的邻接矩阵在机内如何表示？ （参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),Typedef struct ArcCell /弧（边）结点的定义 VRType adj; /顶点间关系，无权图取1或0；有权图取权值类型 InfoType *info; /该

13、弧相关信息的指针 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;,Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可(n) AdjMatrix arcs; /邻接矩阵n*n Int Vernum, arcnum; /顶点总数n，弧（边）总数e GraphKind kind; /图的种类标志 Mgraph;,.,20,Status CreateUDN(Mgraph /输入n个顶点值，存入一维向量,例：用邻接矩阵生成无向网的算法（参见教材P162）,对于n个顶点e

14、条弧的网， 建网时间效率 = O(n+n2+e*n),for(i=0; iG.vexnum; +i) /对邻接矩阵n*n个单元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL;,for(k=0;kG.arcnum;+k) /给邻接矩阵有关单元赋初值(循环次数弧数e scanf( /如果弧有信息则填入 G.arcsij = G.arcs j i； /无向网是对称矩阵 ,return OK; / CreateUDN,.,21,2. 邻接表（链式）表示法, 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或

15、出度边）链接起来，表中每个结点都设为3个域:, 每个单链表还应当附设一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi 邻接点的位置,链域，指向下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi 信息,链域，指向单链表的第一个结点, 每个单链表的头结点另外用顺序存储结构存储。,.,22,例1：无向图的邻接表如何表示？,邻接表,例2：有向图的邻接表如何表示？,邻接表(出边),逆邻接表(入边),请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。,v1邻接点v4的位置,此无权图未开第3分量,.,23,例3：已知某网的邻接（出边）表，请画出该网络。,8

16、0,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,.,24,分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？ 怎样计算有向图顶点的入度？ 怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD(Vi)=单链表中

17、链接的结点个数,OD(Vi)单链出边表中链接的结点数 I D( Vi ) 邻接点为Vi的弧个数,TD(Vi) = OD( Vi ) + I D( Vi ),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,.,25,讨论：邻接表与邻接矩阵有什么异同之处？,1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。

18、 3. 用途： 邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)； 而邻接表多用于稀疏图的存储（en2),.,26,图的邻接表在机内如何表示？ （参见教材P163）,#define MAX_VERTEX_NUM 20 /假设的最大顶点数,空间效率为O(n+2e)或O(n+e) 时间效率为O(n+e*n),Typedef struct VNode /顶点结构 VertexType data; /顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针 VNode, AdjList MAX_VERTEX_NUM ;,Typedef struct /图结构 AdjLis

19、t vertics ; /应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志） ALGraph;,Typedef struct ArcNode /弧结构 int adjvex; /该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针 ArcNode；,图的邻接表生成算法作为自测题,.,27,它是有向图的另一种链式结构。 思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。 1、开设弧结点，设5个域（每段弧是一个数据元素） 2

20、、开设顶点结点，设3个域（每个顶点也是一个数据元素）,data : 顶点信息 Firstin : 以顶点为弧头的第一条弧结点 Firstout: 以顶点为弧尾的第一条弧结点,顶点结点,弧结点,3. 十字链表表示法,tailvex: 弧尾顶点位置 headvex: 弧头顶点位置 hlink: 弧头相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,n个顶点的集合怎样储存？,仍用顺序存储结构,.,28,例：画出有向图的十字链表。,十字链表优点：容易操作，如求顶点的入度、出度等。,此无权图未开第4分量,空间复杂度和建表的时间复杂度都与邻接表相同。,.,29,#define MA

21、X_VERTEX_NUM 20,十字链表存储结构描述：,Typedef struct ArcBox /弧结点结构，5分量 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox;,Typedef struct VexNode /顶点结构, 3分量 VertexType data; ArcBox * firstin,*firstout; VexNode;,Typedef struct /图结构,整体概念 VexNode xlist MAX_VERTEX_NUM ; /表头向量 int vexnum

22、, arcnum; OLGraph;,.,30,这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。 1、设立边结点， 6个域（每条边是一个数据元素） 2、设立顶点结点， 2个域（每个顶点也是一个数据元素）,边结点,data : 存储顶点信息 Firstedge : 依附顶点的第一条边结点,顶点结点,4. 邻接多重表表示法,mark：标志域 ivex， jvex : 边依附的两个顶点位置 ilink: 指向下一条依附顶点 i 的边位置 jlink; 指向下一条依附顶点 j 的边位置 info: 边信息,n个顶点的集合怎样储存？,仍用顺序存储结构,.,31,例：画出无向图的邻接多重表,

23、邻接多重表优点： 容易操作，如求顶点的度等。,空间复杂度和建表的时间复杂度都与邻接表相同。,此无权图未开第6分量,.,32,一、深度优先搜索 二、广度优先搜索,7.3 图的遍历,遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。 图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路：可设置一个辅助数组 visited n ，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某

24、一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。,图常用的遍历：,怎样避免重复访问？,.,33,一、深度优先搜索( DFS ),基本思想：仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 结果,v4 v6,起点,起点,遍历步骤,应退回到V8，因为V2已有标记,.,34,深度优先搜索（遍历）步骤：,详细归纳： 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1； 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2； 然后

25、再从 w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,简单归纳： 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,.,35,讨论1：计算机如何实现DFS？,DFS 结果,邻接矩阵 A,辅助数组 visited n ,起点,开辅助数组 visited n

26、 ！,例：,v2,v1,v3,v5,v4,v6,请注意逐级回退是递归概念,.,36,for( j=1; j=n; j+) if ( Av, j / DFS1,讨论2： DFS算法如何编程？,DFS1(A, n, v) visit（v）; visitedv=1;,可以用递归算法！,/Ann为邻接矩阵，v为起始顶点(编号）,/访问（例如打印）顶点v,Av,j 1 有邻接点,visited n =0 未访问过,/访问后立即修改辅助数组标志,/从v所在行从头搜索邻接点,（教材上DFS递归算法见P169）,.,37,讨论3：在图的邻接表中如何进行DFS？,DFS 结果,辅助数组 visited n ,例

27、：,照样借用visited n ！,起点,0 1 2 3,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,因此遍历速度很快。,v0,v1,v2,v3,.,38,讨论4： 邻接表的DFS算法如何编程？,（书上没有，仅供参考）,/访问后立即修改辅助数组标志,仍用递归算法,Int visited; /初始化辅助数组,元素均为0 Void DFS(List,v,p) /设p为v的头指针 visit(v); /访问起点 visitedv=1; /起点已访问,0变1 while(p-link) /当存在起点的第一个邻接点时 p=p-link; v=p-data; if(!visitedv)DFS(

28、List,v,p); /进行递归 return; ,.,39,DFS 算法效率分析:,（设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结 论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。,.,40,二、广度优先搜索( BFS ),基本思想：仿树的层次遍历过程。,Breadth_First Search,v1,BFS 结果

29、,例1：,例2：,v3 ,BFS 结果,v4 v5 ,起点,遍历步骤,起点,v2 v1 v6 ,v9 v8 v7,.,41,广度优先搜索（遍历）步骤：,简单归纳： 在访问了起始点v之后，依次访问 v的邻接点； 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点； 直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。 因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,.,42,讨论1：计算机如何实现BFS？,邻接表,宽度优先搜索要借助队列！,例：,起点,辅助队列,v2已访问过了,V2入队,visited

30、 n 仍需要,BFS 遍历结果,.,43,while(rear!=front) /队不空时 front=(front+1)%n; v=qfront; /访问过的顶点出队 p=Listv.firstarc; /P指向第1个邻接点 while(!p) if(! Visitedadjvex(p) )/未到表尾，且邻接域未访问过， Visit(adjvex(p); Visitedadjvex(p)=1;/则先输出再改标记， rear=(rear+1)%n; qrear= adjvex(p) /最后再入队 p=nextarc(p); /指向单链表中下一个邻接点 return / BFS1,讨论2： BF

31、S算法如何编程？,BFS1(List, n, v) /List为邻接表，v为起点，Qn为辅助队列 Visit(v); Visitedv=1; /访问（例如打印）顶点v并修改标志,层次遍历应当用队列！,（教材上BFS算法见P170）,front=n-1;rear=0; /队列指针初始化 qrear=v; /起始点入队,.,44,BFS 算法效率分析:,DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用堆栈或队列装n个顶点）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0 + d1 + + dn-1 = O(e

32、)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,.,45,7.4 图的连通性问题,1. 求图的生成树 2. 求最小生成树,.,46,1.求图的生成树（或生成森林）,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：若对连通图进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的生成树！ 由深度优先搜索得到的生成树，称为深度优先搜索生成树。 由广

33、度优先搜索得到的生成树，称为广度优先搜索生成树。 思考2：若对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的生成森林！,.,47,例1 ：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,.,48,其实由邻接矩阵或邻接表也能直接画出生成森林,例2：画出下图的生成森林（或极小连通子图）,求解步骤： Step1:先求出邻接矩阵或邻接表； Step2:写出DFS或BFS结果序列； Step3:画出对应子图或生成森林。,这是一个无向非连通图（参见教材P170-171例）,下面选用邻接表方式来求深度优先搜索生成森林,生成森林的定

34、义（对有向或无向图均适用）：是若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。,.,49,子图1：,再写出DFS结果ABMJLCF DE GHKI,先写出邻接表（或邻接矩阵）：,子图2：,子图3：,最小连通！,怎样找3个根？,.,50,子图 (或连通分量),生成森林,.,51,2. 求最小生成树,首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树肯定有 n 个顶点和仅仅n-1 条边。,即有权图,构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边

35、来联结网络中的n个顶点； 不能使用产生回路的边。,目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,.,52,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有 n(n-1)/2 条线路，那么，如何选择n1条线路使总费用最少？,典型用途：,先建立数学模型： 顶点表示城市，有n个； 边表示线路，有n1条； 边的权值表示线路的经济代价； 连通网表示n个城市间的通信网。,显然此连通网是一棵生成树！,问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST。,Minimu

36、m cost Spanning Tree,.,53,讨论：如何求得最小生成树？,最小生成树（MST）的 性质如下：,若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在最小生成树上。,设想一下：先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到的很可能就是最小生成树！,求MST有多种算法，但最常用的是以下两种：,Kruskal（克鲁斯卡尔）算法 Prim（普里姆）算法,Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。,54,Kruskal算法示例：对边操作

37、，归并边,Kruskal算法效率分析：,Kruskal算法的时间效率O（elog2e）,Kruskal算法是归并边，适用于稀疏图（用邻接表）,.,55,普利姆（Prim）算法示例： 归并顶点,1,Prim算法效率分析：,Prim算法的时间效率O（n2）,Prim算法是归并顶点，适用于稠密网。,.,56,图5-4-5 构造最小生成树过程中辅助数组中各分量的值,图5-4-5 构造最小生成树过程中辅助数组中各分量的值,.,57,7.5 有向无环图及其应用,1. 拓扑排序 2. 求关键路径,.,58,1 拓扑排序 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系

38、，即必须在一子项目完成后，才能开始实施另一个子项目； 子项目之间无次序要求，即两个子项目可以同时进行，互不影响。 在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。 学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。,.,59,这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。 如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。

39、例如表5-6-1是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图5-6-1所示。,.,60,表5-6-1 某专业课程设置,.,61,图5-6-1（a） AOV网络,.,62,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。 AOV网络中一定不能有有向环路。例如在图5-6-1（b）那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。 因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才

40、有实际意义。,.,63,图5-6-1（b） 有向环路,.,64,所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。 由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。 通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。,.,65,拓扑排序方法,(1) 在AOV网中选择一个没有前驱（即入度为0）的顶点，并把它输出； (2) 从网络中删去该顶点和从该顶点发出的所有有向边； (3) 重

41、复执行上述两步，直到网中所有的顶点都被输出 (此时，原AOV网络中的所有顶点和边就都被删除掉了)。 如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。,.,66,C1,C10,C11,C6,C2,C12,C4,C8,C3,C7,C5,C9,拓扑有序序列： （C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8） （C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）,.,67,0,1,0,1,0,2,1,1,.,68,图5-6-2 AOV网及拓扑序列的产生过程,a b c d e f,

42、（a）AOV网；(b)输出v0后；（c）输出v5后；（d）输出v3后；（e）输出v2后；（f）输出v1后。 这样得到的一个拓扑排序序列为：v0, v5, v3, v2, v1, v4,.,69,为了实现拓扑排序，针对上述两个步骤，采用邻接表作为有向图的存储结构，并且在表结点中增设一个入度，存放顶点的入度。例如图5-6-2种的AOV网的邻接表如图5-6-3（a）所示。这样，入度域为零的表结点及时无前驱的顶点，删除该顶点及它为尾的弧的操作，则可以转换为将它的所有弧头顶点的入度减1来实现,.,70,.,71,A,B,C,D,E,F,G,H,I,.,72,两个事件之间只能画一条箭线，表示一项作业。若两

43、项或两项以上作业同时开始或结束，就要引进虚事件和虚作业，虚作业不消耗资源。,.,73,3各项作业之间的关系及它们在网络图上的表达方式如下： 作业a结束后可以开始b和c，见图(a)； 作业c在a和b均结束后才能开始，见图(b)；,.,74,a、b两项作业均结束后可以开始c和d，见图(c)； 作业c在a结束后即可进行，但作业d必须同时在a和b结束后才能开始，见图(d)。,.,75,表71,.,76,C,B,E,D,A,X2,X1,K,G,I,H,0,F,J,0,.,77,2.关键路径,关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。 AOE网络是一个带权的有

44、向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。 离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。 权值表示活动持续的时间。,.,78,图5-6-4 一个AOE网络,.,79,AOE网络,通常利用AOE网络可以研究以下两个问题： (1) 完成整个工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键？,.,80,关键路径,完成工程所需的时间就是从开始点起进行到结束点止所需的时间。 路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。 完成整个工程所需的时间取决于从开始点到结束点的最长路径长

45、度，此长度最大的路径叫做关键路径。 分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。,.,81,在描述关键路径的算法时，设活动ai由弧表示，要确定如下几个相关的量： (1) 事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成Vej。顶点Vj的最早出现时间Vej决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以ei表示活动ai的最早开始时间。显然ei= Vej 。 (2) 活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开

46、始时间，表示成Li。 只要某活动ai有Li=ei的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。,.,82,(3) 事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为VLj。对某条指向顶点Vj的边所代表的活动ai可得到： Li= VLj-(活动ai所需时间) 也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。 下图所示为活动开始时

47、间与事件出现时间的关系。,确定关键路径的方法就是要确定ei=Li的关键活动！,.,83,假设以wj,k表示有向边的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间ei和活动ai的最迟开始时间Li，先要求得顶点Vk的事件Vk的最早出现时间Vek和最迟出现时间VLk 。,.,84,事件最早出现时间Ve（j）和最迟出现时间Vl（j）,Vek和VLk可以采用下面的递推公式计算： (1) 向汇点递推 由源点的Vv1=0开始，利用公式： 向汇点的方向递推，可逐个求出各顶点的ev 。式中p表示所有指向顶点的边的集合，如图6.22所示。,.,85,图7-6-6 集合p,此式的意义为：从

48、指向顶点Vk的各边的活动中取最晚完成的一个活动的完成时间作为Vk的最早出现时间Vek。,.,86,(2) 向源点递推 由上一步的递推，最后总可求出汇点的最早出现时间evn。因汇点就是结束点，最迟出现时间与最早出现时间相同，即Lvn=evn。从汇点的最迟出现时间Lvn开始，利用下面公式： 向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表示所有由Vj点指出的边的集合，如图6.23所示。,.,87,图5-6-7 集合s,此公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。,.,88,无论是向汇点递推还是向源点递推，都必须按一定的顶点

49、顺序进行。 对所有的有向边，向汇点递推是先求出尾顶点的ev值，再求头顶点的ev值；向源点递推则相反，先求头顶点的Lv值，再求尾顶点的Lv值。 为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。,.,89,7.5.2 关键路径算法,(1) 输入e条有向边，建立AOE网络的存储结构； (2) 从源点出发，令ev1 =0，按拓扑排序的序列求其余各顶点的最早出现时间evi(2in)。若拓扑排序序列中的顶点个数小于网络中的顶点数n，则说明网络中存在环路，算法中止执行；否则执行(3)； (3) 从汇点Vn出发，令Lvn=evn，按逆拓扑排序的序

50、列求其余各顶点的最迟出现时间 Lvi(n-1i1)； (4) 根据各顶点的ev和Lv值求每条有向边ai的最早开始时间ei和最迟开始时间Li。若某有向边ai满足ei=Li,则为关键活动,.,90,AOE网：带权的有向图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。 关键路径：AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的长度是指路径上各个活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径。 最早发生时间：假设开始点是V1，从V1到Vi的最长的路径的长度叫做事件Vi的最早发生时间。 最迟开始时间：不推迟整个工程

51、完成的前提下，活动ai最迟 必须开始进行的时间。 关键活动：l（i）=e（i）的活动。,回顾基本概念并练习：,.,91,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,如何求关键路径？,如图所示：,关键： 求出各个事件最早出现时间ve（j）和最迟发生时 间vl（j）。 再判断各活动e（i）是否等于l（i）！,.,92,1 求事件最早出现时间,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6

52、,a2=4,a5=1,a7=9,0,6,4,5,7,14,18,7,16,从ve（0）=0开始向后推. Ve（j）=Maxve（i）+dut（i,j） (j=1，2.n-1),.,93,1 求事件最迟出现时间,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,0,6,6,8,10,14,18,7,16,从vl(9）=18开始向回推（倒计时）。 Ve（i）=Minvl（j）- dut（i,j） (j=n-2,n-3,-,0),.,94,.,95,由表可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。 这些关键活动构成两条关键路径，即