LLY的博客

Appearance

图算法题分类解析 ​

一、图的基础与遍历（DFS/BFS） ​

类型特点：这是图论最基础的操作。需要掌握如何构建图（邻接表/邻接矩阵），以及如何用 DFS/BFS 遍历图。很多复杂问题都是在此基础上扩展的。

难度题目核心思路简介
简单1971. 寻找图中是否存在路径DFS/BFS/并查集判断两点是否连通
中等133. 克隆图DFS/BFS + 哈希表记录已克隆节点
中等841. 钥匙和房间DFS/BFS 遍历，判断能否访问所有房间
中等797. 所有可能的路径DFS 回溯，记录从源点到目标的所有路径
中等547. 省份数量DFS/BFS/并查集统计连通分量个数

二、拓扑排序 ​

类型特点：用于处理有向无环图（DAG） 中任务的依赖关系。核心思想是不断删除入度为 0 的节点（Kahn 算法）或使用 DFS 后序记录。

难度题目核心思路简介
中等207. 课程表拓扑排序判断是否有环（能否完成所有课程）
中等210. 课程表 II拓扑排序返回一种合理的课程顺序
中等1462. 课程表 IVFloyd 或 DFS 预处理课程间的先修关系
困难1203. 项目管理两次拓扑排序（组间+组内）
中等2115. 从给定原材料中找到所有可以做出的菜拓扑排序，将食谱看作依赖关系

三、并查集（Union-Find） ​

类型特点：高效处理动态连通性问题，支持合并集合和查询所属集合。核心操作是 find（路径压缩）和 union（按秩合并）。

难度题目核心思路简介
中等684. 冗余连接并查集，当发现两个节点已连通时，当前边即为冗余边
中等721. 账户合并将邮箱作为节点，用并查集合并属于同一账户的邮箱
中等990. 等式方程的可满足性先将相等关系的变量合并，再检查不等关系是否矛盾
中等1319. 连通网络的操作次数并查集统计连通分量个数，所需操作数 = 分量数 - 1
困难947. 移除最多的同行或同列石头将行号和列号作为节点合并，最多移除数 = 总石头数 - 连通分量数

四、最短路径 ​

类型特点：求图中两点之间的最短路径。根据边权特点选择不同算法：

  • BFS：适用于无权图（所有边权为1）
  • Dijkstra：适用于非负权图（优先队列优化）
  • Bellman-Ford/SPFA：适用于有负权图（可检测负环）
  • Floyd-Warshall：多源最短路径
难度题目核心思路简介
中等743. 网络延迟时间Dijkstra 标准模板
中等1631. 最小体力消耗路径二分答案 + BFS/DFS，或 Dijkstra 变种
中等1514. 概率最大的路径Dijkstra 变种（求乘积最大值）
中等787. K 站中转内最便宜的航班Bellman-Ford 或 BFS + DP
中等1334. 阈值距离内邻居最少的城市Floyd-Warshall 多源最短路径
中等542. 01 矩阵多源 BFS（所有0同时入队）

五、最小生成树（MST） ​

类型特点：在连通加权图中寻找一棵树，连接所有节点且总权值最小。常用算法：

  • Kruskal：按边权排序 + 并查集
  • Prim：类似 Dijkstra，每次找最小边连接新节点
难度题目核心思路简介
中等1584. 连接所有点的最小费用Kruskal 或 Prim 模板
中等1135. 最低成本联通所有城市（会员）Kruskal 模板
困难1489. 找到最小生成树里的关键边和伪关键边最小生成树 + 枚举判断

六、二分图 ​

类型特点：判断图是否能分成两个集合，使得集合内部无边（即所有边连接两个不同集合）。可用染色法（DFS/BFS）解决。

难度题目核心思路简介
中等785. 判断二分图染色法 BFS/DFS
中等886. 可能的二分法建图后判断二分图

七、强连通分量 & 割点/桥 ​

类型特点：进阶图论问题，通常需要 Tarjan 算法找强连通分量（SCC）或关键连接。

难度题目核心思路简介
困难1192. 查找集群内的关键连接Tarjan 算法找桥（边）
困难1568. 使陆地分离的最少天数结合连通分量计数和 Tarjan 思想

八、欧拉路径/回路 ​

类型特点：寻找一条路径经过每条边恰好一次（一笔画问题）。常用 Hierholzer 算法。

难度题目核心思路简介
困难332. 重新安排行程Hierholzer 算法找欧拉路径
困难753. 破解保险箱将密码看作边，找欧拉回路

图算法核心模板（JavaScript） ​

1. 图的构建（邻接表） ​

javascript
// 输入：n 个节点，edges 数组 [[u,v], ...]
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u); // 无向图
}

2. DFS 遍历模板 ​

javascript
function dfs(node, visited) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const neighbor of graph[node]) {
        dfs(neighbor, visited);
    }
}

3. BFS 遍历模板 ​

javascript
function bfs(start) {
    const queue = [start];
    const visited = new Set([start]);
    while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

4. 拓扑排序模板（Kahn 算法） ​

javascript
function topologicalSort(n, graph, indegree) {
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    const result = [];
    while (queue.length) {
        const node = queue.shift();
        result.push(node);
        for (const neighbor of graph[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] === 0) queue.push(neighbor);
        }
    }
    return result.length === n ? result : []; // 有环返回空
}

5. 并查集模板 ​

javascript
class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // 路径压缩
        }
        return this.parent[x];
    }
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) return false;
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

6. Dijkstra 模板（优先队列） ​

javascript
function dijkstra(graph, n, start) {
    const dist = Array(n).fill(Infinity);
    dist[start] = 0;
    const pq = new MinHeap(); // 需实现最小堆
    pq.push([0, start]); // [距离, 节点]
    while (pq.size()) {
        const [d, u] = pq.pop();
        if (d > dist[u]) continue;
        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    return dist;
}

刷题建议 ​

  1. 基础入门：从 1971. 寻找图中是否存在路径、841. 钥匙和房间 入手，掌握图的 DFS/BFS 遍历。

  2. 拓扑排序：练习 207. 课程表 → 210. 课程表 II，理解依赖关系处理。

  3. 并查集：从 547. 省份数量 → 684. 冗余连接，掌握连通分量和环检测。

  4. 最短路径：从 743. 网络延迟时间（Dijkstra）→ 542. 01 矩阵（多源 BFS）。

  5. 进阶挑战：最后攻克 1192. 关键连接（Tarjan 桥）和 332. 重新安排行程（欧拉路径）。

Released under the MIT License.

Copyright © 2026