图算法题解题思路与代码分析

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

核心解题思路

• DFS：递归或栈实现，遍历时需记录已访问节点，避免重复访问和死循环。
• BFS：队列实现，常用于无权图的最短路径或层次遍历。

经典例题：133. 克隆图

题目：给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。每个节点包含一个值 val 和邻居列表 neighbors。

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) return null;
    // 哈希表记录原节点 -> 克隆节点的映射
    const map = new Map();
    
    function dfs(original) {
        if (map.has(original)) return map.get(original);
        // 创建克隆节点
        const clone = new Node(original.val);
        map.set(original, clone);
        // 递归克隆所有邻居
        for (const neighbor of original.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
    
    return dfs(node);
};

关键点：

• 使用哈希表避免重复克隆和死循环（因为图可能有环）。
• DFS 递归克隆每个节点，并递归处理邻居。
• 时间复杂度 O(N + M)，N 为节点数，M 为边数。

BFS 版本：

var cloneGraph = function(node) {
    if (!node) return null;
    const map = new Map();
    map.set(node, new Node(node.val));
    const queue = [node];
    
    while (queue.length) {
        const cur = queue.shift();
        for (const neighbor of cur.neighbors) {
            if (!map.has(neighbor)) {
                map.set(neighbor, new Node(neighbor.val));
                queue.push(neighbor);
            }
            // 将邻居的克隆节点加入当前节点的克隆节点的邻居列表
            map.get(cur).neighbors.push(map.get(neighbor));
        }
    }
    return map.get(node);
};

二、拓扑排序

核心解题思路

拓扑排序用于有向无环图（DAG），常见算法是 Kahn 算法（基于入度）和 DFS 后序。核心是不断删除入度为 0 的节点，若最后仍有节点剩余，则说明有环。

经典例题：207. 课程表

题目：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。给定课程总量以及先修关系列表 prerequisites，请你判断是否可能完成所有课程的学习？

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    // 构建邻接表
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);
    for (const [course, pre] of prerequisites) {
        graph[pre].push(course);
        indegree[course]++;
    }
    
    // 将入度为0的节点入队
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    
    let count = 0; // 已访问节点数
    while (queue.length) {
        const cur = queue.shift();
        count++;
        for (const next of graph[cur]) {
            indegree[next]--;
            if (indegree[next] === 0) queue.push(next);
        }
    }
    
    return count === numCourses; // 若能访问所有节点，则无环
};

关键点：

• 邻接表存储有向图，同时记录每个节点的入度。
• 队列中始终存放入度为 0 的节点（当前可修的课程）。
• 若最终访问节点数等于总节点数，则无环；否则有环。
• 时间复杂度 O(N + M)。

三、并查集（Union-Find）

核心解题思路

并查集用于处理动态连通性问题，支持合并和查找操作。通常配合路径压缩和按秩合并优化。

经典例题：684. 冗余连接

题目：在本问题中，树是一个连通的无向图，且没有环。输入一个图，该图由一个树添加一条额外的边构成。请你找出这条多余的边（如果有多个答案，返回最后出现的边）。

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
    const n = edges.length;
    const parent = new Array(n + 1).fill(0).map((_, i) => i); // 节点从1到n
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX === rootY) return false; // 已经连通，说明这条边多余
        parent[rootY] = rootX; // 合并
        return true;
    }
    
    for (const [u, v] of edges) {
        if (!union(u, v)) return [u, v];
    }
    return [];
};

关键点：

• 初始时每个节点单独成一个集合。
• 遍历每条边，尝试合并两个端点。若两点已经在同一集合中，则当前边是多余的，直接返回。
• 时间复杂度接近 O(n)（因路径压缩）。

四、最短路径（Dijkstra）

核心解题思路

Dijkstra 算法用于解决非负权图的单源最短路径问题。核心思想是贪心 + 优先队列，每次从当前距离最小的节点开始松弛其邻居。

经典例题：743. 网络延迟时间

题目：有 n 个网络节点，标记为 1 到 n。给你一个 times 数组，表示有向边及其传播时间。现从某个节点 k 发出一个信号，需要多久才能使所有节点都收到信号？如果不可能，返回 -1。

/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function(times, n, k) {
    // 构建邻接表
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) {
        graph[u].push([v, w]);
    }
    
    // 距离数组，初始化为无穷大
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    
    // 优先队列，存储 [距离, 节点]，按距离升序
    // 手动实现最小堆，或使用数组 + sort（效率低，但简洁演示）
    const pq = [[0, k]];
    
    while (pq.length) {
        pq.sort((a, b) => a[0] - b[0]); // 每次排序（实际应用应使用堆）
        const [d, u] = pq.shift();
        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]);
            }
        }
    }
    
    let maxTime = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxTime = Math.max(maxTime, dist[i]);
    }
    return maxTime;
};

关键点：

• 使用邻接表存储有向加权图。
• 距离数组初始化为无穷大，起点距离为 0。
• 每次从优先队列中取出当前距离最小的节点，松弛其邻居。
• 最终取所有节点距离的最大值即为所需时间。
• 时间复杂度 O((N+M) log N)（若用堆），这里用数组排序会导致 O(N² log N)。

五、最小生成树（Kruskal）

核心解题思路

Kruskal 算法：将所有边按权值排序，依次加入边，若加入后不形成环（用并查集判断），则保留该边，直到加入 n-1 条边。

经典例题：1584. 连接所有点的最小费用

题目：给你一个 points 数组，表示二维平面上的点。连接两个点 [xi, yi] 和 [xj, yj] 的费用是曼哈顿距离：|xi - xj| + |yi - yj|。请你返回将所有点连接的最小总费用。

/**
 * @param {number[][]} points
 * @return {number}
 */
var minCostConnectPoints = function(points) {
    const n = points.length;
    // 生成所有边
    const edges = [];
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const cost = Math.abs(points[i][0] - points[j][0]) + 
                         Math.abs(points[i][1] - points[j][1]);
            edges.push([i, j, cost]);
        }
    }
    // 按权值排序
    edges.sort((a, b) => a[2] - b[2]);
    
    // 并查集
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x) => {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    };
    const union = (x, y) => {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX === rootY) return false;
        parent[rootY] = rootX;
        return true;
    };
    
    let totalCost = 0;
    let edgesUsed = 0;
    for (const [u, v, cost] of edges) {
        if (union(u, v)) {
            totalCost += cost;
            edgesUsed++;
            if (edgesUsed === n - 1) break;
        }
    }
    return totalCost;
};

关键点：

• 计算所有点对之间的曼哈顿距离，生成边列表。
• 按边权排序后，用并查集判断是否形成环。
• 当加入 n-1 条边时，即得到最小生成树。
• 时间复杂度 O(n² log n)（生成所有边 + 排序）。

六、二分图

核心解题思路

二分图判定常用染色法：用两种颜色对图进行 DFS/BFS 染色，若相邻节点颜色相同，则不是二分图。

经典例题：785. 判断二分图

题目：给定一个无向图 graph，当这个图是二分图时返回 true。图用邻接表给出，graph[i] 表示节点 i 的邻居。

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function(graph) {
    const n = graph.length;
    const colors = new Array(n).fill(0); // 0未染色，1和-1分别代表两种颜色
    
    function bfs(start) {
        const queue = [start];
        colors[start] = 1; // 染成1
        while (queue.length) {
            const node = queue.shift();
            const color = colors[node];
            for (const neighbor of graph[node]) {
                if (colors[neighbor] === 0) {
                    colors[neighbor] = -color; // 染成相反色
                    queue.push(neighbor);
                } else if (colors[neighbor] === color) {
                    return false; // 相邻同色
                }
            }
        }
        return true;
    }
    
    for (let i = 0; i < n; i++) {
        if (colors[i] === 0 && !bfs(i)) {
            return false;
        }
    }
    return true;
};

关键点：

• 对每个未染色节点进行 BFS 染色。
• 如果发现相邻节点颜色相同，则不是二分图。
• 时间复杂度 O(N + M)。

七、强连通分量 & 割点/桥（Tarjan）

核心解题思路

Tarjan 算法通过 DFS 记录每个节点的发现时间 disc 和最早可达祖先时间 low。若对于边 (u,v)，有 low[v] > disc[u]，则 (u,v) 是桥（关键连接）。对于割点，条件稍复杂。

经典例题：1192. 查找集群内的关键连接

题目：给定一个无向连通图，找到所有的关键连接（桥），即删除后会增加连通分量数量的边。

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number[][]}
 */
var criticalConnections = function(n, connections) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const disc = new Array(n).fill(-1); // 发现时间
    const low = new Array(n).fill(-1);  // 最早可达祖先时间
    const result = [];
    let time = 0;
    
    function dfs(u, parent) {
        disc[u] = low[u] = time++;
        for (const v of graph[u]) {
            if (v === parent) continue; // 忽略父节点
            if (disc[v] === -1) {
                // 未访问
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    // (u,v) 是桥
                    result.push([u, v]);
                }
            } else {
                // 回边
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (disc[i] === -1) dfs(i, -1);
    }
    return result;
};

关键点：

• disc 记录节点首次被访问的时间戳。
• low 记录节点不经过父节点能到达的最早祖先的发现时间。
• 桥的条件：对于边 (u,v)（v 是 u 的子节点），若 low[v] > disc[u]，则说明 v 无法通过其他路径回到 u 或更早的节点，因此 (u,v) 是桥。
• 时间复杂度 O(N + M)。

八、欧拉路径/回路

核心解题思路

欧拉路径是经过每条边恰好一次的路径。Hierholzer 算法：从起点开始 DFS，每经过一条边就删除它，并将访问的节点按逆序记录，最后逆序输出就是路径。对于有向图，需确保入度出度条件。

经典例题：332. 重新安排行程

题目：给定一个机票列表，每张机票 [from, to] 表示从出发地到目的地。所有机票都是从 JFK 出发，请重新规划行程，使得行程按字典序最小（若有多种可能）。

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
    // 构建邻接表，并按字典序排序
    const graph = new Map();
    for (const [from, to] of tickets) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push(to);
    }
    for (const [from, list] of graph) {
        list.sort(); // 字典序升序
    }
    
    const result = [];
    
    function dfs(node) {
        const neighbors = graph.get(node) || [];
        while (neighbors.length) {
            const next = neighbors.shift(); // 取最小的邻居并移除（相当于删除边）
            dfs(next);
        }
        result.push(node); // 后序记录
    }
    
    dfs("JFK");
    return result.reverse(); // 逆序即为欧拉路径
};

关键点：

• 使用邻接表，并对每个节点的邻居按字典序排序，保证优先选择字典序小的路径。
• 在 DFS 中，每遍历一条边就将其删除（shift 出最小邻居）。
• 将访问的节点在递归返回后推入结果数组，最后反转得到正确顺序（Hierholzer 算法）。
• 时间复杂度 O(N log N)（排序）。

总结

以上八个分类覆盖了图论的主要算法。建议按以下顺序练习：

1. 基础遍历：133. 克隆图
2. 拓扑排序：207. 课程表
3. 并查集：684. 冗余连接
4. 最短路径：743. 网络延迟时间
5. 最小生成树：1584. 连接所有点的最小费用
6. 二分图：785. 判断二分图
7. 强连通分量/桥：1192. 关键连接（进阶）
8. 欧拉路径：332. 重新安排行程（进阶）