第六章：图 (Graphs)
学习内容
图是一种非线性数据结构，由节点（顶点）和边组成，是表示对象之间关系的重要工具。
图的基本概念
#### 图的定义
图 G 由两个集合组成：顶点集 V 和边集 E，表示为 G = (V, E)
#### 图的分类
1. 有向图：边有方向性
2. 无向图：边没有方向性
3. 有权图：边或顶点有权值
4. 无权图：边或顶点没有权值
#### 图的表示方法
1. 邻接矩阵：使用二维数组表示顶点间的关系
2. 邻接表：使用链表数组表示每个顶点的邻接顶点
图的遍历
#### 深度优先搜索（DFS）
- 从起始顶点开始，沿着一条路径尽可能深入
- 到达叶子节点后回溯，继续探索其他路径
- 可用于检测环、拓扑排序等
#### 广度优先搜索（BFS）
- 从起始顶点开始，逐层向外扩展
- 使用队列维护待访问的顶点
- 可用于求最短路径、层序遍历等
图的相关算法
#### 拓扑排序
- 对有向无环图（DAG）的顶点进行排序
- 使得对于任何有向边 (u, v)，u 在排序中都出现在 v 之前
#### 最短路径
- Dijkstra算法：单源最短路径（非负权边）
- Floyd算法：多源最短路径
#### 最小生成树
- Kruskal算法：基于边的贪心算法
- Prim算法：基于顶点的贪心算法
重点和难点
重点
1. 理解图的基本概念和表示方法
2. 掌握图的遍历算法：DFS 和 BFS
3. 理解图在实际问题中的应用
难点
1. 图的存储结构选择
2. 复杂图算法的实现
3. 图算法的时间复杂度分析
练习题
图的遍历
1. 课程表 (Course Schedule)
- 题目：你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1。在选修某些课程之前需要一些先修课程。请你判断是否可能完成所有课程的学习。
- 解题思路：构建有向图，检测图中是否存在环。可以使用拓扑排序或DFS检测环。
- 注意点：注意处理边界情况，如没有依赖关系的情况。
2. 岛屿数量 (Number of Islands)
- 题目：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算其中岛屿的数量。
- 解题思路：遍历网格，遇到陆地时使用DFS或BFS将相连的陆地标记为已访问。
- 注意点：注意边界处理和访问标记，避免重复计算。
图的算法
1. 课程表 II (Course Schedule II)
- 题目：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。返回你为了学完所有课程所安排的学习顺序。
- 解题思路：使用拓扑排序，BFS实现Kahn算法或DFS实现基于完成时间的排序。
- 注意点：注意处理无法完成所有课程的情况。
2. 冗余连接 (Redundant Connection)
- 题目：树可以看成是一个连通且无环的无向图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。找到一条可以删去的边，删除后可使得剩余部分是一棵树。
- 解题思路：使用并查集检测环，遍历边集，当两个顶点已在同一集合时，该边为冗余边。
- 注意点：注意并查集的路径压缩和按秩合并优化。
解题思路总结
DFS vs BFS 在图中的应用
- DFS：适用于路径问题、回溯问题、连通性问题
- BFS：适用于最短路径问题、层序遍历问题
图的存储结构选择
- 邻接矩阵：适合稠密图，查询边方便，空间复杂度 O(V²)
- 邻接表：适合稀疏图，节省空间，空间复杂度 O(V+E)
常见图算法应用场景
- 拓扑排序：任务调度、依赖关系处理
- 最短路径：导航系统、网络路由
- 最小生成树：网络设计、电路设计
学习时间
建议学习时间：1天
- 图的基础知识和遍历：1小时
- 图的算法：1小时
- 练习题：1小时