如何在 LeetCode 上练习图问题：初学者的结构化路线图

Source: Dev.to

TL;DR

• 不要从随机的图题开始；先从 无权重的 BFS/DFS 在网格和简单树上 入手，然后逐步转向邻接表、拓扑排序和最短路径。
• 按 模式（BFS、DFS、连通分量、拓扑排序、最短路径） 将图题分成 集群 练习，而不是随意跳来跳去，这样大脑才能真正看到共同的结构。
• 在编码前使用可视化图（节点、边、层级）来推理图的行为，尤其是 BFS 的层级和环检测。
• 初学者常常跳过基础的网格/图建模，不画图，直接去做 Dijkstra/并查集，这会削弱信心和记忆。
• 一个简单的 3 阶段路线图，配合 DSA 学习路径 与类似 AI 引导的 LeetCode 练习 的工具，可以让图题感觉系统化而非混乱。

Phase 0: Get Comfortable with the Mental Model of a Graph

What is a graph?

从本质上讲，图是：

• 一组 节点（顶点）。
• 一组 边，连接节点（可能是有向的）。

可视化示例

   A ---- B
   |      |
   |      |
   C ---- D

你可以把许多 LeetCode 题目建模为图：

• 网格（每个格子是一个与相邻格子相连的节点）。
• 课程先修关系（节点 = 课程，边 = “必须先修”。）
• 社交网络、城市地图、依赖图。

Minimal code representation

对于大多数入门题目，邻接表已经足够：

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # if undirected

当你对这段代码熟悉后，后面的图算法就会容易得多。

Phase 1: Grids and Trees – Your Gentle Graph On‑Ramp

1A. Grids as implicit graphs

像 “Number of Islands” 或 “Rotting Oranges” 这类题目本质上是图题：

• 每个单元格 (r, c) 是一个节点。
• 边连接它的上下左右相邻单元格（如果合法）。

邻居辅助函数

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbors(r, c, rows, cols):
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

重点关注：

• 将节点标记为 已访问。
• 防止重复访问。
• 理解 BFS 如何按层次遍历。

1B. Trees as simpler graphs

二叉树问题是 “有结构且无环的图”。
练习：

• DFS（递归和迭代）用于深度、路径和、子树检查。
• BFS（层序遍历）用于距离、每层平均值等。

Phase 1 目标
你能够毫不犹豫地在网格和树上编写 BFS/DFS，并在笔记中拥有一套干净、可复用的遍历模板。

Phase 2: Explicit Graphs – Adjacency Lists, Components, and Cycles

2A. Build the graph yourself

给定 n 个节点和一个 edges 列表：

def build_graph(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # if undirected
    return graph

练习那些会问：

• “有多少个连通分量？”
• “这张图是二分图吗？”
• “X 与 Y 之间是否存在路径？”

2B. Connected components with DFS/BFS

遍历所有节点；如果某节点未访问，则启动一次 BFS/DFS，将所有可达节点标记为已访问，然后将连通分量计数加一。

可视化示例

Component 1: 0 - 1 - 2
Component 2: 3 - 4
Component 3: 5

2C. Cycle detection

• 无向图 – 使用带 parent 参数的 DFS；若访问到的相邻节点不是父节点，则说明存在环。
• 有向图 – 使用三色标记（未访问、访问中、已访问）或递归栈集合。

这一步让你开始接触需要 “不仅仅是遍历” 的题目。

Phase 3: Topological Sort and Shortest Paths

3A. Topological sort (ordering with prerequisites)

两种常见实现：

• Kahn 算法（基于入度的 BFS）。
• DFS + 栈（逆后序）。

典型模式：节点 = 任务/课程，边 u → v 表示 “u 必须在 v 之前”。拓扑序就是任意满足依赖关系的排列。

想获取更多面试准备指导，请参阅 how to run mock coding interviews by yourself。

3B. Shortest paths in unweighted graphs

使用 BFS：每条边的代价为 1，因而从源点出发的 BFS 自然得到最少步数。示例：在无权重网格中的最短路径。

3C. Shortest paths with weights (optional for beginners)

在掌握了 BFS/DFS + 拓扑排序后，学习 Dijkstra 算法（配合最小堆）。并非所有加权最短路变体都必须会才能通过大多数面试，但能够判断何时使用 BFS、何时需要 Dijkstra 是关键。

Weekly Practice Plan for Graph Beginners

一个切合实际的 3–4 周 计划，可嵌入更广的 DSA 学习路径。

Week 1 – Grids & Trees

• 3–4 道 “Number of Islands” 类的网格题。
• 2–3 道树的 BFS 题（层序遍历、每层平均值等）。
• 2–3 道树的 DFS 题（最大深度、路径和等）。

Week 2 – Explicit Graphs & Components

• 3 题：构建邻接表并遍历。
• 2 题：统计连通分量。
• 2 题：检测无向图中的环。

Week 3 – Directed Graphs & Toposort

• 2–3 题：检测有向图中的环。
• 2–3 题：课程表 / 任务排序（拓扑排序）。
• 1–2 题：无权图的 BFS 最短路径。

Optional Week 4 – Weighted Graphs

• 2–3 题：Dijkstra 风格的加权最短路径。
• 1–2 题：将图与其他模式混合的题目。

像 AI‑guided LeetCode practice 这样的工具可以帮助你生成自定义题集，并在遵循此路线图时即时获得反馈。