Interview Prep

图论算法题复习笔记

整理邻接表建图、BFS/DFS 遍历、网格图 dx dy、拓扑排序、并查集、BFS 与 Dijkstra 最短路，并附一组精简练习题。

发布于 约 4 分钟算法LeetCode
目录 · 26 节

这里整理一组练图论基础模板的 LeetCode 题单。目标不是追求难题，而是把这些常用写法练熟：

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

一、入门：先练「图怎么存」

题目

题号题名练什么
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);
}

无向图就是双向各 push 一次：

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

注意：无向图只 push 一边会漏掉连通关系；建图前 vector<vector<int>> g(n) 先开好大小。

二、BFS / DFS 基础遍历

题目

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

BFS 核心模板

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);
    }
}

注意：入队时立刻标 visited，不然同一节点会重复入队。

三、网格图：dx dy 板子

这是面试最常见的一类。

题目

题号题名练什么
200岛屿数量网格 DFS/BFS
695岛屿的最大面积DFS 统计面积
994腐烂的橘子多源 BFS
54201 矩阵多源 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]
}

其中 n = grid.size()，m = grid[0].size()，越界直接 continue。

八方向板子

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

四、拓扑排序：课程表这一类

这是你现在正在练的。

题目

题号题名练什么
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;

注意：learned == n 才是无环，小于 n 说明有环。减入度只对邻居操作，别动 indeg[u]。

五、并查集：连通性专用

并查集适合处理：

谁和谁属于同一个集合。

题目

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

UnionFind 板子

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;
        }
    }
};

注意：merge 前先对 a、b 各做一次 find，直接 parent[a] = b 会丢掉路径压缩后的根。

六、最短路：BFS / Dijkstra

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

BFS 最短路题

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

Dijkstra 题

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

Dijkstra 堆优化板子（743 完整例题）

// 743 网络延迟时间：从 k 出发到所有点的最短路，取最大值
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // 邻接表：g[u] = {v, w}
    vector<vector<pair<int, int>>> g(n + 1);
    for (auto& e : times) {
        g[e[0]].push_back({e[1], e[2]});
    }

    const int INF = 0x3f3f3f3f;
    vector<int> dist(n + 1, INF);  // dist 全部初始化 INF
    dist[k] = 0;

    // 小根堆：{当前距离, 节点}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, k});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) {
            continue;  // 过期的堆顶，跳过
        }

        for (auto& [v, w] : g[u]) {
            if (d + w < dist[v]) {  // 松弛
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            return -1;  // 有点到不了
        }
        ans = max(ans, dist[i]);
    }
    return ans;
}

变形点：

  • 1514：求概率最大，松弛方向反过来。dist 初始 0、起点为 1，d * w > dist[v] 才更新。
  • 1631：网格图直接当最短路跑，格子就是点，边权是相邻格高度差，松弛改成 max(d, w) 取最小。
  • 787：限制 k 次中转，堆里的状态带上已飞次数 (d, u, cnt)，cnt > k + 1 就跳过；也可以按层数做 k + 1 轮松弛。

七、网络流：Dinic 板子

什么时候用：

最大流 / 最小割、二分图匹配、有容量限制的分配问题。

建模三板斧：

  • 超级源汇：源点连所有「供给」，汇点收所有「需求」。
  • 容量 = 限制：这个资源能用多少，边容量就设多少。
  • 二分图：源连左边、右边连汇，左右之间容量设 1。

板子（背到会默写）：

struct Edge {
    int to, cap, rev;  // rev: 反向边在 g[to] 里的下标
};

class Dinic {
public:
    vector<vector<Edge>> g;
    vector<int> level, it;

    Dinic(int n) : g(n), level(n), it(n) {}

    void addEdge(int u, int v, int cap) {
        g[u].push_back({v, cap, (int)g[v].size()});
        g[v].push_back({u, 0, (int)g[u].size() - 1});  // 反向边容量 0
    }

    // bfs 分层
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);

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

            for (auto& e : g[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }

        return level[t] >= 0;
    }

    // dfs 增广 + 当前弧优化
    int dfs(int u, int t, int f) {
        if (u == t) {
            return f;
        }

        for (int& i = it[u]; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];

            if (e.cap > 0 && level[e.to] == level[u] + 1) {
                int d = dfs(e.to, t, min(f, e.cap));

                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;  // 反向边加回流量，留后悔药
                    return d;
                }
            }
        }

        return 0;
    }

    int maxFlow(int s, int t) {
        int flow = 0;

        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            int f;

            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }

        return flow;
    }
};

LeetCode 直接考网络流的题很少，但板子要能默写。面试碰到「分配 / 匹配 + 容量」就往这上面想。

八、DFS 判环

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

题目

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

三色标记

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

九、推荐刷题顺序

不要一上来全刷，按这个顺序来：

第一组：邻接表 + 普通 BFS/DFS
841 -> 1971 -> 547

第二组：网格图 dx dy
733 -> 200 -> 695 -> 994 -> 542

第三组：拓扑排序
207 -> 210 -> 802 -> 310

第四组：并查集
547 -> 1971 -> 684 -> 1319 -> 990

第五组：状态图 BFS
752 -> 1091 -> 433 -> 127

第六组：Dijkstra
743 -> 1631 -> 1514

十、精简题单

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

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

你现在最该练的是：

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

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