5.1 考点归纳与考点分析

5.1 考点归纳与考点分析

　　图是一种复杂的非线性数据结构，在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构都有着广泛的应用。图是数据结构的一个常考点，主要考查图的概念、图的存储、图的深度优先遍历（搜索）和广度优先遍历（搜索）、图的基本应用及其算法的复杂度。本章中的考点情况如表5-1所示。

表5-1 图的考点情况

　　（1）图的定义。理解图的概念，理解图的各种分类的概念，比如有向图、无向图、强连通图等。
　　（2）图的存储及基本操作。理解图的邻接矩阵存储和邻接表存储，理解这两种存储方法的操作，并能够分析两种存储方法的异同和优缺点。
　　（3）图的遍历。理解图的深度优先搜索和广度优先搜索方法，并能够通过栈、队列和函数递归等方法实现。
　　（4）图的基本应用及其复杂度分析。理解最小（代价）生成树的概念和生成算法，理解最短路径的概念和获取最短路径的算法，理解拓扑排序的概念和实际应用，理解关键路径的概念，并且能够提取关键路径。