总结
图这一章的术语密度是全书最高的:邻接矩阵与邻接表决定了存储方式,DFS 与 BFS 决定了遍历方式,最小生成树、最短路径与拓扑排序则是三类经典问题。术语对照表把中英文说法对齐,核心要点给出必须记住的度数关系与遍历复杂度,建议在做完本章习题后再回来看这份总结。
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 图 | Graph | 顶点集与边集的集合 |
| 有向图 | Directed Graph | 边有方向 |
| 无向图 | Undirected Graph | 边无方向 |
| 邻接矩阵 | Adjacency Matrix | 二维数组存储 |
| 邻接表 | Adjacency List | 链表存储邻接点 |
| 深度优先搜索 | DFS | 用递归/栈,纵深优先 |
| 广度优先搜索 | BFS | 用队列,按层访问 |
| 最小生成树 | MST | 权值和最小的生成树 |
| 最短路径 | Shortest Path | 两顶点间最短路径 |
| 拓扑排序 | Topological Sort | DAG 顶点的线性排序 |
| 关键路径 | Critical Path | 最长路径,决定工期 |
- 无向图度数之和 = 2e;有向图入度之和 = 出度之和 = e
- BFS 用队列、DFS 用递归/栈,复杂度均 O(n+e)(邻接表)
- Prim 适合稠密图,Kruskal 适合稀疏图
- Dijkstra 单源且非负权,Floyd 多源允许负权
- 拓扑排序输出的顶点数小于 n,说明存在环
