图算法专题

图算法核心：图的表示 + 遍历方式 + 经典算法

📊 题目总览

题目	难度	梯队	关键技巧
图的表示与遍历	⭐⭐	基础	DFS/BFS
拓扑排序	⭐⭐	第二梯队	入度/Kahn
Dijkstra 最短路径	⭐⭐⭐	第三梯队	贪心/优先队列
最小生成树	⭐⭐⭐	进阶	并查集/Kruskal

1. 图的表示与遍历

难度: ⭐⭐ | 梯队: 基础 | 标签: DFS, BFS

题目描述

实现图的两种表示方式（邻接表、邻接矩阵），并实现 DFS 和 BFS 遍历。

图的表示

javascript

/**
 * 邻接表表示法（推荐）
 * 空间 O(V + E)，适合稀疏图
 */
class GraphAdjList {
  constructor() {
    this.adjList = new Map();
  }

  /**
   * 添加顶点
   */
  addVertex(v) {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
    }
  }

  /**
   * 添加边（无向图）
   */
  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjList.get(v1).push(v2);
    this.adjList.get(v2).push(v1);
  }

  /**
   * 添加有向边
   */
  addDirectedEdge(from, to) {
    this.addVertex(from);
    this.addVertex(to);
    this.adjList.get(from).push(to);
  }

  /**
   * 获取邻居节点
   */
  getNeighbors(v) {
    return this.adjList.get(v) || [];
  }
}

/**
 * 带权邻接表
 */
const weightedGraph = {
  A: [{ node: 'B', weight: 1 }, { node: 'C', weight: 4 }],
  B: [{ node: 'C', weight: 2 }, { node: 'D', weight: 5 }],
  C: [{ node: 'D', weight: 1 }],
  D: []
};

/**
 * 邻接矩阵表示法
 * 空间 O(V²)，适合稠密图
 */
class GraphAdjMatrix {
  constructor(size) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () =>
      new Array(size).fill(0)
    );
  }

  addEdge(v1, v2, weight = 1) {
    this.matrix[v1][v2] = weight;
    this.matrix[v2][v1] = weight; // 无向图
  }
}

图的遍历

javascript

/**
 * DFS 深度优先遍历 - 递归
 * @param {Map} graph - 邻接表
 * @param {any} start - 起始节点
 * @return {any[]}
 */
function dfsRecursive(graph, start) {
  const visited = new Set();
  const result = [];

  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);

    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor);
    }
  }

  dfs(start);
  return result;
}

/**
 * DFS 深度优先遍历 - 迭代（使用栈）
 */
function dfsIterative(graph, start) {
  const visited = new Set();
  const result = [];
  const stack = [start];

  while (stack.length) {
    const node = stack.pop();

    if (visited.has(node)) continue;
    visited.add(node);
    result.push(node);

    // 逆序入栈，保证顺序
    const neighbors = graph.get(node) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return result;
}

/**
 * BFS 广度优先遍历（使用队列）
 */
function bfs(graph, start) {
  const visited = new Set([start]);
  const result = [];
  const queue = [start];

  while (queue.length) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

示例调用

javascript

// 创建图
//   A -- B
//   |    |
//   C -- D
const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D']],
  ['C', ['A', 'D']],
  ['D', ['B', 'C']]
]);

// DFS 遍历
console.log(dfsRecursive(graph, 'A')); // ['A', 'B', 'D', 'C']
console.log(dfsIterative(graph, 'A')); // ['A', 'B', 'D', 'C']

// BFS 遍历
console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D']

// 边界条件：空图
const emptyGraph = new Map();
console.log(dfsRecursive(emptyGraph, 'A')); // []
console.log(bfs(emptyGraph, 'A'));           // []

// 边界条件：单节点
const singleGraph = new Map([['A', []]]);
console.log(dfsRecursive(singleGraph, 'A')); // ['A']
console.log(bfs(singleGraph, 'A'));           // ['A']

// 边界条件：不连通图（只遍历连通部分）
const disconnected = new Map([
  ['A', ['B']],
  ['B', ['A']],
  ['C', ['D']],
  ['D', ['C']]
]);
console.log(bfs(disconnected, 'A')); // ['A', 'B']

// 边界条件：有环图
const cyclic = new Map([
  ['A', ['B']],
  ['B', ['C']],
  ['C', ['A']] // 形成环
]);
console.log(dfsRecursive(cyclic, 'A')); // ['A', 'B', 'C'] (不会死循环)

复杂度分析

时间: O(V + E)，V 为顶点数，E 为边数
空间: O(V)，visited 集合

2. 拓扑排序

LeetCode: 207. 课程表 / 210. 课程表 II | 难度: ⭐⭐ | 梯队: 第二梯队

题目描述

给定课程数量和先决条件，判断是否能完成所有课程（检测有向图是否有环），并返回学习顺序。

输入: numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]
输出: [0, 1, 2, 3] 或 [0, 2, 1, 3]（拓扑排序不唯一）

核心思路

Kahn 算法（BFS）：

计算所有节点的入度
将入度为 0 的节点入队
每次出队一个节点，将其邻居的入度减 1
入度变为 0 的节点入队
若最终出队数 == 节点数，则无环

代码实现

javascript

/**
 * 拓扑排序 - Kahn 算法（BFS）
 * @param {number} numCourses - 课程数量
 * @param {number[][]} prerequisites - 先决条件 [course, prereq]
 * @return {number[]} - 拓扑排序结果，有环返回空数组
 */
function topologicalSort(numCourses, prerequisites) {
  // 1. 构建图和入度数组
  const inDegree = new Array(numCourses).fill(0);
  const graph = Array.from({ length: numCourses }, () => []);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  // 2. 入度为 0 的节点入队
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  // 3. BFS 处理
  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);
      }
    }
  }

  // 4. 判断是否有环
  return result.length === numCourses ? result : [];
}

/**
 * 检测是否能完成所有课程（有无环）
 */
function canFinish(numCourses, prerequisites) {
  return topologicalSort(numCourses, prerequisites).length === numCourses;
}

/**
 * 拓扑排序 - DFS 版本
 */
function topologicalSortDFS(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  const WHITE = 0; // 未访问
  const GRAY = 1;  // 访问中
  const BLACK = 2; // 已完成
  const color = new Array(numCourses).fill(WHITE);
  const result = [];
  let hasCycle = false;

  function dfs(node) {
    if (hasCycle) return;
    color[node] = GRAY;

    for (const neighbor of graph[node]) {
      if (color[neighbor] === GRAY) {
        // 发现后向边，有环
        hasCycle = true;
        return;
      }
      if (color[neighbor] === WHITE) {
        dfs(neighbor);
      }
    }

    color[node] = BLACK;
    result.unshift(node); // 完成时加入结果
  }

  for (let i = 0; i < numCourses; i++) {
    if (color[i] === WHITE) {
      dfs(i);
    }
  }

  return hasCycle ? [] : result;
}

示例调用

javascript

// 基础示例
console.log(topologicalSort(4, [[1, 0], [2, 0], [3, 1], [3, 2]]));
// 输出: [0, 1, 2, 3] 或 [0, 2, 1, 3]

console.log(canFinish(2, [[1, 0]])); // true

// 边界条件：有环
console.log(topologicalSort(2, [[0, 1], [1, 0]])); // []
console.log(canFinish(2, [[0, 1], [1, 0]]));        // false

// 边界条件：无依赖
console.log(topologicalSort(3, [])); // [0, 1, 2]

// 边界条件：单个课程
console.log(topologicalSort(1, [])); // [0]

// 边界条件：线性依赖
console.log(topologicalSort(3, [[1, 0], [2, 1]])); // [0, 1, 2]

// 边界条件：复杂图
console.log(topologicalSort(6, [
  [1, 0], [2, 0], [3, 1], [3, 2], [4, 3], [5, 3]
])); // [0, 1, 2, 3, 4, 5] 或其他有效顺序

// DFS 版本对比
console.log(topologicalSortDFS(4, [[1, 0], [2, 0], [3, 1], [3, 2]]));
// 输出: [0, 2, 1, 3] 或其他有效顺序

复杂度分析

时间: O(V + E)
空间: O(V + E)

3. Dijkstra 最短路径

难度: ⭐⭐⭐ | 梯队: 第三梯队 | 标签: 贪心, 优先队列

题目描述

给定带权有向图和起点，求到所有其他节点的最短路径。

核心思路

Dijkstra 算法：

初始化所有距离为 Infinity，起点距离为 0
每次选择距离最小的未访问节点
更新其邻居的距离（松弛操作）
重复直到所有节点访问完毕

限制：不能处理负权边

代码实现

javascript

/**
 * Dijkstra 最短路径 - 简易版（O(V²)）
 * @param {Object} graph - 带权邻接表
 * @param {string} start - 起始节点
 * @return {Object} - 到各节点的最短距离
 */
function dijkstraSimple(graph, start) {
  const distances = {};
  const visited = new Set();

  // 初始化距离
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    // 找到距离最小的未访问节点
    let minNode = null;
    let minDist = Infinity;
    for (const node in distances) {
      if (!visited.has(node) && distances[node] < minDist) {
        minNode = node;
        minDist = distances[node];
      }
    }

    if (minNode === null) break;
    visited.add(minNode);

    // 松弛操作
    for (const { node: neighbor, weight } of graph[minNode] || []) {
      const newDist = distances[minNode] + weight;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
      }
    }
  }

  return distances;
}

/**
 * Dijkstra 最短路径 - 优先队列版（O((V+E) log V)）
 */
class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(item) {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent][0] <= this.heap[index][0]) break;
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }

  bubbleDown(index) {
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;

      if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
        smallest = right;
      }

      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

function dijkstraHeap(graph, start) {
  const distances = {};
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  const pq = new MinHeap();
  pq.push([0, start]); // [distance, node]

  const visited = new Set();

  while (!pq.isEmpty()) {
    const [dist, node] = pq.pop();

    if (visited.has(node)) continue;
    visited.add(node);

    for (const { node: neighbor, weight } of graph[node] || []) {
      const newDist = dist + weight;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }

  return distances;
}

/**
 * 获取最短路径（不仅仅是距离）
 */
function dijkstraWithPath(graph, start, end) {
  const distances = {};
  const previous = {};

  for (const node in graph) {
    distances[node] = Infinity;
    previous[node] = null;
  }
  distances[start] = 0;

  const pq = new MinHeap();
  pq.push([0, start]);
  const visited = new Set();

  while (!pq.isEmpty()) {
    const [dist, node] = pq.pop();

    if (visited.has(node)) continue;
    visited.add(node);

    if (node === end) break;

    for (const { node: neighbor, weight } of graph[node] || []) {
      const newDist = dist + weight;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        previous[neighbor] = node;
        pq.push([newDist, neighbor]);
      }
    }
  }

  // 重建路径
  const path = [];
  let curr = end;
  while (curr !== null) {
    path.unshift(curr);
    curr = previous[curr];
  }

  return {
    distance: distances[end],
    path: distances[end] === Infinity ? [] : path
  };
}

示例调用

javascript

// 创建带权图
//   A --1-- B
//   |       |
//   4       2
//   |       |
//   C --1-- D
const graph = {
  A: [{ node: 'B', weight: 1 }, { node: 'C', weight: 4 }],
  B: [{ node: 'A', weight: 1 }, { node: 'D', weight: 2 }],
  C: [{ node: 'A', weight: 4 }, { node: 'D', weight: 1 }],
  D: [{ node: 'B', weight: 2 }, { node: 'C', weight: 1 }]
};

// 基础示例
console.log(dijkstraSimple(graph, 'A'));
// { A: 0, B: 1, C: 4, D: 3 }

console.log(dijkstraHeap(graph, 'A'));
// { A: 0, B: 1, C: 4, D: 3 }

// 获取路径
console.log(dijkstraWithPath(graph, 'A', 'D'));
// { distance: 3, path: ['A', 'B', 'D'] }

// 边界条件：起点和终点相同
console.log(dijkstraWithPath(graph, 'A', 'A'));
// { distance: 0, path: ['A'] }

// 边界条件：单节点图
const singleGraph = { A: [] };
console.log(dijkstraSimple(singleGraph, 'A'));
// { A: 0 }

// 边界条件：不可达节点
const disconnectedGraph = {
  A: [{ node: 'B', weight: 1 }],
  B: [{ node: 'A', weight: 1 }],
  C: []
};
console.log(dijkstraSimple(disconnectedGraph, 'A'));
// { A: 0, B: 1, C: Infinity }

// 边界条件：有多条路径
const multiPath = {
  A: [{ node: 'B', weight: 1 }, { node: 'C', weight: 5 }],
  B: [{ node: 'C', weight: 2 }],
  C: []
};
console.log(dijkstraSimple(multiPath, 'A'));
// { A: 0, B: 1, C: 3 } (通过 B 更短)

复杂度分析

版本	时间复杂度	空间复杂度
简易版（数组）	O(V²)	O(V)
优先队列版	O((V+E) log V)	O(V)

4. 最小生成树

难度: ⭐⭐⭐ | 梯队: 进阶 | 标签: 贪心, 并查集

题目描述

给定连通无向图，找到边权和最小的生成树（包含所有顶点的树）。

核心思路

Kruskal 算法：

将所有边按权重排序
依次选择权重最小的边
若该边不形成环（用并查集判断），则加入 MST
直到选够 V-1 条边

代码实现

javascript

/**
 * 并查集（Union-Find）
 */
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  /**
   * 查找根节点（带路径压缩）
   */
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  /**
   * 合并两个集合（按秩合并）
   * @return {boolean} - 是否成功合并（false 表示已在同一集合）
   */
  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);

    if (px === py) return false;

    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }

    return true;
  }

  /**
   * 判断是否在同一集合
   */
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

/**
 * Kruskal 最小生成树
 * @param {number} n - 节点数量
 * @param {number[][]} edges - 边列表 [[u, v, weight], ...]
 * @return {Object} - { mst: 边列表, cost: 总权重 }
 */
function kruskal(n, edges) {
  // 按权重排序
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  const mst = [];
  let cost = 0;

  for (const [u, v, weight] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v, weight]);
      cost += weight;

      if (mst.length === n - 1) break;
    }
  }

  return { mst, cost };
}

/**
 * Prim 最小生成树（适合稠密图）
 */
function prim(n, graph) {
  // graph[u] = [{ node: v, weight: w }, ...]
  const visited = new Set();
  const mst = [];
  let cost = 0;

  // 从节点 0 开始
  const pq = new MinHeap();
  pq.push([0, 0, -1]); // [weight, node, from]

  while (!pq.isEmpty() && visited.size < n) {
    const [weight, node, from] = pq.pop();

    if (visited.has(node)) continue;
    visited.add(node);

    if (from !== -1) {
      mst.push([from, node, weight]);
      cost += weight;
    }

    for (const { node: neighbor, weight: w } of graph[node] || []) {
      if (!visited.has(neighbor)) {
        pq.push([w, neighbor, node]);
      }
    }
  }

  return { mst, cost };
}

示例调用

javascript

// 创建图
//     0
//    /|\
//   1-2-3
// 边: [0,1,1], [0,2,2], [0,3,3], [1,2,4], [2,3,5]

// Kruskal 示例
const edges = [
  [0, 1, 1],
  [0, 2, 2],
  [0, 3, 3],
  [1, 2, 4],
  [2, 3, 5]
];

console.log(kruskal(4, edges));
// { mst: [[0, 1, 1], [0, 2, 2], [0, 3, 3]], cost: 6 }

// 边界条件：单节点
console.log(kruskal(1, []));
// { mst: [], cost: 0 }

// 边界条件：两个节点
console.log(kruskal(2, [[0, 1, 5]]));
// { mst: [[0, 1, 5]], cost: 5 }

// 边界条件：不连通图
console.log(kruskal(3, [[0, 1, 1]]));
// { mst: [[0, 1, 1]], cost: 1 } (只能连接部分节点)

// 并查集单独测试
const uf = new UnionFind(5);
console.log(uf.connected(0, 1)); // false
uf.union(0, 1);
console.log(uf.connected(0, 1)); // true
uf.union(1, 2);
console.log(uf.connected(0, 2)); // true (传递性)

// 边界条件：自环
const ufSelf = new UnionFind(3);
console.log(ufSelf.union(0, 0)); // false (已在同一集合)

复杂度分析

算法	时间复杂度	空间复杂度	适用场景
Kruskal	O(E log E)	O(V)	稀疏图
Prim	O(E log V)	O(V)	稠密图

💡 图算法技巧总结

算法选择指南

问题类型	算法	适用条件
遍历/连通性	DFS/BFS	通用
有向图依赖	拓扑排序	DAG（无环有向图）
最短路径（单源）	Dijkstra	非负权边
最短路径（负权）	Bellman-Ford	可处理负权
最短路径（多源）	Floyd-Warshall	求所有点对
最小生成树	Kruskal/Prim	无向连通图

常见图问题模式

javascript

// 1. 检测环 - 拓扑排序或三色标记
// 2. 最短路径 - BFS（无权）/ Dijkstra（带权）
// 3. 连通分量 - DFS/BFS 或并查集
// 4. 二分图判断 - 染色法 BFS/DFS
// 5. 关键路径 - 拓扑排序 + DP

代码模板

javascript

// DFS 模板
function dfs(graph, start) {
  const visited = new Set();
  function helper(node) {
    if (visited.has(node)) return;
    visited.add(node);
    // 处理节点
    for (const neighbor of graph[node]) {
      helper(neighbor);
    }
  }
  helper(start);
}

// BFS 模板
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    // 处理节点
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

图算法专题 ​

📊 题目总览 ​

1. 图的表示与遍历 ​

题目描述 ​

图的表示 ​

图的遍历 ​

示例调用 ​

复杂度分析 ​

2. 拓扑排序 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

3. Dijkstra 最短路径 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

4. 最小生成树 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

💡 图算法技巧总结 ​

算法选择指南 ​

常见图问题模式 ​

代码模板 ​

图算法专题

📊 题目总览

1. 图的表示与遍历

题目描述

图的表示

图的遍历

示例调用

复杂度分析

2. 拓扑排序

题目描述

核心思路

代码实现

示例调用

复杂度分析

3. Dijkstra 最短路径

题目描述

核心思路

代码实现

示例调用

复杂度分析

4. 最小生成树

题目描述

核心思路

代码实现

示例调用

复杂度分析

💡 图算法技巧总结

算法选择指南

常见图问题模式

代码模板