数据结构复习与习题解析.ppt
《数据结构复习与习题解析.ppt》由会员分享,可在线阅读,更多相关《数据结构复习与习题解析.ppt(29页珍藏版)》请在三一办公上搜索。
1、数据结构 与 算法,复习与习题解析(第6-8讲),第6讲 图,图的相关定义(无向完全图、有向完全图、网、连通图、强连通图、度、入度、出度、生成树和生成森林)图的存储方式邻接矩阵无向图邻接矩阵有向图邻接矩阵网的邻接矩阵每个结点的出度?入度?度?图的边数?邻接表每个结点的出度?入度?度?图的边数?,10/07/2023,2,例已知某网的邻接(出边)表,请画出该网络。,当邻接表的存储结构形成后,图便唯一确定!,例题解析,10/07/2023,3,图的遍历,广度优先搜索从图的某一结点出发,首先依次访问该结点的所有邻接顶点 V1,V2,Vn 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问
2、的顶点,重复此过程,直至所有顶点均被访问为止。深度优先搜索1、访问指定的起始顶点;2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕;3、若此时图中尚有顶点未被访问,则再选其中一个顶点作为起始顶点并访问之,转 2;反之,遍历结束。,10/07/2023,4,例题解析,10/07/2023,5,熟悉图的存储结构,画出右边有向图的邻接矩阵、邻接表、逆邻接表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。,深度优先遍历序列为ABCFED,广度优先遍历序列为ABDCEF,邻接矩阵如下,邻接表如下,逆邻
3、接表如下,【答】,最小生成树,普里姆(Prim)算法将顶点进行归并克鲁斯卡尔(Kruscal)算法将边进行归并,10/07/2023,6,例:Prim算法,最小代价生成树的生成过程,U,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,(4),(1),(3),(2),(5),10/07/2023,7,例:Kruscal 算法,实例的执行过程,图G,1、初始连通分量:0,1,2,3,4,52、反复执行添加、放弃动作。条件:边数不等于 n-1时 边 动作连通分量(0,2)添加0,2,1,3,4,5(3,5)添加0,2
4、,3,5,1,4(1,4)添加0,2,3,5,1,4(2,5)添加0,2,3,5,1,4(0,3)放弃因构成回路(2,3)放弃因构成回路(1,2)添加0,2,3,5,1,4,最小代价生成树,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,5,5,10/07/2023,8,例题解析,请分别用Prim算法和Kruskal算法构造以下网络的最小生成树,并求出该树的代价。,10/07/2023,9,例题解析,10/07/2023,10,【解析】Prim算法的操作步骤:首先从一个只有一个顶点的集合开始,通过加入与其中顶点
5、相关联的最小代价的边来扩充顶点集,直到所有顶点都在一个集合中。,例题解析,10/07/2023,11,【解析】Kruscal算法的操作步骤:首先将n个顶点看成n个互不连通的分量,从边集中找最小代价的边,如果落在不同连通分量上,则将其加入最小生成树,直到所有顶点都在同一连通分量上。,单源最短路径,在带权有向图中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。迪杰斯特拉(Dijkstra)算法:按路径长度递增次序产生最短路径1、把 V 分成两组:(1)S:已求出最短路径的顶点的集合。(2)V-S=T:尚未确定最短路径的顶点集合。2、将 T 中顶点按最短路径递增
6、的次序加入到 S 中,保证:(1)从源点 v0 到 S 中各顶点的最短路径长度都不大于 从 v0 到 T 中任何顶点的最短路径长度。(2)每个顶点对应一个距离值:S中顶点:从 v0 到此顶点的最短路径长度。T中顶点:从 v0 到此顶点的只包括 S 中顶点作中间顶点的 最短路径长度。,10/07/2023,12,Dijkstra 算法步骤:,T 中顶点对应的距离值用辅助数组 D 存放。,Di 初值:若 存在,则为其权值;否则为。,v2,1383032,v2,8,13133032,v3,v1,v1,13,13302220,v3,8+5v2,192220,v4,v4,8+5+6v2-v3,2120,
7、v6,v5,13+7 v1,21,v5,v6,初始时令 S=v0,T=其余顶点。,v0,从 T 中选取一个其距离值最小的顶点 vj,加入 S。,对 T 中顶点的距离值进行修改:若加进 vj 作中间顶点,从 v0 到 vi 的距离值比 不加 vj 的路径要短,则修改此距离值。,重复上述步骤,直到 S=V 为止。,8+5+6+2v2-v3-v4,10/07/2023,13,拓扑排序,AOV网:在一个有向图中,若用顶点表示活动,有向边表示活动间先后关系,称该有向图叫做顶点表示活动的网络(Activity On Vertex network)简称为AOV网。拓扑排序的方法:在有向图中选一个没有前驱的顶
8、点且输出之。从图中删除该顶点和所有以它为起点的弧。重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。,10/07/2023,14,例题解析,拓扑排序的结果不是唯一的,试写出下图任意2个不同的拓扑序列。,10/07/2023,15,【解析】解题关键是弄清拓扑排序的步骤,(1)在AOV网中,选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。,【答案】(1)0132465(2)0123465,关键路径,AOE(Activity on Edge)网络:定义结点为事件,有向边的指向表示事件的执行次序。单位是时间(时刻
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 习题 解析
链接地址:https://www.31ppt.com/p-5466416.html