数据结构---图.ppt

上传人:本田雅阁 文档编号:3185479 上传时间:2019-07-22 格式:PPT 页数:132 大小:1.68MB
返回 下载 相关 举报
数据结构---图.ppt_第1页
第1页 / 共132页
数据结构---图.ppt_第2页
第2页 / 共132页
数据结构---图.ppt_第3页
第3页 / 共132页
数据结构---图.ppt_第4页
第4页 / 共132页
数据结构---图.ppt_第5页
第5页 / 共132页
点击查看更多>>
资源描述

《数据结构---图.ppt》由会员分享,可在线阅读,更多相关《数据结构---图.ppt(132页珍藏版)》请在三一文库上搜索。

1、数据结构-图,齐 恒 大黑楼 B0912,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林的表示方法,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,6.1 树的类型定义,现实生活中的树结构: 单位的组织结构 书籍的目录 家族族谱 广义表 ,数据对象 D:,D是具有相同特性的数据元素的集合。,若D为空集,则称为空树 ;否则: (1) 在D中存在唯一的称为根的数据元素root; (2) 当n1时,其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm,其中每一 个子集本身又是一棵符合本定义

2、的树, 称为根root的子树。,数据关系 R:,=递归定义,基本操作:,查 找 类,插 入 类,删 除 类,6.2 二叉树的类型定义,二叉树:或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的主要基本操作:,查 找 类,插 入 类,删 除 类,两类特殊的二叉树:,满二叉树:指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树:树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,

3、g,h,i,j,6.3 二叉树的存储结构,二、链式存储表示,一、 顺序存储表示,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4* 线索链表,6.4 二叉树的遍历,先(根)序遍历-波兰式,中(根)序遍历-中缀表示,后(根)序遍历-逆波兰式,二、遍历算法 对“二叉树”而言,可以有四种搜索路径:,层序遍历,6.5 线索二叉树,何谓线索二叉树? 线索链表的遍历算法 如何建立线索链表?,指向该线性序列中的“前驱”和“后继” 的指针,称作“线索”,与其相应的二叉树,称作 “线索二叉树”,包含 “线索” 的存储结构,称作 “线索链表”,A B C D E F G H K, D ,C ,

4、 B,E ,6.6 树和森林 的表示方法,树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟) 存储表示法,6.7 树和森林的遍历,一、树的遍历,二、森林的遍历,三、树的遍历的应用,6.8 哈 夫 曼 树 与 哈 夫 曼 编 码,最优二叉树 如何构造最优二叉树 前缀编码,树的带权路径长度定义为: 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。,带权路径长度最小的二叉树称为最优二叉树,简称为最优树或哈夫曼树。,7.1 抽象数据类型图的定义,7.2 图的存储表示,7.3 图的遍历,7.4 最小生成树,7.5 重(双)连通图和关节

5、点,7.6 两点之间的最短路径问题,7.7 拓扑排序,7.8 关键路径,7.1 抽象数据类型图的定义,图是由一个顶点集 V 和一个弧集 VR构成的数据结构。 Graph = (V , VR ) 其中,VR | v,wV 且 P(v,w) 表示从 v 到 w 的一条弧,并称 v 为弧尾,w 为弧头。 谓词 P(v,w) 定义了弧 的意义或信息。,图的结构定义:,由于“弧”是有方向的,因此称由顶点集和弧集构成的图为有向图。,A B E C D,例如:,G1 = (V1, VR1),其中 V1=A, B, C, D, E VR1=, , , , , , ,若VR 必有VR, 则称 (v,w) 为顶点

6、v 和顶点 w 之间存在一条边。,B C A D F E,例如: G2=(V2,VR2) V2=A, B, C, D, E, F VR2=, , , , , , ,由顶点集和边集构成的图称作无向图。,名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、 强连通图、强连通分量,生成树、生成森林,A,B,E,C,F,A,E,F,B,B,C,设图G=(V,VR) 和图 G=(V,VR), 且 VV, VRVR, 则称 G 为 G 的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,假设图中有 n

7、个顶点,e 条边,则,含有 e=n(n-1)/2 条边的无向图称作完全图;,含有 e=n(n-1) 条弧的有向图称作 有向完全图;,若图中边或弧的个数 enlogn,则称作稀疏图,否则称作稠密图。,假若顶点v 和顶点w 之间存在一条边, 则称顶点v 和w 互为邻接点,边(v,w) 和顶点v 和w 相关联。,A,C,D,F,E,例如:,ID(B) = 3,ID(A) = 2,B,和顶点v 关联的边的数目定义为顶点的度。,顶点的出度(OD):以顶点v为弧尾的弧数,A,B,E,C,F,对有向图来说,,顶点的入度(ID):以顶点v为弧头的弧数,顶点的度(TD)= 出度(OD)+入度(ID),例如:,I

8、D(B) = 2,OD(B) = 1,TD(B) = 3,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中,(vi,j-1,vi,j)VR 1jm, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。,A,B,E,C,F,如:长度为3的路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,若无向图G中任意两个顶点之间都有路径相通,则称此图为连通图.,若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,B,A,C,D,F,E,A,B,E,C,F,

9、A,B,E,C,F,对有向图,,否则,其各个强连通子图称作它的强连通分量。,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。,假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。,对非连通图,称由各个连通分量的生成树构成的集合为此非连通图的生成森林。,B,A,C,D,F,E,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基 本 操 作,CreatGraph(&G, V, VR): / 按定义(V, VR) 构造图,DestroyGraph(&G): / 销毁图

10、,结构的建立和销毁,对顶点的访问操作,LocateVex(G, u); / 若G中存在顶点u,则返回该顶点在 / 图中“位置” ;否则返回其它信息。,GetVex(G, v); / 返回 v 的值。,PutVex( / 对 v 赋值value。,对邻接点的操作,FirstAdjVex(G, v); / 返回 v 的“第一个邻接点” 。若该顶点 /在 G 中没有邻接点,则返回“空”。,NextAdjVex(G, v, w); / 返回 v 的(相对于 w 的) “下一个邻接 / 点”。若 w 是 v 的最后一个邻接点,则 / 返回“空”。,插入或删除顶点,InsertVex( /在图G中增添新顶

11、点v。,DeleteVex( / 删除G中顶点v及其相关的弧。,插入和删除弧,InsertArc( / 在G中增添弧/边,若G是无向的, /则还增添对称边。,DeleteArc( /在G中删除弧/边,若G是无向的, /则还删除对称边。,遍 历,DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G,并对每 /个顶点调用函数Visit一次且仅一次。,BFSTraverse(G, v, Visit(); /从顶点v起广度优先遍历图G,并对每 /个顶点调用函数Visit一次且仅一次。,7.2 图的存储表示,一、图的数组(邻接矩阵)存储表示 二、图的(逆)邻接表存储表示 三

12、、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示,Aij=,0 (i,j)VR,1 (i,j)VR,一、图的数组(邻接矩阵)存储表示,B,A,C,D,F,E,定义:矩阵的元素为,有向图的邻接矩阵一般为非对称矩阵,A,B,E,C,D,无向图的邻接矩阵一定是对称矩阵,typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图,用1或0表示相邻否; / 对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX

13、_NUM;,typedef struct / 图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数,弧数 GraphKind kind; / 图的种类标志 MGraph;,二、图的邻接表 存储表示,在有向图的邻接表中,对每个顶点,链接的是该顶点引出的弧。,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,有向图的邻接表,可见,在有向图的邻接表中不易找到指向该顶点的弧。,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0

14、,0 1 2 3 4,在有向图的逆邻接表中,对每个顶点,链接的是指向该顶点的弧。,typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附于该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,adjv

15、ex nextarc info,弧的结点结构,typedef struct AdjList vertices; / 顶点数组 int vexnum, arcnum, kind; / 图的结点数、弧数及图类别标志 ALGraph;,图的结构定义,三、有向图的十字链表存储表示,弧的结构表示,弧尾顶点位置 弧头顶点位置 弧的相关信息,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; infoType *info; struct ArcBox *hlink, *tlink; VexNode;

16、,顶点的结构表示,顶点信息数据,指向该顶点的第一条入弧,指向该顶点的第一条出弧,typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;,typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),四、无向图的邻接多重表存储表示,typedef struct Ebox / VisitIf mark; / 访问标记

17、,用于遍历 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; /指向下一条依附于ivex/ jvex的边 InfoType *info; / 该边信息指针 EBox;,边的结构表示,typedef struct VexBox / VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;,typedef struct / 邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;,顶点的结构表示,无

18、向图的结构表示,7.3 图的遍历,从图中某个顶点出发游历图,访遍 图中其余顶点,并且使图中的每个顶点 仅被访问一次的过程。,深度优先搜索,广度优先搜索,遍历应用举例,从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历,V,w1,SG1,SG2,SG3,W1、W2和W3 均为 V 的邻接点,SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V, for (W1、W2、W3 ) 若该邻接点W未被访问, 则从它出发进行深度优先搜索

19、遍历。,w2,w3,w2,从上页的图解可见:,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;,解决的办法是:为每个顶点设立一个 “访问标志 visitedw”。,2. 如何判别V的邻接点是否被访问?,void DFS(Graph G, int v) / 从顶点v出发,深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for (w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS,首先将图中每

20、个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点,如果未被访问,则以该顶点为起始点,进行深度优先搜索遍历,否则继续检查下一顶点。,非连通图的深度优先搜索遍历,void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS ,a,b,c,h,d,

21、e,i,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,i,f,e,b,g,a,c,h,i,f,e,d,b,g,访问标志:,访问次序:,例如:,a b c d e f g h i,二、广度优先搜索遍历图,V,w1,w8,w3,w7,w6,w2,w5,w4,对连通图,从起始点V到其余各顶点必定存在路径。,其中,V-w1, V-w2, V-w8 的路径长度为1;,V-w7, V-w3, V-w5 的路径长度为2;,V-w6, V-w4 的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,从图中的某个顶点V0出发,并在访问此顶点之后依

22、次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。,=需要利用队列,void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visited

23、v) / v 尚未访问 / BFSTraverse, ,visitedv = TRUE; Visit(v); / 访问v EnQueue(Q, v); / v入队列 while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for (w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while,三、遍历应用举例,1. 求从顶点 i 到顶点 s 的一条 简单路径

24、,2. 求两个顶点之间的一条长度 最短的路径,1. 求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,求从顶点 b 到顶点 k 的一条简单路径。,从顶点 b 出发进行深度优先搜索遍历。,例如:,假设找到的第一个邻接点是a,则得到的结点访问序列为: b a d h c e k f g。,假设找到的第一个邻接点是c,则得到的结点访问序列为: b c h d a e k f g,,1. 从顶点 i 到顶点 s ,若存在路径,则从顶点 i 出发进行深度优先搜索,必能搜索到顶点 s 。,2. 遍历过程中搜索到的顶点不一定是路径上的顶点。,结论:,3. 由它出发进行的深度优先遍

25、历已经完成的顶点不是路径上的顶点。,void DFSearch( int v, int s, char *PATH) / 从第v个顶点出发递归地深度优先遍历图G, / 求得一条从v到s的简单路径,并记录在PATH中 visitedv = TRUE; / 访问第 v 个顶点 Append(PATH, getVertex(v); / 第v个顶点加入路径 for (w=FirstAdjVex(v); w!=0 / 从路径上删除顶点 v ,2. 求两个顶点之间的一条路径 长度最短的路径,若两个顶点之间存在多条路径,则其中必有一条路径长度最短的路径。如何求得这条路径?,a,b,c,h,d,e,k,f,g

26、,因此,求路径长度最短的路径可以基于广度优先搜索遍历进行,但需要修改链队列的结点结构及其入队列和出队列的算法。,深度优先搜索访问顶点的次序取决于图的存储结构,而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,例如:求下图中顶点 3 至顶点 5 的一条最短路径。,链队列的状态如下所示:,3 1 2 4 7 5,Q.front Q.rear,3,2,1,4,7,5,6,8,9,1) 将链队列的结点改为“双链”结点。即 结点中包含next 和priou两个指针;,2) 修改入队列的操作。插入新的队尾结点时,令其priou域的指针指向刚刚出队列的结点,即当前的队头指针所指结点;,3) 修改出队

27、列的操作。出队列时,仅移动队头指针,而不将队头结点从链表中删除。,typedef DuLinkList QueuePtr; void InitQueue(LinkQueue e = Q.front-data ,7.4 (连通网的)最小生成树,假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网?,问题:,构造网的一棵最小(代价)生成树,即:在 e 条带权的边中选取 n-1 条边(不构成回路),使“权值之和”为最小。,算法二:(克鲁斯卡尔算法),该问题等价于:,算法一:(普里姆算法),MST性质: 假设N=(V, E)是一个连

28、通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中uU,v V-U,则必存在一棵包含边(u,v)的最小生成树。,取图G=(V, E)中任意一个顶点 v 作为生成树的根(U=v),之后往生成树上添加新的顶点 w。在添加的顶点 w (wV-U)和已经在生成树上的顶点v (vU) 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。,普里姆(Prim)算法的基本思想:,例如:,所得生成树权值和,= 14+8+3+5+16+21 = 67,a,b,c,d,e,g,f,19,5

29、,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,在生成树的构造过程中,图中 n 个顶点分属两个集合:已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ,则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,设置一个辅助数组,对当前 VU集合中的每个顶点,记录和顶点集U中顶点相连接的代价最小的边:,struct VertexType adjvex; / U集中的顶点序号 VRType lowcost; / 连接边的最小权值 closedgeMAX_VERTEX_NUM;,例如:

30、,a,a,a,19,14,18,14,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,16,21,void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始,Uu for (i=0; iG.vexnum; +i) ,继续向生成树上添加顶点;

31、,k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ;,具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵

32、树为止,这棵树便是连通网的最小生成树。,考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小,但不能出现回路。,克鲁斯卡尔(Kruskal)算法的基本思想:,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,算法描述:,构造非连通图 ST=( V, ); k = i = 0; / k 统计选中的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路, 则

33、输出边(u,v); 且 k+; ,typedef struct VertexType vex1; VertexType vex2; VRType weight; EdgeType; typedef ElemType EdgeType; typedef struct / 有向网的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点 EdgeType edgeMAX_EDGE_NUM; / 边 int vexnum,arcnum; / 图中顶点数和边数 ELGraph,void MiniSpanTree_Kruskal(ELGraph G, SqList / 返回边e的两个

34、顶点所在树的树根,if (r1 != r2) if (ListInsert(MSTree, k, e) k+; /选定生成树上第k条边e插入生成树 mix_mfset(F, r1, r2); / 将两棵树归并为一棵树 / if i+; / 继续考察下一条权值最小边 / while DestroySet(F); / MiniSpanTree_Kruskal,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,7.5 重连通图和关节点,问题: 若从一个连通图中删去任何一个顶点及其相关联的边,它仍为一个连通图的话,则该连通图被称为重(

35、双)连通图。,如何判别给定的连通图是重连通图?,若连通图中的某个顶点和其相关 联的边被删去之后,该连通图被分割 成两个或两个以上的连通分量,则称 此顶点为关节点。,没有关节点的连通图为重连通图。,若在连通图中至少删除k个顶点才能破坏图的连通性,则称此图的连通度为k。,关节点有何特征?,假设从某个顶点V0出发对连通图进行深度优先搜索遍历,则可得到一棵深度优先生成树,树上包含图的所有顶点。,需借助图的深度优先生成树来分析。,若生成树的根结点,有两个或两个以上的分支,则生成树的根必为关节点;,对生成树上的任意一个“顶点”,若其某棵子树的根和子树中其它“顶点”都没有和其祖先相通的回边,则该“顶点”必为

36、关节点。,7.6 两点之间的 最短路径问题,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径长度递增的次序,求得各条路径,源点,v1,v2,v0 -v1:在这条路径上,必定只含一条弧,并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点:,第一条路径长度最短的最短路径的特点:,它只可能有两种情况:或者是v0 -v2 (只含一条弧); 或者是v0 -v1 v2 (由两条弧组成)。,其余最短路径的特点:,再下一条路径长度次短的最短路径的特点:,它可能有三种情况:或者是v0 -v3 (只含一条弧);或者是v0 -v1 -v3

37、 (包含两条弧);或者是v0 -v1 -v2 -v3 (包含三条弧) 。,它或者是直接从源点到该点(只含一条弧); 或者是从源点经过已求得最短路径的顶点,再到达该顶点。,求最短路径的迪杰斯特拉算法:,一般情况下, Distk = 或者 = + 。,设置辅助数组Dist,其中每个分量Distk 表示当前所求得的从源点到其余各顶点 k 的最短路径。,可以用反证法证明:上面所述的其它顶点j必定是已求得最短路径且与v0相通的顶点,且顶点j的最短路径中的顶点必然也已求得最短路径。 即:从v0到k的最短路径或者是从v0到k(G),或者是中间只经过已求得最短路径的顶点j而到达k的一条路径。,1)在所有从源点

38、出发的弧中选取一条权值最小的弧,即为第一条最短路径。,2)假设已求得最短路径的顶点为u,修改与u相邻的其它各顶点的Distk值 若 Distu+G.arcsuk Distk 则将 Distk 改为 Distu+G.arcsuk。,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为第一条最短路径的长度。,求每一对顶点之间的最短路径,弗洛伊德算法的基本思想是:,从vi到vj的所有可能存在的路径中,选出一条长度最短的路径。,若存在,则存在路径vi,vj / 路径长度为1,且其中不含其它顶点 若,存在,则存在路径vi,v1,vj /路径长度为2,且其中所含顶点序号, ,存在, 则存在一条路径v

39、i, v1, v2, vj / 路径长度为3,且其中所含顶点序号=2 ,依次类推,则 vi 至 vj 的最短路径应是上述这些路径中,路径长度最小者。,7.7 拓扑排序,问题:,假设以有向图表示一个工程的施工图或程序的数据流图,则图中不允许出现回路。,检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。,何谓“拓扑排序”?,对有向图进行如下操作:,按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。,例如:对于下列有向图,B,D,A,C,可求得拓扑有序序列: A B C D 或 A C B D,由此所得顶点的线性序列称之

40、为拓扑有序序列,B,D,A,C,反之,对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,如何进行拓扑排序?,一、从有向图中选取一个没有前驱 的顶点,并输出之;,重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。,二、从有向图中删去此顶点以及所 有以它为尾的弧;,在算法中需要用定量的描述替代定性的概念:,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减1,取入度为零的顶点v; while (v0) printf(v); +m; w=FirstAdj(v); while (w0) inDegreew-; w:=nextAdj(v,w

41、); /v的所有邻接点入度-1 取下一个入度为零的顶点v; if mn printf(“图中有回路”);,算法描述:,为避免每次都要搜索入度为零的顶点, 在算法中设置一个“栈”,以保存“入度为零”的顶点。,CountInDegree(G,indegree); /对各顶点求入度 InitStack(S); for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度为零的顶点入栈,count=0; /对输出顶点计数 while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=First

42、Adj(v); w; w=NextAdj(G,v,w) - indegree(w); / 弧头顶点的入度减一 if (!indegreew) Push(S, w); /新产生的入度为零的顶点入栈 if (countG.vexnum) printf(“图中有回路”),7.8 关键路径,假设以有向网表示一个施工流图,其中的顶点表示事件,弧表示活动(子工程项) ,弧上的权值表示完成该项子工程所需时间(持续时间);指向顶点的弧表示该顶点(事件)所依赖的活动(必须先完成),该顶点所引出的弧表示该事件(顶点)发生后可以启动的活动。,=边表示活动网-AOE网,问:哪些子工程项的拖延将影响整个工程的完成期限?

43、 即:哪些子工程项是“关键工程”,问:哪些子工程项允许拖延?最多拖延多长时间而不影响整个工程的完成期限? 即:哪些子工程项是“非关键工程”? 可以延迟多长时间?,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,例如:,“关键活动”指的是:该弧上的权值增加 将使有向图上的最长路径的长度增加。,整个工程完成的时间为:从有向图的源点到终点的最长路径。,源点,终点,6,1,7,4,如何求关键活动?,“事件(顶点)” 的 最早发生时间 ve(j) ve(j) = 从源点到顶点j的最长路径长度;,ve(源点) = 0; ve(k) = Maxve(j) + dut(),“事

44、件(顶点)” 的 最迟发生时间 vl(k) vl(k)=从源点到终点的最长路径长度 从顶点k到终点的最长路径长度 vl(终点) = ve(终点); vl(j) = Minvl(k) dut(),假设第 i 条弧(第 i 项活动)为 ,其持续时间为dut(), 则 对第 i 项活动而言 “活动(弧)”的 最早开始时间 ee(i) ee(i) = ve(j); “活动(弧)”的 最迟开始时间 el(i) el(i) = vl(k) dut();,0,0,0,0,0,0,0,0,0,6,4,5,7,11,5,7,15,14,18,18,18,18,18,18,18,18,18,18,16,14,8,

45、6,6,10,8,0,7,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,边:,0 0 2 3 0 3 1 0 0,关键路径:a-b-e-h-k,算法的实现要点:,显然,求ve的顺序应该是按拓扑有序的次序; = 从前向后,而 求vl的顺序应该是按拓扑逆序的次序 = 从后向前 因为 拓扑逆序序列即为拓扑有序序列的 逆序列,,因此 应该在拓扑排序的过程中, 另设一个“栈”记下拓扑有序序列。,7.1 抽象数据类型图的定义,7.2 图的存储表示,7.3 图的遍历,7.4 最小生成树,7.5 重(双)连通图和关节点,7.6 两点之间的最短路径问题,7.7 拓扑排序,7.8 关键路径,1. 熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 2. 熟练掌握图的两种搜索路径的遍历:遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。,在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 3. 应用图的遍历算法求解各种简单路径问题。 4. 理解各种图的算法。,上机题目:(11月23日),1、 树和图的类型定义及基本操作,2、 二叉树的三种遍历方式,4、 图的最小生成树算法,5、 图的最

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 其他


经营许可证编号:宁ICP备18001539号-1