图的表示与遍历
图是面试中最复杂的数据结构之一。但只要理解BFS 是"一圈一圈"地扩展，DFS 是"一条路走到黑"，就能应对大多数问题。
面试考察点
面试官通过这道题想考察：
1. 你是否理解图的三种表示方法及适用场景
2. 你是否理解 BFS 和 DFS 的本质区别
3. 你是否能用 BFS/DFS 解决实际问题
4. 你是否理解拓扑排序和环检测的原理
一、图的基础概念
1.1 什么是图？（小白解释）
图 = 顶点 + 边
现实中的"图"：
- 社交网络：人是顶点，"关注"是边
- 地图：城市是顶点，公路是边
- 网页：页面是顶点，链接是边
图的分类：
1. 有向图 vs 无向图
- 有向：边有方向，像单向车道
- 无向：边没有方向，像双向车道
2. 加权图 vs 非加权图
- 加权：边有权重（距离、费用等）
- 非加权：边没有权重
3. 有环 vs 无环
- 有环：可以走回起点
- 无环：像树结构
1.2 图的表示方法（面试必问）
面试官追问："图怎么存储？邻接矩阵和邻接表各有什么优缺点？"
方法1：邻接矩阵
用二维数组表示：
matrix[i][j] = 1 表示 i → j 有边
优点：
- 检查两个顶点是否有边：O(1)
- 实现简单
缺点：
- 空间复杂度 O(V²)，V 是顶点数
- 如果图很稀疏（边很少），浪费大量空间
示例（无向图）：
A B C D
┌────────────┐
A │ 0 1 1 0 │
B │ 1 0 0 1 │
C │ 1 0 0 1 │
D │ 0 1 1 0 │
└────────────┘
A 连接 B 和 C，D 连接 B 和 C
方法2：邻接表
每个顶点维护一个列表，存储它连接的所有顶点。
优点：
- 空间复杂度 O(V + E)，E 是边数
- 稀疏图很节省空间
- 遍历一个顶点的邻居很方便
缺点：
- 检查两个顶点是否有边需要遍历列表
示例（无向图）：
A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]
面试回答：通常用邻接表，因为大多数图是稀疏的！
二、BFS 和 DFS 的本质
2.1 BFS - 广度优先搜索（层层扩展）
面试官追问："BFS 为什么用队列？"
BFS 的核心思想：一圈一圈地扩展
想象向湖里扔一块石头：
涟漪一圈一圈扩散
○○○○○○○
○○○ ○○○
○○ ● ○○ ← 中心是起点
○○○ ○○○
○○○○○○○
先访问距离为 1 的点
再访问距离为 2 的点
...
怎么做到？用队列！
1. 把起点加入队列
2. 取出队首，访问它
3. 把它的邻居（未访问的）加入队列
4. 重复...
这不就是队列的先进先出吗？
先加入的邻居会先被访问 = 层层扩展！
BFS 图解：
图： BFS 从 A 开始：
A A
/|\ (第0层)
B C D B C D
|/ | (第1层)
E F E F
(第2层)
访问顺序：A → B → C → D → E → F
2.2 DFS - 深度优先搜索（一条路走到黑）
面试官追问："DFS 为什么用栈（或递归）？"
DFS 的核心思想：一条路走到黑，走不通就回退
想象走迷宫：
1. 从一个路口出发，随便选一条路
2. 走到下一个路口，再随便选一条（没走过的）
3. 如果走到死路（没有未访问的邻居），就退回上一个路口
4. 重复...
这不就是栈的特性吗？
LIFO = 最深走过的点先回退！
用递归实现：递归本身就是用调用栈
用迭代实现：手动用一个栈
DFS 图解：
图： DFS 从 A 开始：
A A
/|\ A → B → E
B C D (一条路走到黑)
|/ | 然后回退，继续
E F A → C → F
最后 D
访问顺序：A → B → E → C → F → D
（取决于选择顺序，可能不同）
三、BFS 和 DFS 的对比
3.1 核心区别
┌─────────────────────────────────────────────────┐
│ BFS vs DFS │
├─────────────────────────────────────────────────┤
│ │
│ BFS DFS │
│ ───────────────── ───────────────── │
│ 队列实现 (FIFO) 栈/递归实现 (LIFO) │
│ │
│ 一圈一圈扩展 一条路走到黑 │
│ │
│ 找最短路径 ✓ 不保证最短路径 │
│ │
│ 空间 = O(宽度) 空间 = O(深度) │
│ │
│ 适合：最短路、层级遍历 适合：连通分量、环检测 │
│ │
└─────────────────────────────────────────────────┘
3.2 什么时候用 BFS？什么时候用 DFS？
用 BFS：
1. 找最短路径（无权图）
2. 按层级遍历树
3. 找到某个解，且想找最近的解
4. 拓扑排序（BFS 版）
用 DFS：
1. 检测环
2. 拓扑排序（DFS 版）
3. 找连通分量
4. 回溯类问题（排列组合）
5. 路径搜索（不关心最短）
四、面试真题讲解
4.1 岛屿数量（LeetCode 200）
考察点：BFS/DFS 解决连通分量问题
问题：二维网格中，'1' 是陆地，'0' 是水。
问有多少个岛屿（相邻陆地的连通分量）？
grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
思路：
遍历每个格子，如果是 '1' 且未访问：
1. 用 BFS/DFS 把这片陆地全部标记为已访问
2. 岛屿数 +1
为什么对？
因为 BFS/DFS 能遍历一个连通分量！
每个连通分量就是一个岛屿！
4.2 课程表（LeetCode 207）- 环检测
考察点：DFS 检测环
问题：课程有先修关系，判断能否完成所有课程
示例：
2 门课，0 先修 1
prerequisites = [[1, 0]]，可以完成
如果有环呢？
prerequisites = [[1,0], [0,1]]
0 先修 1，1 先修 0，死循环！
怎么检测环？
用 DFS！
遍历图，如果 DFS 过程中遇到正在访问的节点 → 有环！
（正在访问 = 这个节点还在当前递归栈中）
五、面试总结
图的遍历核心
BFS = 队列 = 层层扩展 = 最短路径
DFS = 栈/递归 = 一条路走到黑 = 回溯
两者都是 O(V + E) 时间复杂度
V = 顶点数，E = 边数
面试能加分的回答
1. 能解释为什么用队列/栈
"队列先进先出 = 层层扩展 = BFS"
"栈先进后出 = 走到黑 = DFS"
2. 能分析时间和空间复杂度
"O(V + E)，V 个顶点，E 条边都要访问"
3. 能选择合适的数据结构
"稀疏图用邻接表，稠密图用邻接矩阵"
相关题目
- LeetCode 200 - 岛屿数量 - BFS/DFS
- LeetCode 207 - 课程表 - 环检测
- LeetCode 417 - 太平洋大西洋水流问题 - 多源 BFS