考研答疑  |  免费领好课入口

2020考研择校择职业指导群

点击关注“四川中公考研”新浪微博，与博主互动获取考研上名校技巧

点击关注“四川中公考研”微信公众号，第一时间获取新考研资讯

职业课协议班、周末面授班、半年集训、暑期集训营

本文是四川中公考研网小编整理的关于“2020计算机职业考研数据结构知识点：图"的相关资讯信息，供大家参考。
        1.图的基本概念，包括：图的定义和特点、无向图、有向图、入度、出度、完图、生成树、路径长度、回路、(强)连通图、(强)连通分量等概念。掌握与这些概念相联系的相关 计 算题。在基本概念中，完图、连通分量、生成树和邻接点是重点。
　　2.图的存储形式。图是复杂的数据结构，有顺序和链式两种存储结构：数组表示法(重点是邻接矩阵)，邻接表与逆邻接表，这两种存储结构对无向图和有向图均使用。
　　3.熟练掌握图的两种遍历算法：深度遍历和广度遍历。深度遍历和广度遍历是图的两种 基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。
　　掌握图的两种遍历算法的应用，图一章的算法设计题常常是基于这两种基本的遍历算 法而设计的。例如，在(强)连通图中，主过程一次调用深(广)度优先遍历过程(DFS/BFS)，即可遍历部顶点，故可以用此方法求出连通分量的个数，要会画出遍 历中形成的深(广)度优先生成树和生成森林。又如，“求长的短路径问题”和 “判断两顶点间是否存在长为K的简单路径问题”，就用到了广度遍历和深度遍历算法。
　　4. 小生成树的概念。连通图的小生成树通常是不的，但小生成树边上的权值 之和是的。掌握小生成树的构造方法：PRIM算法和KRUSKAL算法，根据这两种算法思想用图示法表示出求给定网的一棵小生成树的过程。
　　5. 拓扑排序是在有向图上对入度(先、后)为零的顶点的一种排序，通常结果不。拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。后一种排序出来的结果 是“逆拓扑有序”的。用拓扑排序和深度优先遍历都可判断图是否存在环路。
　　6. 关键路径问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键 路径，二是早时间的含义及求解方法，三是晚时间的含义及求解方法。简单地说，早时间是“从前向后”的方法求的，而晚时间是“从后向前”的方法求解的，并且，要想求晚时间必须是在所有的早时间都已经求出来之后才能进行。 熟练掌握求解的过程和步骤。关键路径问题是工程进度控制的重要方法，具有很强的 实用性。理解“减少关键活动时间可以缩短工期”是指该活动为所有关键路径所共有， 且减少到尚未改变关键路径的前提下有效。
　　7. 短路径问题也是为图一章的难点问题。短路径问题分为两种：一是求从某一点出发到其余各点的短路径;二是求图中每一对顶点之间的短路径。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。掌握这两个算法，并能手工熟练模拟。掌握用求短路径问题来解决的应用问题(如旅游景点及旅游路线的选择问题)
         更多考研常识相关内容尽在四川中公考研专硕栏目，中公考研为广大学子推出乐学面授课、VIP一对一等系列备考课程，针对每一个科目要点进行深入的指导分析，欢迎各位考生了解咨询。同时，中公考研一直为大家推出考研直播课堂，足不出户就可以边听课边学习，为大家的考研梦想助力！