计算机#2021计算机考研究生#<图>的有关知识

类目：三人行考研网>计算机>正文

时间：2020-05-1311:19:57

为了帮助计算机考研的同学更好地复习，切实地利用好基础复习这个考研过程中关键的时间点 ，三人行考研网小编整理分享“2021计算机考研：“图”的有关知识 ”相关内容
，一起来看看吧。

图：

在数据结构中，图的结构是最复杂的 ，这里的概念也是最多的 。我们要掌握图的基本概念(有向图、无向图 、连通
、路径、子图 、出度
、入度、生成树 、最短路径
、关键路径等)
。

图的存储及基本操作主要有邻接矩阵法和邻接表法
，我们要掌握这有向图和无向图的这2种存储方法，要清楚图的连通和存储方法之间的关系。例如 ，一个顶点的出度和临界矩阵中1的个数有什么关系
，等等 。

图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这2种遍历方法的算法实现
。给出一个具体的图 ，要能知道它的遍历次序。

在数据结构课程中，图的基本应用是最多的
，也是最复杂的，我们要掌握这些应用的复杂度分析 。要掌握的具体应用主要包括最小(代价)生成树、最短路径 、拓扑排序、关键路径
。在给出的一个具体的图中 ，我们要会利用已知条件
，求出上述应用的结果。