面试手撕图论板子：建图 / BFS / 网格 / 拓扑 / 并查集 / 最短路

给你一套专门练图论板子的 LeetCode 题单。目标不是刷玄学难题，而是把这些板子练熟：

邻接表建图、BFS、DFS、网格 BFS/DFS、拓扑排序、并查集、最短路。

0. 入门：先练”图怎么存”

题目

题号	题名	练什么
797	所有可能的路径	有向图邻接表 + DFS
841	钥匙和房间	邻接表 + BFS/DFS
1971	寻找图中是否存在路径	无向图建图 + BFS/DFS
1791	找出星型图的中心节点	边的理解

先把这个板子练熟：

vector<vector<int>> g(n);

for (int i = 0; i < edges.size(); i++) {
    int u = edges[i][0];
    int v = edges[i][1];

    g[u].push_back(v);
}

无向图就是：

g[u].push_back(v);
g[v].push_back(u);

1. BFS / DFS 基础遍历

题目

题号	题名	推荐做法
547	省份数量	DFS / BFS
841	钥匙和房间	DFS / BFS
1971	寻找图中是否存在路径	BFS
2316	统计无向图中无法互相到达点对数	DFS 统计连通块大小

核心模板：

vector<int> visited(n, 0);
queue<int> q;

q.push(start);
visited[start] = 1;

while (!q.empty()) {
    int cur = q.front();
    q.pop();

    for (int i = 0; i < g[cur].size(); i++) {
        int next = g[cur][i];

        if (visited[next] == 1) {
            continue;
        }

        visited[next] = 1;
        q.push(next);
    }
}

2. 网格图：dx dy 板子

这是面试最常见的一类。

题目

题号	题名	练什么
200	岛屿数量	网格 DFS/BFS
695	岛屿的最大面积	DFS 统计面积
994	腐烂的橘子	多源 BFS
542	01 矩阵	多源 BFS
733	图像渲染	简单 Flood Fill
130	被围绕的区域	从边界反向 DFS/BFS
1091	二进制矩阵中的最短路径	八方向 BFS
417	太平洋大西洋水流问题	反向 DFS/BFS

四方向板子：

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

for (int k = 0; k < 4; k++) {
    int nx = x + dx[k];
    int ny = y + dy[k];

    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
        continue;
    }

    // 处理 grid[nx][ny]
}

八方向板子：

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

3. 拓扑排序：课程表这一类

这是你现在正在练的。

题目

题号	题名	练什么
207	课程表	拓扑排序判环
210	课程表 II	输出拓扑序
802	找到最终的安全状态	反图 + 拓扑 / DFS 判环
1462	课程表 IV	传递依赖
310	最小高度树	拓扑剥叶子
1203	项目管理	分组拓扑排序，偏难

最核心先刷：

207 -> 210 -> 802 -> 310

拓扑排序模板：

queue<int> q;
vector<vector<int>> g(n);
vector<int> indeg(n, 0);

for (int i = 0; i < edges.size(); i++) {
    int u = edges[i][0];
    int v = edges[i][1];

    g[u].push_back(v);
    indeg[v]++;
}

for (int i = 0; i < n; i++) {
    if (indeg[i] == 0) {
        q.push(i);
    }
}

int learned = 0;

while (!q.empty()) {
    int learning = q.front();
    q.pop();

    learned++;

    for (int i = 0; i < g[learning].size(); i++) {
        int toBeLearn = g[learning][i];

        indeg[toBeLearn]--;

        if (indeg[toBeLearn] == 0) {
            q.push(toBeLearn);
        }
    }
}

return learned == n;

4. 并查集：连通性专用

并查集适合处理：

谁和谁属于同一个集合。

题目

题号	题名	练什么
547	省份数量	并查集入门
684	冗余连接	找环
1971	寻找图中是否存在路径	连通性
1319	连通网络的操作次数	连通块数量
990	等式方程的可满足性	字符并查集
721	账户合并	字符串并查集，偏实战

板子：

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    void merge(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (pa != pb) {
            parent[pa] = pb;
        }
    }
};

5. 最短路：BFS / Dijkstra

普通无权图最短路，用 BFS。带权正边最短路，用 Dijkstra。

BFS 最短路题

题号	题名	练什么
1091	二进制矩阵中的最短路径	八方向 BFS
752	打开转盘锁	状态图 BFS
127	单词接龙	状态图 BFS，偏难
433	最小基因变化	BFS

Dijkstra 题

题号	题名	练什么
743	网络延迟时间	Dijkstra 模板
1514	概率最大的路径	Dijkstra 变形
1631	最小体力消耗路径	Dijkstra on Grid
787	K 站中转内最便宜的航班	最短路变形，偏难

Dijkstra 先不用急，等你 BFS / 拓扑 / 并查集稳了再练。

6. DFS 判环

拓扑排序可以 BFS 做，DFS 也能判环。你可以后面补。

题目

题号	题名	练什么
207	课程表	DFS 三色标记判环
802	找到最终的安全状态	DFS 判环
1059	从始点到终点的所有路径	DFS 判环，偏难

三色标记：

0 = 没访问
1 = 正在访问
2 = 访问完成

最小无痛版题单

要是你只想快速掌握面试图论板子，刷这 15 道就够有感觉：

841 钥匙和房间
1971 寻找图中是否存在路径
547 省份数量
733 图像渲染
200 岛屿数量
695 岛屿的最大面积
994 腐烂的橘子
542 01 矩阵
207 课程表
210 课程表 II
802 找到最终的安全状态
684 冗余连接
1319 连通网络的操作次数
752 打开转盘锁
743 网络延迟时间

你现在最该练的是：

207 课程表
210 课程表 II
841 钥匙和房间
200 岛屿数量
994 腐烂的橘子

这五道刷完，图论最基础的几个板子就真的立住了。