图
图
1. 基本概念
- 图：由顶点集和边集组成，可分为有向图、无向图
- 邻接、度、连通、权、路径、回路、连通分量
2. 存储结构
- 邻接矩阵：二维数组，适合稠密图
- 邻接表：数组+链表，适合稀疏图
- 邻接多重表、十字链表：适合复杂图
3. 遍历
- 深度优先搜索（DFS）：递归/栈实现，优先走深
- 广度优先搜索（BFS）：队列实现，优先走广
4. 基本应用
- 最小生成树（Prim、Kruskal 算法）
- 最短路径（Dijkstra、Floyd 算法）
- 拓扑排序：有向无环图
- 关键路径：AOV 网，项目管理
习题
习题 1
简述图的基本概念及常见术语。
答案与解析
图由顶点和边组成，有向/无向、邻接、度、连通、权、路径、回路等
习题 2
邻接矩阵和邻接表各自的优缺点是什么？
答案与解析
邻接矩阵：适合稠密图，空间大，查找快；邻接表：适合稀疏图，空间省，查找慢
习题 3
DFS 和 BFS 的基本思想和实现方式是什么？
答案与解析
DFS 递归/栈，优先走深；BFS 队列，优先走广
习题 4
最小生成树和最短路径的常用算法有哪些？
答案与解析
最小生成树：Prim、Kruskal；最短路径：Dijkstra、Floyd
习题 5
拓扑排序的应用场景是什么？
答案与解析
有向无环图的任务调度、课程安排、项目管理等
考研真题
真题 1
【2022·408】下列关于图的说法中，错误的是（ ） (A) 无向图中所有顶点的度数之和等于边数的 2 倍 (B) 有向图中所有顶点的入度之和等于所有顶点的出度之和 (C) 具有 n 个顶点的无向完全图有 n(n-1)/2 条边 (D) 具有 n 个顶点的有向完全图有 n(n-1)/2 条边
答案与解析
(D) 错误。具有n个顶点的有向完全图有n(n-1)条边，因为每对顶点之间有两条方向相反的边。
真题 2
【2020·408】已知一个有向无环图的拓扑序列是唯一的，则此图一定是（ ） (A) 强连通图 (B) 有向完全图 (C) 有向树 (D) 有向链
答案与解析
(D) 有向链。拓扑序列唯一意味着图中任意两个顶点之间都有明确的先后关系，只有有向链（即所有顶点形成一条链）才能满足这个条件。