您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 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计算机职业考研数据结构知识点：排序

10秒智能择校

查看历年试题

热点推荐

备考福利站

公共课
|专业课

课程系列	班次名称	价格	免费开通
考研政治网络课堂	2026政治考研备考指导课	39	免费开通
考研政治网络课堂	考研政治五年试题精讲	199	免费开通
考研英语网络课堂	2026考研英语备考指导课	39	免费开通
考研英语网络课堂	考研英语（一、二）五年试题精讲	199	免费开通
考研数学网络课堂	2026考研数学备考指导课	39	免费开通
	考研数学五年试题精讲	199	免费开通
	考研数学常用公式整理	39	免费开通
23专业课精品课	311教育学考研入门课	11	免费开通
	333教育综合考研入门课	11	免费开通
	法律硕士（非法学）考研入门课	11	更多课程

课程系列	班次名称	价格	免费开通
经济学精品班	金融学考研入门课	咨询	免费开通
教育学精品班	经济学（初级）考研入门课	19	免费开通
教育学精品班	经济学（中级）考研入门课	19	免费开通
法学精品班	法律硕士（非法学）考研入门课	19	免费开通
法学精品班	13大热门专业课备考抢学包	19	免费开通
管理学精品班	管理学考研入门课	19	免费开通
管理学精品班	社会工作考研入门课	19	免费开通