2022年的小伙伴们正在积极备考，大多数考生对计算机综合（408）考研知识点都感到很茫然。研学长为大家按照2020年考研大纲的考察目标对计算机综合（408）考研知识点进行了系统化的整合。下面，各位考生就跟着研学长一起了解一下“考研知识点-计算机综合（408）数据结构-图”，希望能给各位考生带来帮助。
在这一章中需要识记的是图以及基于图的各种定义，存储方式。要熟练掌握图的深度遍历和广度遍历算法，这是用图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法，能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象， 会成为下列问题：最小生成树求解(PRIM算法和KRUSKAL算法， 两种方法思想都很简单， 但注意不要混淆这两种方法)，拓扑排序问题(这里会用到数组实现的链表，可以注意一下)，关键路径问题((数据结构的较大难点，要把概念理解透，能做出表格找出关键路径)，最短路径问题(有重要的应用背景，也是贪心法不多的能给出解的典型问题之一)。
考研-计算机综合（408）-知识点01-图的基本概念
线性表可以是空表，树可以是空树，但图不可以是空图，就是说，图中不能一概顶点也没有，图的顶点集合一定非空。
顶点的度是指与顶点相目关联的边数，对于有向图，还要区分出度和入度。
连通性一般指的是无向图中的性质，而在有向图的情形要考虑的是强连通性。
图的生成树是由顶点和顶点之间关系组成的连通图。有n个顶点，必有n-1条边将它们连通。要注意的是，这种生成树不能是空树。
从非强连通的有向图图和非连通的无向图通过遍历得到的是生成森林。
不像线性表，元素之间有前驱后继关系；也不像树，结点之间有父子分层关系；在图中各个顶点之间的地位是平等的，因此可以按照需要对图中顶点重新编号。
在有向图中，每个顶点对(有向边)的顶点之间有前驱后继关系，称为前导一紧随关系，在用它描述“工程”计划时称为活动网络或前导图。
稀疏图的边数远远少于图的顶点数的平方，稠密图则不是。
考研-计算机综合（408）-知识点02-图的存储及基本操作
图的邻接矩阵是一个n×n的方阵，如果执行与每一个顶点有关的边的操作，需要检测每一行的矩阵元素，需要的时间代价为O(n²)；而如果在图的邻接表上做同样的与每一个顶点有关的边上的操作，所需时间代价为O(n+e)，其中n是图顶点个数，e是图的边数。
无向图中所有顶点的度加起来是边数的2倍，这是由于边的无向性造成的。
有向图中的矩阵元素A[i][j]，往往是指从顶点i到顶点j的有向边(弧)。统计第i行中1(或权值0
对于图中的边数远远小于顶点个数的平方的情形，邻接矩阵往往成为稀疏矩阵，此时改用邻接表较好。
有向图的邻接表要区分出边表(邻接表)和入边表(逆邻接表))。有时把这两个表结合起来形成十字链表，但这样可能会把问题的解决复杂化。
在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。
在无向图的邻接表中，每一条边(Vi，v；)在邻接表中有两个结点：一个在vi的边链表中，一个在vj的边链表中。在较复杂的问题中，有时需要给被处理的边加标记(如房屋标志或删除标志等)，以免重复处理。
在设计与图有关的算法时最好不要改动图中的原有数据，这样使得图可以复用。
考研-计算机综合（408）-知识点02-图的遍历
深度优先遍历：
遍历时，对图的每个顶点至多调用一次DFS函数。其实质就是是对每个顶点查找邻接顶点的过程，取决于存储结构。邻接矩阵表示方法，查找每个顶点的复杂度为O(n²)以邻接表为存储结构，当图有e条边，其时间复杂度为O(e)，总时间复杂度为O(n+e)。
广度优先遍历：
用广度优先搜索算法遍历图与深度优先搜索算法遍历图的区别是邻接点搜索次序不同；因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e)。需要注意的是，一个给定的图的邻接矩阵表示是的，但对于邻接表来说，如果边的输入先后次序不同，生成的邻接表表示也不同。因此，对于同样一个图，基于邻接矩阵表示的遍历所得到的DFS序列或BFS序列是的， 基于邻接表表示的遍历所得到的DFS序列或BFS序列可以是不的。
考研-计算机综合（408）-知识点03-图的基本应用
（一）最小（代价）生成树
对于一个连通网络(即连通带权图)，生成树不同，每棵树的权(即树中所有边上的权值总和)也可能不同。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。因此，构造最小代价生成树的准则有三条：
必须只是用该网络中的边来构造最小代价生成树；
必须使用且仅使用n-1条边来连接网络中的n个顶点；
不能使用产生回路的边。
以上就是研学长整理的“考研知识点-计算机综合（408）数据结构-图”，希望能给各位考生带来帮助。心专注研学长公众号，回复“真题”，更多考研信息尽在研学长考研网公众号！
