您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 2020计算机职业考研数据结构知识点：图

2020计算机职业考研数据结构知识点：图

发布日期：2019-06-12 20:40:14 来源：四川中公考研

2020考研择校择职业指导群

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

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

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

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

免责声明：本站所提供的内容均来源于网友提供或网络搜集，由本站编辑整理，仅供个人研究、交流学习使用，不涉及商业盈利目的。如涉及版权问题，请联系本站管理员予以更改或删除。

【责任编辑：白红梅】

上一篇： 2020计算机职业考研数据结构知识点：二叉树

下一篇： 2020计算机职业考研数据结构知识点：排序

预约报名流程

考研指导图书

热点推荐

中公考研课堂

公共课
|专业课

课程系列	班次名称	价格	免费试听
考研政治网络课堂	2022考研政治+英语提升课程	咨询	免费试听
考研政治网络课堂	考研政治主观题答题技巧班	咨询	免费试听
考研英语网络课堂	2022考研政英数提升课程	咨询	免费试听
考研英语网络课堂	2022考研英语备考指导课	咨询	免费试听
考研数学网络课堂	2022考研数学备考指导课	咨询	免费试听
	2022考研数学（二）	咨询	免费试听
	2022考研数学（三）	咨询	免费试听
22专业课精品班	2022考研英语核心词汇精讲	咨询	免费试听
	9天突破英语核心1000词	咨询	免费试听
	2022考研管综备考指导课	咨询	免费试听

课程系列	班次名称	价格	免费试听
经济学精品班	2021考研经济学	咨询	免费试听
教育学精品班	经济学（初级）考研入门课	咨询	免费试听
教育学精品班	经济学（中级）考研入门课	咨询	免费试听
法学精品班	法律硕士（非法学）考研入门课	咨询	免费试听
法学精品班	2022考研法律硕士	咨询	免费试听
管理学精品班	管理学考研入门课	咨询	免费试听
管理学精品班	考研管理学全科精讲	咨询	免费试听

2022考研乐学先锋

乐学先锋；实战式教学；陪伴式督学；考研轻松学；提供差异化考研辅导。GO>

冲刺集训

浓缩高精考点易学不累、串讲模考点晴721配比、实战教学一切为效率服务GO>

您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 2020计算机职业考研数据结构知识点：图

2020计算机职业考研数据结构知识点：图

推荐阅读

热点推荐

中公考研课堂

2021年考研工具箱

研友互动

报考信息

备考指导

快速查询

招考信息

备考资料

复试调剂

四川中公考研

四川考研中公资讯

四川中公考研互动平台