电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数据结构习题解析第8章VIP专享VIP免费

数据结构习题解析第8章_第1页
数据结构习题解析第8章_第2页
数据结构习题解析第8章_第3页
158 第8 章 图 一、复习要点 图是一种重要的非线性结构。它的特点是每一个顶点都可以与其它顶点相关联,与树不同,图中各个顶点的地位都是平等的,对顶点的编号都是人为的。通常,定义图由两个集合构成:一个是顶点的非空有穷集合,一个是顶点与顶点之间关系(边)的有穷集合。对图的处理要区分有向图与无向图。它的存储表示可以使用邻接矩阵,可以使用邻接表,前者属顺序表示,后者属链接表示。在本章着重讨论了图的深度优先搜索和广度优先搜索算法,附带引入了生成树与生成森林的概念。对于带权图,给出了最小生成树的两种方法:Prim算法和 Kruskal 算法,后者使用了最小堆和并查集作为它的辅助求解手段。在解决最短路径问题时,采用了逐步求解的策略。最后讨论了作工程计划时常用的活动网络。涉及的主要概念是拓扑排序和关键路径,在解决应用问题时它们十分有用。 本章复习的要点是: 1 、基本知识点 主要要求理解图的基本概念,包括图的定义、图的连通性、图的路径和路径长度、图中各顶点的度及度的度量、无向连通图的最大边数和最小边数,有向强连通图的最大边数与最小边数等。掌握图的存储表示,包括邻接矩阵和邻接表,以及这些存储表示上的典型操作,如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。并要求掌握图的两种遍历算法:深度优先搜索和广度优先搜索算法,以及求解连通性问题的方法。理解求解关节点及构造重连通图的方法。此外,要求掌握构造最小生成树的 Prim 算法和 Kruskal 方法,掌握活动网络的拓扑排序算法,掌握求解关键路径的方法。需要注意的是,让某个关键活动提前完成,是否能让整个工程提前完成。 2 、算法设计  建立无向带权图的邻接表的算法,要求输入边的数目随机而定。  图的深度优先搜索的递归算法。  利用图的深度优先搜索的递归算法建立图的深度优先生成森林(用左子女右兄弟表示)的算法。  图的广度优先搜索算法。  利用图的广度优先搜索算法建立图的广度优先生成森林(用左子女右兄弟表示)的算法。  求解最小生成树的 Prim 算法,注意 nearvex和 lowcost 辅助数组的变化。  求解最小生成树的 Kruskal 算法,注意 minheap 和 UFset 的变化。  求解最短路径的 dijkstra 算法,注意 dist 辅助数组的变化。  有向图中求解拓扑排序的算法,要求用邻接表作为图的存储表示。注意算法执行过程中入度为零的顶点栈的变化。  有...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部