考研数据结构：图论核心刷题集

"考研数据结构第七章-图论必刷题，包含42道历年名校考研真题，涵盖选择题、填空题和应用大题，全面覆盖图论知识点。" 在数据结构的学习中，图论是至关重要的一部分，特别是在考研复习阶段。本资源提供的42道题目的内容涉及了图的基本概念、性质以及各种操作。以下是根据题目内容总结的一些关键知识点： 1. **图的定义**：图是由顶点和边组成的集合，边可以连接两个顶点，形成路径。选择题中的选项A正确地描述了这一点。 2. **图的边数与顶点数的关系**：对于无向图，其边数的最大值是顶点数的平方减去顶点数除以2，即B选项n(n-1)/2；对于有向图，如果图是完全图，边数为n(n-1)，即每个顶点到其他每个顶点都有一条边。 3. **连通图的概念**：一个连通图意味着图中的任意两个顶点都通过边可以直接或间接相连。对于无向图，至少需要n-1条边才能保证连通；对于有向图，同样需要n-1条边才能连通所有顶点。 4. **完全图**：如果图中任意两个不同的顶点之间都有一条边，那么这个图被称为完全图。对于n个顶点的完全有向图，边数为n(n-1)，对应D选项。 5. **连通分量**：在图中，连通分量是指图中的最大子图，其中任意两个顶点都是连通的。对于有向图，最少有一个连通分量（当图是强连通图时），最多n个连通分量（每个顶点都是独立的分量）。 6. **度数与边数关系**：在无向图中，所有顶点的度数之和等于边数的两倍，因为每条边贡献了两个度数。在有向图中，所有顶点的入度之和等于出度之和，体现了一条边的起点和终点的度数平衡。 7. **有向无环图(DAG)的拓扑排序**：DFS遍历DAG并退栈返回时，得到的顶点序列是拓扑有序的，即不存在边(a, b)使得a在b之后出现。 8. **图的存储结构**：表示稀疏图（边数远小于顶点数的平方）时，邻接表和逆邻接表更为高效；邻接矩阵适用于稠密图。而邻接多重表和十字链表可以表示无向图和有向图，但不适用于特定的稀疏图情况。 9. **邻接矩阵的性质**：无向图的邻接矩阵是对称的，因为每条边在矩阵中表示为两个对称的非零元素。 10. **图的性质**：AOV网（Activity On Vertex，顶点上的活动）表示的图是无向的，而AOE网（Activity On Edge，边上的活动）表示的图是有向的，且通常包含权重。 通过解答这些题目，考生可以深入理解图的基本概念，掌握图的性质，以及如何利用图来解决实际问题。这些题目覆盖了图的生成树、拓扑排序、最短路径等问题，是备考数据结构和图论的重要实践练习。