2020考研计算机数据结构知识点:图
2019.04.30 19:00

  2020年计算机考研复习已经开始,新东方在线在此整理了2020考研计算机数据结构知识点:图,希望能帮助大家!

  1.图的基本概念,包括:图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、路径长度、回路、(强)连通图、(强)连通分量等概念。掌握与这些概念相联系的相关 计 算题。在基本概念中,完全图、连通分量、生成树和邻接点是重点。

  2.图的存储形式。图是复杂的数据结构,有顺序和链式两种存储结构:数组表示法(重点是邻接矩阵),邻接表与逆邻接表,这两种存储结构对无向图和有向图均使用。

  3.熟练掌握图的两种遍历算法:深度遍历和广度遍历。深度遍历和广度遍历是图的两种 基本的遍历算法,这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。

  掌握图的两种遍历算法的应用,图一章的算法设计题常常是基于这两种基本的遍历算 法而设计的。例如,在(强)连通图中,主过程一次调用深(广)度优先遍历过程(DFS/BFS),即可遍历全部顶点,故可以用此方法求出连通分量的个数,要会画出遍 历中形成的深(广)度优先生成树和生成森林。又如,“求最长的最短路径问题”和 “判断两顶点间是否存在长为K的简单路径问题”,就用到了广度遍历和深度遍历算法。

  4. 最小生成树的概念。连通图的最小生成树通常是不唯一的,但最小生成树边上的权值 之和是唯一的。掌握最小生成树的构造方法:PRIM算法和KRUSKAL算法,根据这两种算法思想用图示法表示出求给定网的一棵最小生成树的过程。

  5. 拓扑排序是在有向图上对入度(先、后)为零的顶点的一种排序,通常结果不唯一。拓 扑排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法。换句话说,一种是“从前向后”的排序,一种是“从后向前”排。后一种排序出来的结果 是“逆拓扑有序”的。用拓扑排序和深度优先遍历都可判断图是否存在环路。

  6. 关键路径问题是图一章的难点问题。理解关键路径的关键有三个方面:一是何谓关键 路径,二是最早时间的含义及求解方法,三是最晚时间的含义及求解方法。简单地说,最早时间是通过“从前向后”的方法求的,而最晚时间是通过“从后向前”的方法求解的,并且,要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。 熟练掌握求解的过程和步骤。关键路径问题是工程进度控制的重要方法,具有很强的 实用性。理解“减少关键活动时间可以缩短工期”是指该活动为所有关键路径所共有, 且减少到尚未改变关键路径的前提下有效。

  7. 最短路径问题也是为图一章的难点问题。最短路径问题分为两种:一是求从某一点出发到其余各点的最短路径;二是求图中每一对顶点之间的最短路径。解决第一个问题用DIJSKTRA算法,解决第二个问题用FLOYD算法,注意区分。掌握这两个算法,并能手工熟练模拟。掌握用求最短路径问题来解决的应用问题(如旅游景点及旅游路线的选择问题)。


MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved