数据结构第八章图ppt课件.ppt
《数据结构第八章图ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构第八章图ppt课件.ppt(75页珍藏版)》请在三一办公上搜索。
1、1,数 据 结 构(第八章 图) Data Structures胡学钢 张 晶计算机与信息学院 2009年2月,2,第八章 图 (Graph),第八章 图(Graph) 8.1 基本概念和运算 8.2 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径,3,8.1 基本概念和运算,图 由顶点集V和连接顶点的弧集E所组成的结构, 记作 G = ( V, E )。 其中弧的形式为, 表示从顶点Vi到Vj之间有一条弧,图形表示为: Vi Vj 有向图例:如右图中的G1就是一个有向图: 其中: 顶点集合 V=1,2,3,4 弧集 E= , , , , ,4,8.
2、1 基本概念和运算,如果顶点间的关系是相互的,即弧的两端没有方向,则图为无向图。其中的弧称为边。边的形式为(Vi,Vj),图形表示为: Vi Vj例:如右图中的G2就是一个无向图: 其中: 顶点集合 V=1,2,3,4 边集 E= (1,2),(1,3),(1,4) (2,4),(3,4) ,5,8.1 基本概念和运算,若G中每条边(弧)对应一个数值表示关系的程度,则称图G为网络。 例: 图G3 就是一个网络 对图G = ( V, E ),若存在G1=(V1,E1), 满足V1V,E1E。则G1是G的子图。 例如:右图G4 就是G2 的子图。,6,8.1 基本概念和运算,顶点间关系: 如果 E
3、 则称 Vi,Vj相邻接, Vi邻接到Vj,Vj邻接自Vi。 例如,右 图中, V1邻接到V2,V4邻接自V3 若( Vi,Vj )E则称Vi,Vj相邻接 顶点的度 顶点的邻接点的数目。 有向图中:入度,出度。 度入度出度。,7,8.1 基本概念和运算,路径 若 顶点序列Vi1,Vi2,Vik, 满足E或 者(Vil,Vi(l+1)E)(l=1,2,k-1), 则该顶点序列Vi1,Vi2,Vik 构成一条路径。 例: 图G1中,1,2,4,1,3,4是一条路径简单路径 中间经过的顶点不重复的路径。 例:图G1中,( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。回路
4、 首尾相同的路径。 例如, ( 1,3,4,1 )简单回路 简单路径 + 回路,8,8.1 基本概念和运算,若无向图中任意两点间都存在路径 则称为连通图。 否则,称为不连通图(非连通图)。 非连通图包含若干连通分量 极大连通子图。 若有向图中的任意两点间可以互相到达 则称为强连通图。,9,8.1 基本概念和运算,若无向图中任意两点间都有一条边 则称为无向完全图。 (共有n (n-1) / 2条边)若有向图中每个顶点到其余各点均有一条弧 则称为有向完全图。 (共有n (n-1) 条边),10,8.1 基本概念和运算,若无向图满足:连通并且无回路 则称为树。 树的定义有如下几个等价的描述: 有最少
5、边数的连通图。 有n-1条边的连通图。 连通的无环图。有向树 如果在有向图中, 有一个顶点的入度为0,其余顶点的入度为1, 则称此图为有向树。 并称其中入度为0的顶点为有向根。 右下图就是一个有向树,其中顶点1就是有向根。,11,8.1 基本概念和运算,图的运算: 基本运算: 初始化图 插入顶点 插入边(弧) 修改权值 删除顶点 删除边(弧) 求指定顶点的邻接点 常用运算: 遍历,12,8.1 基本概念和运算,邻接点的求解方法: 具体实现依赖于图的存储结构, 可以考虑用两个运算来实现求解: int firstadj(G,v); 返回顶点v的第一个邻接点号。 若不存在时,返回0(或定义为-1)。
6、 int nextadj(G,v,w); 返回顶点v的邻接点中处于邻接点w之后的邻接点号。 若不存在时,返回0(或定义为-1)。,13,8.2 图的存储,图的存储 图结构在计算机中的存储形式1. 邻接矩阵 (1)不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示, 1 E 其中 Aij 0 否则例:,0 1 1 00 0 0 10 0 0 11 0 0 0,行的方向:发出的弧列的方向 :进入的弧,14,8.2 图的存储,(2) 网络的表示方法 wij E Aij 0 或 否则例:, 4 3 54 23 65 2 6 ,0 1 1 11 0 0 11 0 0 11 1 1 0,无向图的邻接矩
7、阵对称,15,8.2 图的存储,2. 邻接表表示法 将邻接点构成链表 例:,data,firstadj,16,8.2 图的存储,逆邻接链表 将“邻接自”的顶点连成链表,data firstadj,data firstadj,代表弧,17,8.3 图的遍历,图的遍历访问图中所有顶点一次且仅且一次。 深度优先搜索遍历 图的两种遍历算法 广度优先搜索遍历8.3.1 深度优先搜索遍历(Depth First Search) 这一问题求解包括几个部分。 1. 基本算法 从顶点v0出发深度优先搜索遍历图G的dfs (v0)描述如下: (1) 访问v0; (2) 依次从v0的未被访问过的邻接点出发深度遍历。
8、,18,dfs(8),dfs(9),dfs(4),dfs(3),8.3.1 深度优先搜索遍历,下面以下图为例来讨论dfs算法的执行过程:调用dfs(1),此箭头表示是从遍历运算dfs(1)中调用dfs(2),即从顶点1直接转到2,此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中,即从顶点3返回到2,9,dfs(1),dfs(2),dfs(5),dfs(6),dfs(7),dfs(10),在访问顶点3后,由于顶点3的邻接点已全被访问,故dfs(3)执行到此结束,应返回到调用层,即返回到dfs(2),dfs(1)包含如下两部分操作:(1)访问顶点1;(2)依次执行dfs(2)和d
9、fs(8),19,8.3.1 深度优先搜索遍历,将dfs(1)执行过程中所搜索的边连接起来(有标注的边),得到一棵生成树-dfs生成树。,原图及其搜索示意图,dfs(1)生成树,20,8.3.1 深度优先搜索遍历,下面讨论dfs算法的设计。为此,先回顾一下dfs (v0)的描述: (1) 访问v0; (2) 依次从v0的未被访问过的邻接点出发深度遍历。 分析:由算法描述可知: 访问顶点v0的基本操作: 可用visite(v0)简单表示。 设置访问标志数组visited ,并约定: 某顶点vi未被访问时, visitedi=FALSE(初值) vi被访问过后, visitedi=TRUE(初值)
10、 求邻接点可以采用两个函数: firstadj(G,v) :返回v的第一个邻接点(号),或0(不存在时)。 nextadj(G,v,w);返回v的第邻接点中处于邻接点w之后的邻接点号, 或0(不存在时),访问v0时, visitedi=TRUE;,21,Y,N,8.3.1 深度优先搜索遍历,由讨论可得到dfs算法的流程图如下:由此得深度遍历基本算法dfs(v0)如下 : void dfs(int v0) visite(v0); visitedv0=TRUE; w=firstadj(G,v0); while(w!=0) if(!visitedw) dfs(w); w=nextadj(G,v0,w
11、); ,N,visite(v0); visitedv0=TRUE;,W=0?,W被访问过?,dfs(w);,w=nextadj(G,v,w);,w=firstadj(G,v) :,22,8.3.1 深度优先搜索遍历,问题: (1)dfs算法是否适用于有向图? (2)如何设置标志数组visited的初值? 能否在dfs算法中设置? (3)从某顶点出发是否能保证访问到所有顶点? 或者说:选择一个起点调用一次dfs算法,能否实现对整个图的遍历?2. 遍历整个图的算法 dfs算法在应用于非连通图,或者是某些有向图时, 某一次调用就不能保证访问到所有顶点。如下图所示。,23,8.3.1 深度优先搜索遍历
12、,为此,需要重新选择起点来调用dfs算法。 如何选择新的起点? 起点应满足什么条件?将对访问标志数组的赋初值运算, 以及选择起点的控制合在一起,构成对整个图的遍历算法如下:void travel_dfs(graph G) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if(!visitedi) dfs(i); ,24,8.3.1 深度优先搜索遍历,3. 深度遍历算法的应用问题: (1)如何设计算法以判断给定的无向图是否是连通的? (2)如何设计算法以求解给定的无向图中的边数? (3)设计算法以判断给定的无向图是树。 (4)设计算法以
13、判断给定的有向图是以v0为根的有向树。 (5)设计算法以判断图中的一个节点是否为关节点。,25,8.3.1 深度优先搜索遍历,例1 设计算法以求解无向图G的连通分量的个数。分析:对无向图G来说,选择某一顶点v执行dfs(v), 可访问到所在连通分量中的所有顶点 因此,选择起点的次数就是图G的连通分量数, 这可通过修改遍历整个图的算法dfs_travel来实现:每调用一次dfs算法计数一次。 另外,考虑到要求求解连通分量数, 因而可以将算法设计为整型函数。 具体算法如下:,26,8.3.1 深度优先搜索遍历,int numofGC(graph G) int i; int k=0; / k用于连通
14、分量的计数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE) k+; dfs(G,i); /用k来累计连通分量个数 return k ;,遍历整个图的算法dfs_travel中的原来的部分,27,8.3.1 深度优先搜索遍历,例2 设计算法求出无向图G的边数。算法如下:void dfs (graph G, int v ) int w; visitedv=TRUE; /设置访问标志(访问结点的其它操作被省去) w=firstadj(G,v); while (w!=0) E+; /此处意味着找到一条边
15、,故累计到变量E中 if (visitedw=FALSE) dfs(G,w); w=nextadj(G,v,w); ,dfs算法中原有的操作,28,8.3.1 深度优先搜索遍历,int Enum (graph G ) int i; E=0; /全局变量E记录整个图中的边数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE;) dfs(G,i); return E/2;,遍历整个图的算法dfs_travel中的原来的部分,29,8.3.1 深度优先搜索遍历,4. 深度遍历算法的应用二例3:设计算法,将
16、1-n(=20,或其他数)放在一个环上,使环上任意两个相邻元素的和为质数。分析:可以用图来描述该问题: 用顶点表示一个数 若两个数的和为质数, 则对应顶点之间有一条边。 例如,若n=10,对应图如右所示。在这一表示下,问题转化为:求图中包含所有顶点的简单回路。如图所示的一个解。(1,2,3,4,7,6,5,8,9,10),30,8.3.1 深度优先搜索遍历,算法设计中需要注意的: 通过在dfs算法的基础上变化而得: (1)路径的记录:需要增加变量或参数以记录路径,因此,不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。 (2)若某些走法行不通,需要重来,为此,要恢复visitedi标志
17、。 (3)需要判断首尾相接。,31,8.3.1 深度优先搜索遍历,算法构思如下:(1)设环上已有k个元素(0kn)。(2)若kn, 且不在当前路径上的顶点中存在与Bk相邻的, 则依次从余下的顶点中取出与Bk相邻的顶点放置在Bk+1中, 转(1)。(3)若kn,而在余下的这些顶点中找不到一个与BK相邻的顶点, 或者是虽然存在邻接点,但这些结点均已在同等条件下放置过了,因而须从环上去掉BK,转(1)。(4)若k=,有两种情况: (a)Bn与B1相邻接, 说明已求得一解, 则输出求解结果, 然后返回。 (b)Bn与B1不邻接,说明前面的放置法不行, 即不构成环, 因而需要重新放置,即要去掉Bn和Bn
18、-1,然而转(1)。为避免遗漏某种放置,从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。,32,8.3.1 深度优先搜索遍历,采用递归方式实现如下: 其中visited为标志数组,表示各结点是否在当前的路径上。void getcc(int k) / A,B,visited为全局变量,k初值为1,B1固定为1 int i; if (k=n / 取消顶点i的放置,以便可被重新放入 调用前,要产生邻接矩阵 A的值。数组visited全置为FALSE, visited1置为TRUE。k为1,B1为1。本递归算法利用函数调用及返回实现搜索与回溯,若不用递归,本算法则较为麻烦。试模拟执行之。,33
19、,8.3.2 广度优先搜索遍历,8.3.2 广度优先搜索遍历(Breadth_first search) 广度优先遍历 由近及远逐层访问顶点(典型的层次遍历) 1. 基本算法 从顶点v0出发广度优先搜索遍历图的算法bfs(v0): (1)访问v0 (2)依次访问v0的各邻接点。 (3)设最近一层访问序列为vi1,vi2,vik, 则依次访问 vi1,vi2,vik的 未被访问过的邻接点。,34,8.3.2 广度优先搜索遍历,bfs(1)的执行过程如下图所示。其中用红线标注搜索路线。将搜索的便连起来得到bfs生成树。,bfs生成树,35,8.3.2 广度优先搜索遍历,算法构思: (1) 设访问标
20、志数组; (2)为了能依次访问上一层次的访问序列中的各顶点的邻接点, 需要设置一个结构以保存上一层次的顶点, 这一结构还要满足这样的要求: 这一层中最先被访问的顶点,其后继也应被最先检测到。 由此可知,这一结构应是队列。 (3)既然涉及到队列(不妨Q),则需要安排队列的运算: (a) 初始化; (b) 入队:每访问一个顶点v,除了访问操作、设置标志外,还要将其入队。 (c) 出队:从队列中删除一个顶点v,这意味着要依次访问v的所有未被访问过的邻接点。,36,8.3.2 广度优先搜索遍历,广度遍历的基本算法如下:void bfs(int v0) Queue Q; visite(v0); visi
21、tedv0=TRUE; Q.append(v0); while(!Q.Empty() v=Q.Serve(); w=firstadj(G,v); while(w!=0) if(!visitew) visite(w); visitedw=TRUE; Q.append(w); w=nextadj(G,v,w); ,37,8.3.2 广度优先搜索遍历,2. 遍历整个图的算法 void travel_bfs(graph G) for(i=1;i=n;i+) visitedi=FALSE; for(i=1;i=n;i+) if(!visitedi) bfs(i); 3.广度遍历算法的应用例:迷宫中的最短
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第八 ppt 课件
链接地址:https://www.31ppt.com/p-1350170.html