04. 图

图

1. 基本概念

• 图：由顶点集和边集组成，可分为有向图、无向图
• 邻接、度、连通、权、路径、回路、连通分量

2. 存储结构

• 邻接矩阵：二维数组，适合稠密图
• 邻接表：数组+链表，适合稀疏图
• 邻接多重表、十字链表：适合复杂图

3. 遍历

• 深度优先搜索（DFS）：递归/栈实现，优先走深
• 广度优先搜索（BFS）：队列实现，优先走广

4. 基本应用

• 最小生成树（Prim、Kruskal 算法）
• 最短路径（Dijkstra、Floyd 算法）
• 拓扑排序：有向无环图
• 关键路径：AOV 网，项目管理

练习题

1. 简述图的基本概念及常见术语。
2. 邻接矩阵和邻接表各自的优缺点是什么？
3. DFS 和 BFS 的基本思想和实现方式是什么？
4. 最小生成树和最短路径的常用算法有哪些？
5. 拓扑排序的应用场景是什么？