根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
四、图的基本应用
1.概念
①将没有回路的连通图定义为树称自由树。
②生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。
3最小生成树：连通网G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。将生成树的各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树。
2.最短路径
路径的开始顶点称源点，路径的最后一个顶点称终点。
3.拓扑排序
3.1概念
AOV网：顶点表示活动，弧表示活动间的优先关系的有向图。
在无回路的AOV网中，所有的活动可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前边，称此序列为拓扑序列，由AOV网构成拓扑序列的过程称为拓扑排序。
3.2拓扑排序算法思想
选择有向图中入度为0的顶点输出，并从图中删去该点相邻弧;
重复上述操作，直到图中全部顶点均被输出或图中已不存在入度为0的顶点(有回路)。