




已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构重难点串讲,讲师:翔高教育一级培训师地点:上海,第5章图,重难点导航,图的存储结构,尤其是邻接矩阵和邻接表图的遍历算法;广度优先搜索遍历和深度优先搜索遍历。图的遍历是图各种运算的基础最小生成树的生成算法以及过程,熟练掌握Prim和Kruskal算法,特别是利用两算法手工模拟生成树的生成过程图的应用:最小生成树,拓扑排序,关键路径,最短路径,邻接矩阵表示法(数组表示法),用一个一维数组存放图的顶点数据用一个矩阵Ann来存放图的边的信息:,图的邻接矩阵定义:typedefstruct/弧结点与矩阵的类型VRTypeadj;/VRType为弧的类型。图-0,1;网-权值InfoType*Info;/与弧相关的信息的指针,可省略ArcCell,AdjMatrixmax_nmax_n;typedefstruct/图的类型VertexTypevexsmax_n;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/顶点数,边数GraphKindkind;/图类型MGraph;,G.arcs=,G.vexs=,无向图的邻接矩阵,存放顶点的数组,表示边的矩阵,G.arcs=,G.vexs=,有向图的邻接矩阵,存放顶点的数组,表示弧的矩阵,V4的出边邻接点,V4的入边邻接点,无向图邻接矩阵的特点:对称矩阵顶点Vi的度等于第i行非零元个数,或第i列非零元个数:矩阵非零元总数等于边数的2倍,有向图邻接矩阵的特点:是非对称矩阵第i行非零元个数等于顶点Vi的出度;第i列非零元个数等于顶点Vi的入度:矩阵非零元总数等于边数,G.arcs=,G.vexs=,有向网的邻接矩阵示例:,7.2.1邻接表表示法将每个顶点的邻接点串成一个单链表:,边结点,顶点结点,firstarc,G.vertices,无向图的邻接表:,无向图邻接表的特点:顶点Vi的度等于Vi所引导的单链表的长度边结点的个数等于边数的2倍,有向图的邻接表:,firstarc,G.vertices,有向图邻接表的特点:顶点Vi引导的单链表是出边链,链表的长度等于Vi的出度找一个顶点的出边容易,找入边需要遍历整个邻接表边结点的个数等于边数,深度优先搜索遍历(DFS),DepthFirstSearch;类似于树的先根遍历;优先向纵深访问,DFS遍历过程:从图G中选某个顶点V作为出发点;访问V;依次从V的未被访问的邻接点出发,深度优先搜索遍历图G,直至与V相通的顶点都被访问完;如果此时图G中还有顶点未曾被访问,则从这些未被访问的顶点中再选一个顶点V,转2,继续遍历;否则遍历结束。,V1,V7,V4,V3,V5,V6,V2,DFS访问序列:,V1,V2,V5,V6,V7,V3,V4,V1,DFS访问序列:,V3,V2,V4,V9,V1,V6,V5,V2,V4,V3,V6,V5,V8,V7,V9,V8,V7,V8,V3,V1,V7,V4,V9,V5,V6,V2,DFS访问序列:,V1,V9,V7,V2,V5,V6,V4,data,8,7,V7,6,V6,5,V5,4,V4,3,V9,2,V2,1,V1,0,firstarc,V8,V3,V3,V8,V1,V7,V4,V3,V5,V6,V2,V8,data,8,V8,7,V7,6,V6,5,V5,4,V4,3,V3,2,V2,1,V1,0,firstarc,G.vertices,DFS访问序列:,V1,V2,V3,V6,V5,V8,V7,V4,BFS遍历过程:从图G的某个顶点v出发,访问v;依次访问V的未被访问的邻接点;再按照“先被访问顶点的邻接点先访问”的次序,依次访问这些邻接点的邻接点,直至图中所有已被访问的顶点的邻接点都被访问到;若此时图中还有顶点未曾被访问,则另选一个未被访问的顶点v作为出发点,重复上述过程,直至图中所有的顶点都被访问完。,V1,BFS访问序列:,V3,V2,V1,V6,V4,V5,V9,V2,V4,V3,V6,V5,V8,V7,V9,V8,V7,V1,V7,V4,V3,V5,V6,V2,V8,访问序列:,V1,V2,V4,V5,V6,V7,V8,V3,data,8,V8,7,V7,6,V6,5,V5,4,V4,3,V3,2,V2,1,V1,0,firstarc,求无向图的连通分量:对无向图G调用一次DFS过程,能访问完G的一个连通分量。因此对DFS算法稍做修改就可解决求无向图连通分量的问题。,最小生成树,最小(代价)生成树:无向网的所有生成树中,边权之和最小的生成树。构造最小生成树的著名算法:Prim算法Kruskal算法,在n个城市之间建通讯网;可能的线路最多有n(n-1)/2条;从中选择n1条,满足:(1)连通;(2)边上权值之和为最小。这就是构造最小代价生成树。,最小生成树的MST性质:设G(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,且uU集,vVU集,则必存在一棵包含边(u,v)的最小生成树。,V1,V2,V4,V5,V6,V3,5,6,1,3,2,6,6,5,5,4,U集(红点集),VU集(蓝点集),最小紫边一定会在G的某棵最小生成树上出现,Prim算法思想:由于红点集与蓝点集的划分是任意的,经过n1次不同的划分,找到每次划分的最小紫边,以此来构成最小生成树的n-1条边。在每次划分中,每个蓝点可能有多条紫边连接红点。为了简化,我们将每个蓝点用一条最小的紫边连接到红点上,构成生成树的n1条边。,初态:任选一个顶点作为红点,不妨设是V1。邻接矩阵的V1行就是n1条连接蓝点的紫边。从紫边集中选一条最小的紫边,将相应的蓝点Vj变成红点。检测剩余蓝点到新红点Vj的边是否小于原来的紫边。若小,则用蓝点到新红点Vj的紫边取代原来的紫边,Prim算法的存储结构(1):无向网用邻接矩阵表示,A,F,E,G,D,C,B,A,F,E,G,D,C,B,设:初态时红点集中只有一个顶点A;邻接矩阵的第0行表示了所有的紫边,A,F,E,G,D,C,B,12,A,A,A,A,A,A,16,14,0,B,10,B,7,选中最小紫边(A,B);B并入红点集;调整蓝点C,F所关联的紫边,A,F,E,G,D,C,B,A,B,A,A,B,A,10,14,0,F,6,7,选中最小紫边(B,F);F并入红点集;调整蓝点C,E,G所关联的紫边,0,F,2,9,F,A,F,E,G,D,C,B,A,F,A,F,B,F,6,2,9,0,0,选中最小紫边(F,E);E并入红点集;调整蓝点C,D,G所关联的紫边,0,E,5,E,4,E,8,A,F,E,G,D,C,B,A,E,E,F,B,E,5,4,16,8,0,B,0,选中最小紫边(E,D);D并入红点集;调整蓝点C所关联的紫边,0,D,3,0,A,F,E,G,D,C,B,A,E,E,F,B,E,3,0,8,0,0,选中最小紫边(D,C);C并入红点集;没有需要调整的紫边,0,0,A,F,E,G,D,C,B,A,E,E,F,B,E,0,8,0,0,选中最小紫边(E,G);G并入红点集;最小生成树构造完毕,0,0,0,Kruskal算法:,A,B,C,D,E,F,A,F,E,G,D,C,B,G,ABCDE,FG,ABC,DE,FG,ABC,D,E,FG,AB,C,D,E,FG,AB,C,D,E,F,G,A,B,C,D,E,F,G,经典例题解析,【例1】若无向图G=(V,E)中合有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是A6B15C16D21【解析】无向图中,如果每个顶点都有到其它所有顶点的路径,那么这个无向图是连通图。这个题是要保证图G在任何情况下都是连通的所需要的最少边数,关键是要把握“在任何情况下都是连通的”。在顶点固定的情况下,全连通图用的边最多。极端情况是所有的边都被用于将部分顶点连接成全连通图,而另一个部分顶点被孤立。15条边能够保证6个顶点的无向图成为全连通图,所以若只有15条边,则可能出现6个顶点全连通而第7个顶点被孤立的情况。再加上一条边就能保证7个顶点的无向图在任何情况下的连通性,所以答案是C,最少加数是16条。,对下图进行拓扑排序,可以得到不同拓扑序列的个数是A.4B.3C.2D.1【解析】拓扑排序是指有向无环图中各顶点构成的有序序列。拓扑排序的步骤为:(1)在有向图中选一个没有前驱的顶点并且输出之;(2)从图中删除除该顶点和所以以它为尾的弧。重复上述两步,直至全部顶点均已输出。由于没有前驱的顶点可能不唯一,所以拓扑排序的结果也不唯一。根据拓扑排序的构
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 纸容器印刷与装饰技术考核试卷
- 贵金属精炼中的贵金属矿床资源可持续发展战略规划考核试卷
- 运动防护用具材料研发进展考核试卷
- 选矿实验方法与技巧考核试卷
- 水电工程信息系统安全与防护措施考核试卷
- 草原生态保护与利用考核试卷
- 小儿饮食护理
- 海外留学申请文书专业撰写与推广服务协议
- 海外复杂地质环境无人机租赁及地质成果解析协议
- 金融存管安全风险评估及应对协议
- GB/T 3299-2011日用陶瓷器吸水率测定方法
- GB/T 18867-2014电子工业用气体六氟化硫
- FZ/T 51011-2014纤维级聚己二酰己二胺切片
- 第15课《驿路梨花》教学实录
- 思想道德修养与法律基础(完整版PPT)
- 动物英语俚语课件
- 幼儿园课件-神奇的中草药
- 金坛区苏科版六年级心理健康教育第18课《中学遐想》课件(定稿)
- 小学生民法典主题班会PPT
- 甲状腺的外科治疗与病ppt课件
- 国家开放大学《课程与教学论》形考任务1-4参考答案
评论
0/150
提交评论