六、图

本章导览

共 6 个小节：图的基本概念、图的存储表示、图的基本操作、图的遍历、图的应用、图的应用

本章重点

• 图 G=(V,E)，多对多网状关系
• 存储：邻接矩阵（稠密）/ 邻接表（稀疏）；遍历：BFS（队列）/ DFS（栈）
• 最短路径 Dijkstra/Floyd；最小生成树 Prim/Kruskal；拓扑排序 / 关键路径

图的基本概念

关键点

• 顶点 + 边，分有向 / 无向；度（有向分入度、出度）、连通 / 强连通
• 邻接矩阵判相邻 O(1)、空间 O(n²)；邻接表省空间 O(n+e)

图的存储表示

关键点

• 邻接矩阵：判相邻 / 取边权 O(1)，宜稠密图
• 邻接表：空间 O(n+e)，宜稀疏图
• 十字链表（有向）、邻接多重表（无向）

邻接矩阵

关键点

空间复杂度：$O(|V|^2)$——只和顶点数相关，和实际的边数无关，适合用于存储稠密图。 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）。

邻接表

十字链表

邻接多重表

图的基本操作

关键点

• 同一操作在不同存储下代价不同
• 口诀：问「是否相邻 / 取边权」用邻接矩阵，问「遍历邻居」用邻接表

图的遍历

关键点

• BFS：逐层扩展、用队列，求无权图最短路
• DFS：钻到底回溯、用栈 / 递归
• 一次遍历的可达顶点 = 一个连通分量

广度优先算法（BFS）

深度优先算法（DFS）

图的遍历与图的连通

图的应用

关键点

• 最小生成树：Prim（顶点扩展，宜稠密）、Kruskal（选边 + 并查集，宜稀疏）
• 最短路径：Dijkstra（无负权）、Floyd（多源 O(n³)）

图的应用

关键点

• 拓扑排序（AOV）：反复删入度为 0 的顶点，判能否进行
• 关键路径（AOE）：最长路径定工期
• 口诀：拓扑看顺序，关键看工期

最小生成树

关键点

（1）Prim 算法（普利姆） （2）Kruskal 算法（克鲁斯卡尔） Prim 算法 V.S. Kruskal 算法

最短路径问题

关键点

单源最短路径——BFS 算法（无权图） 单源最短路径——Dijkstra 算法（带权图、无权图） 各顶点间的最短距离——Floyd 算法（带权图、无权图）

有向无环图描述表达式

拓扑排序

关键路径