升研教育考研频道为23考研、24考研的同学们整理了“计算机考研备考资料：数据结构（图②）”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

计算机考研专业课一般涉及到四个科目：数据结构、计算机组成原理、操作系统、计算机网络 ，知识点繁多，复习起来也并不失分容易，为了帮助大家复习，本篇为大家整理了一些数据结构中的知识点，供大家参考。

图

1、图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次。这一过程称为图的遍历。有两种基本方法:深度优先搜索和广度优先搜索。

深度优先搜索：从图中某个顶点v_i出发，访问出发点V_i，然后任选一个V_i的未访问过的邻接点v_j，以v_j为新的出发点继续进行深度优先搜索，直到图中所有顶点都被访问过。算法如下:

Dfs (GraphTp g , int v)

/*图g的存储结构为邻接表，进行深度优先搜索，数组visited的所有元素初始化为0*/

广度优先搜索：从图中某个顶点v_i出发，在访问了v_i之后依次访问v_i的所有邻接点，然后分别从这些邻接点出发广度优先搜索遍历图的其它顶点，直至所有顶点都被访问过。算法如下:

Bfs (GraphTp g , int v)

/*图g的存储结构为邻接表，进行广度优先搜索，数组visi ted的所有元素初始化为0*/ 

2、最小生成树：一个图的最小生成树是该图所有生成树中权最小的生成树。n个顶点无向图的最小生成树有n个顶点和n-1条边。如下图中右图是左图的最小生成树。

3、拓扑排序:设G=(V,E)是一个具有n个顶点的有向图，V中顶点的序列V₁, V₂, .. V_n称为一个拓扑序列, 

当且仅当该顶点序列满足下列条件:若在有向图G中，从顶点V_i到V_j有一条路径，则在序列中顶点V_i必排在顶点V_j之前。找一个有向图拓扑序列的过程称为拓扑排序。

拓扑排序的基本步骤如下:

①从图中选一个入度为0的顶点，输出该顶点;

②从图中删除该项点及其相关联的弧;

③重复①、②，直到所有顶点均被输出。