图数据结构 - 完整指南与 DFS & BFS 遍历

什么是图？

**图（Graph）**是一种基本的数据结构，由以下部分组成：

• 顶点（Vertices/Nodes）：图中的实体或节点
• 边（Edges）：顶点之间的连接

图用于建模关系、网络、层次结构和路径。它们在以下场景中必不可少：

• 社交网络连接（Facebook 好友）
• 道路网络和导航（Google Maps）
• 网页链接（Google PageRank）
• 依赖关系解析（npm 包）
• 推荐系统（Netflix、Amazon）

为什么面试官喜欢图？

图问题在 FAANG 面试中占 40-50%，因为它们考察：

1. 多种算法模式：DFS、BFS、最短路径、环检测
2. 数据结构设计：选择正确的表示方法
3. 复杂问题解决：真实世界应用
4. 代码组织：清晰的遍历逻辑

图的类型

有向图 vs 无向图

无向图:              有向图:
   A --- B              A ──> B
   |     |              |     ↑
   C --- D              └──> C

• 无向图：边没有方向（Facebook 好友关系）
• 有向图：边有方向（Twitter 关注）

带权图 vs 无权图

带权图:              无权图:
   A --5-- B            A --- B
   |       |            |     |
   3       2            C --- D
   |       |
   C --1-- D

• 带权图：边有权值（道路距离）
• 无权图：所有边相等（连接存在或不存在）

有环图 vs 无环图

有环图:              无环图 (DAG):
   A → B                A → B
   ↓   ↓                ↓   ↓
   C ← D                C → D

• 有环图：包含环
• 无环图：没有环（DAG = 有向无环图）

图的表示方法

表示图的两种主要方式：邻接表和邻接矩阵。

对比表格

特性	邻接表	邻接矩阵
空间复杂度	$O(V + E)$	$O(V^2)$
检查边	$O(\text{度数})$	$O(1)$
查找邻居	$O(\text{度数})$	$O(V)$
添加边	$O(1)$	$O(1)$
适用于	稀疏图	稠密图、快速边查询
面试使用	✅ 90% 的问题	少见（特定用例）

何时使用

使用邻接表，当：

• 图是稀疏的（边数少）：$E \ll V^2$
• 需要频繁遍历邻居
• 这是 90% 面试问题的默认选择

使用邻接矩阵，当：

• 图是稠密的：$E \approx V^2$
• 需要 $O(1)$ 边存在性检查
• 处理有很多操作的带权图
• 问题明确要求使用

邻接表实现

面试中最常用的表示方法！

JavaPythonJavaScript

Loading...

邻接表可视化

图的边: (0,1), (0,2), (1,3), (1,4), (2,4)

邻接表:
  0: [1, 2]
  1: [0, 3, 4]
  2: [0, 4]
  3: [1]
  4: [1, 2]

可视化:
    0
   / \
  1   2
 / \ /
3   4

邻接矩阵实现

较少使用，但对稠密图有用。

JavaPythonJavaScript

Loading...

邻接矩阵可视化

同上图:

邻接矩阵 (5×5):
     0  1  2  3  4
  0 [0, 1, 1, 0, 0]
  1 [1, 0, 0, 1, 1]
  2 [1, 0, 0, 0, 1]
  3 [0, 1, 0, 0, 0]
  4 [0, 1, 1, 0, 0]

1 表示边存在，0 表示无边
对于带权图，使用权重代替 1

图的深度优先搜索（DFS）

DFS 沿着每个分支尽可能深入地探索，然后回溯。

DFS 模式

1. 从一个节点开始
2. 标记为已访问
3. 递归访问未访问的邻居
4. 当没有未访问的邻居时回溯
5. 重复直到所有可达节点被访问

交互式 DFS 可视化

DFS Visualization

Hide Adj ListShow Matrix

Step 0 of 12Initialize DFS from node 0

Current

Visited

In Path

Adjacency List

0: [1, 2]

1: [0, 3, 4]

2: [0, 4]

3: [1, 5]

4: [1, 2, 5]

5: [3, 4]

Stack

[0]

Visited

{}

ResetPreviousNext

DFS 实现

JavaPythonJavaScript

Loading...

DFS 遍历示例

图:              从 0 开始的 DFS:
    0                访问: 0
   / \               访问: 1
  1   2              访问: 3
 /|   |              访问: 5
3 4   5              访问: 4
  |   |              访问: 2
   \-/

顺序: 0 → 1 → 3 → 5 → 4 → 2

栈状态:
0:  [0]
1:  [0, 1]      (进入 1)
2:  [0, 1, 3]   (进入 3)
3:  [0, 1]      (从 3 回溯)
4:  [0, 1, 4]   (进入 4)
5:  [0, 1, 4, 5] (进入 5)
6:  [0, 1, 4]   (从 5 回溯)
...

图的广度优先搜索（BFS）

BFS 在深入之前先探索当前深度的所有邻居。

BFS 模式

1. 从一个节点开始，加入队列
2. 当队列不为空时:
   a. 出队一个节点
   b. 标记为已访问
   c. 将所有未访问的邻居加入队列
3. 重复直到队列为空

交互式 BFS 可视化

BFS Visualization

Hide Adj ListShow Matrix

Step 0 of 12Initialize BFS from node 0

Current

Visited

In Path

Adjacency List

0: [1, 2]

1: [0, 3, 4]

2: [0, 4]

3: [1, 5]

4: [1, 2, 5]

5: [3, 4]

Queue

[0]

Visited

{0}

ResetPreviousNext

BFS 实现

JavaPythonJavaScript

Loading...

BFS 遍历示例

图:              从 0 开始的 BFS:
    0                第 0 层: 0
   / \               第 1 层: 1, 2
  1   2              第 2 层: 3, 4
 /|   |              第 3 层: 5
3 4   5
  |   |
   \-/

顺序: 0 → 1 → 2 → 3 → 4 → 5

队列状态:
0:  [0]
1:  [1, 2]      (出队 0，入队 1, 2)
2:  [2, 3, 4]   (出队 1，入队 3, 4)
3:  [3, 4]      (出队 2，4 已在队列)
4:  [4, 5]      (出队 3，入队 5)
5:  [5]         (出队 4，5 已在队列)
6:  []          (出队 5)

DFS vs BFS 对比

方面	DFS	BFS
数据结构	栈（递归或显式）	队列
顺序	深度优先	广度优先
空间复杂度	$O(H)$ (高度)	$O(W)$ (最大宽度)
时间复杂度	$O(V + E)$	$O(V + E)$
用途	路径、环、回溯	最短路径、层级
面试频率	⭐⭐⭐⭐⭐ 非常常见	⭐⭐⭐⭐⭐ 非常常见

常见图问题

问题一：岛屿数量 (LC 200)

问题：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的 2D 网格，计算岛屿数量。

模式：在隐式图（网格作为图）上进行 DFS/BFS

JavaPythonJavaScript

Loading...

复杂度：$O(M \times N)$ 时间，$O(M \times N)$ 空间（递归栈）

为什么时间复杂度是 O(M × N)？详细分析

乍一看，这可能有些令人困惑：

• 外层双重循环访问所有格子：$O(M \times N)$
• 每次 DFS 调用可能访问很多格子
• 这意味着 $O((M \times N)^2)$ 吗？不！ ❌

关键洞察：每个格子最多被访问一次！

正确的分析

1. 外层循环成本

for (int i = 0; i < M; i++) {           // M 次迭代
    for (int j = 0; j < N; j++) {       // N 次迭代
        if (grid[i][j] == '1') {
            dfs(grid, i, j);
        }
    }
}

这个循环访问所有 $M \times N$ 个格子：$O(M \times N)$

2. DFS 总调用次数（均摊分析）

关键是要分析整个执行过程中所有 DFS 调用的总次数：

private void dfs(char[][] grid, int i, int j) {
    if (grid[i][j] == '0') {
        return;  // ← 已访问，立即返回
    }
    
    grid[i][j] = '0'; // ← 标记为已访问（关键！）
    
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

关键观察：

• 当我们访问一个格子时，立即将其标记为 '0'
• 一旦标记，就永远不会再次访问
• 每个格子被 DFS 处理恰好一次

3. 具体示例

考虑一个 3×4 的网格（M=3，N=4）：

[
  ['1', '1', '0', '0'],
  ['1', '0', '0', '1'],
  ['0', '0', '1', '1']
]

执行跟踪：

步骤 1：扫描到 grid[0][0] = '1'
  → 调用 dfs(0,0)
  → DFS 访问：(0,0) → (0,1) → (1,0)
  → 全部标记为 '0'
  → 总计：访问了 3 个格子

步骤 2：继续扫描，grid[0][1] 现在是 '0'，跳过
步骤 3：继续扫描，grid[1][0] 现在是 '0'，跳过
步骤 4：扫描到 grid[1][3] = '1'
  → 调用 dfs(1,3)
  → DFS 访问：(1,3)
  → 标记为 '0'
  → 总计：访问了 1 个格子

步骤 5：扫描到 grid[2][2] = '1'
  → 调用 dfs(2,2)
  → DFS 访问：(2,2) → (2,3)
  → 标记为 '0'
  → 总计：访问了 2 个格子

统计数据：

• 外层循环迭代：12 个格子（3×4）
• DFS 总访问次数：3 + 1 + 2 = 6 个格子（恰好是所有 ‘1’ 的数量）
• 每个格子被 DFS 恰好访问一次

4. 时间复杂度公式

总时间 = 外层循环时间 + 所有 DFS 调用时间

外层循环：
  - 访问 M×N 个格子
  - 每次检查：O(1)
  - 总计：O(M×N)

所有 DFS 调用（整个执行过程）：
  - 每个格子最多访问一次
  - 每次访问：O(1) 工作（标记 + 4 次递归调用）
  - 总计：O(M×N)

总时间 = O(M×N) + O(M×N) = O(M×N)

为什么不是 $O((M \times N)^2)$？

❌ 错误想法：“每次 DFS 可能访问 $O(M \times N)$ 个格子，我们调用 DFS $M \times N$ 次”

✅ 正确想法：“虽然我们可能发起多次 DFS 调用，但所有 DFS 调用加起来每个格子最多访问一次”

类比：就像给数组涂色：

• 外层循环扫描所有元素：$O(N)$
• 当我们发现未涂色的元素时，给它和相邻的都涂色
• 多次”涂色操作”，但每个元素只涂色一次
• 总时间：$O(N)$，而不是 $O(N^2)$

空间复杂度：$O(M \times N)$（最坏情况）

最坏情况：整个网格都是 ‘1’（一个巨大的岛屿）

[
  ['1', '1', '1'],
  ['1', '1', '1'],
  ['1', '1', '1']
]

DFS 递归深度可能达到 $O(M \times N)$，形成从左上角到右下角的蛇形路径。

总结：

• ✅ 每个格子最多标记一次
• ✅ 标记后的格子永不再访问
• ✅ 均摊分析：所有 DFS 调用每个格子访问一次
• ✅ 线性时间，不是平方时间！

替代方案：BFS 解法

虽然 DFS 对这个问题很直观，但 BFS 同样可以完美解决，对某些人来说可能更容易理解。

关键区别：

• DFS：使用递归（隐式栈），深入探索一个岛屿
• BFS：使用显式队列，逐层探索岛屿

JavaPythonJavaScript

Loading...

BFS 执行示例：

网格：                   执行过程：
['1', '1', '0']         1. 在 (0,0) 找到 '1'，count=1
['1', '0', '0']         2. 从 (0,0) 开始 BFS：
['0', '0', '1']            队列：[(0,0)]
                           处理 (0,0)，标记为 '0'，添加邻居
                           队列：[(0,1), (1,0)]
                           处理 (0,1)，标记为 '0'
                           队列：[(1,0)]
                           处理 (1,0)，标记为 '0'
                           队列：[]  (BFS 完成)
                        3. 继续扫描...
                        4. 在 (2,2) 找到 '1'，count=2
                        5. 从 (2,2) 开始 BFS：
                           队列：[(2,2)]
                           处理 (2,2)，标记为 '0'
                           队列：[]  (BFS 完成)
                        
结果：2 个岛屿

岛屿数量问题：DFS vs BFS 对比：

方面	DFS	BFS
实现难度	更简单（递归）	稍复杂（需要队列）
内存占用	$O(M \times N)$ 最坏情况（递归）	$O(\min(M, N))$ 典型情况
遍历顺序	深入探索（曲折）	逐层扩展
栈溢出风险	有（超大网格）	无
面试偏好	⭐⭐⭐⭐⭐ 更常见	⭐⭐⭐⭐ 也很好

何时使用 BFS：

• 大型网格，DFS 可能导致栈溢出
• 需要找到最短路径（虽然此题不需要）
• 更倾向于迭代解法而非递归

何时使用 DFS：

• 更简单的实现
• 递归对问题更自然
• 网格大小合理（< 1000×1000）

两者时间复杂度相同：$O(M \times N)$

BFS 关键要点：

• 在添加到队列时立即标记为已访问（不是在处理时）
• 这防止同一格子被多次添加到队列
• 如果不这样做，一个格子可能被添加 4 次（从 4 个邻居）！

问题二：克隆图 (LC 133)

问题：深拷贝一个无向图。

模式：DFS/BFS 配合哈希表追踪克隆

JavaPythonJavaScript

Loading...

复杂度：$O(V + E)$ 时间，$O(V)$ 空间

问题三：课程表 (LC 207)

问题：检测课程是否可以完成（有向图中的环检测）。

模式：DFS 环检测或拓扑排序

JavaPythonJavaScript

Loading...

复杂度：$O(V + E)$ 时间，$O(V)$ 空间

时间和空间复杂度总结

表示方法

操作	邻接表	邻接矩阵
空间	$O(V + E)$	$O(V^2)$
检查边	$O(\text{度数})$	$O(1)$
查找邻居	$O(\text{度数})$	$O(V)$
添加边	$O(1)$	$O(1)$

遍历算法

算法	时间	空间	最适合
DFS	$O(V + E)$	$O(H)$	路径、环、连通性
BFS	$O(V + E)$	$O(W)$	最短路径、层级

其中：

• $V$ = 顶点数量
• $E$ = 边数量
• $H$ = 图的高度（DFS 栈深度）
• $W$ = 最大宽度（BFS 队列中的最大节点数）

面试技巧与常见错误

✅ 最佳实践

1. 始终明确图的类型：

   • 有向还是无向？
   • 带权还是无权？
   • 可能有环吗？

2. 选择正确的表示方法：

   • 默认使用邻接表（90% 的情况）
   • 只有明确有益时才使用矩阵

3. DFS vs BFS 决策：

   • 使用 BFS 进行最短路径、层序遍历
   • 使用 DFS 进行路径、环、回溯

4. 追踪已访问节点：

   • 使用 Set<Integer> 或 boolean[]
   • 在加入队列之前标记为已访问（BFS）
   • 进入节点时标记为已访问（DFS）

❌ 常见错误

1. 忘记标记节点为已访问 → 无限循环
2. BFS 中标记已访问太晚 → 节点被多次添加
3. 不处理不连通的组件 → 遗漏图的部分
4. 使用错误的表示方法 → 低效解决方案
5. 不检查空/空图 → 运行时错误

面试策略

当你看到图问题时：

1. 明确：有向？带权？有环？
2. 选择表示方法（通常是邻接表）
3. 识别模式：
   - 连通性 → DFS
   - 最短路径 → BFS
   - 环检测 → 带状态的 DFS
   - 拓扑排序 → DFS 或 BFS (Kahn 算法)
4. 实现并追踪已访问
5. 测试边界情况：空、单节点、不连通

常见图模式

模式 1：图遍历

使用时机：需要访问所有节点、检查连通性 使用方法：DFS 或 BFS 示例：岛屿数量、连通分量

模式 2：最短路径

使用时机：查找最小距离/步数 使用方法：BFS（无权）、Dijkstra（带权） 示例：单词接龙、最短的桥

模式 3：环检测

使用时机：检查循环依赖 使用方法：带 3 种状态的 DFS（未访问、正在访问、已访问） 示例：课程表、检测环

模式 4：拓扑排序

使用时机：对有依赖的任务排序 使用方法：DFS（后序）或 BFS（Kahn 算法） 示例：课程表 II、外星词典

模式 5：并查集

使用时机：动态连通性、分组 使用方法：并查集（不相交集合联合） 示例：省份数量、冗余连接

何时不使用图

• 简单线性遍历 → 使用数组/列表
• 具有明确父子关系的层次数据 → 使用树
• 键值查找 → 使用哈希表
• 顺序处理 → 使用队列/栈

面试关键要点

1. 邻接表是默认表示方法（90% 的问题）
2. DFS = 栈，BFS = 队列（记住两个模板）
3. 始终追踪已访问节点以避免无限循环
4. BFS 找最短路径（在无权图中）
5. DFS 更适合路径、环和回溯
6. 时间复杂度是 $O(V + E)$（两种遍历）
7. 空间复杂度：
   • DFS: $O(H)$ (高度/深度)
   • BFS: $O(W)$ (最大宽度)

总结

图是建模关系和连接的基本数据结构。掌握图需要：

1. 理解表示方法：邻接表（默认）vs 矩阵
2. 了解遍历算法：DFS（深度优先）和 BFS（广度优先）
3. 识别模式：连通性、最短路径、环、拓扑排序
4. 练习常见问题：从 LC 200、133、207 开始

记住：面试中的大多数图问题使用邻接表和 DFS 或 BFS。熟练掌握这两种遍历模式，你将自信地处理 90% 的图问题！

下一步：

• 练习基本遍历问题
• 学习高级算法：Dijkstra、并查集、拓扑排序
• 研究图的特定模式：二分图、强连通分量

祝编码愉快！🚀