小落叶的个人知识库

外观

📖预计阅读时长：0 分钟字数：0

代码随想录 — 图论 ​

对应 leetcode-master：图论理论基础、DFS/BFS、并查集、最短路（Dijkstra/Bellman-Ford/Floyd）、拓扑排序、最小生成树等。

一、图论在代码随想录中的位置 ​

leetcode-master 中图论部分包含：

  • 理论基础：图的存储（邻接表/邻接矩阵）、DFS/BFS 思想。
  • 卡码网题目：岛屿类（数量、面积、周长）、路径、冗余连接、最小生成树（Prim/Kruskal）、拓扑排序、最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）、A* 等。

下面只做思路与知识点提炼，便于你理解与复习；具体实现以原仓库和卡码网题目为准。

二、图的存储与遍历 ​

  • 邻接表：适合稀疏图；vector<vector<pair<int,int>>> graph 或 Map<节点, List<{邻居, 边权}>>。
  • 邻接矩阵：适合稠密图；g[i][j] 表示 i→j 的边权或是否有边。
  • DFS：用栈或递归，一条路走到底再回溯；适合「连通块、路径、环检测」。
  • BFS：用队列，一层层扩展；适合「最短步数、层序、拓扑」。
  • 岛屿类：网格图，上下左右为邻接；遍历过的格子标记（改原值或 visited），每个连通块 DFS/BFS 一次，计数即岛屿数；面积即连通块格子数；周长可对每格看四条边中哪些是边界或水。

三、并查集（Union-Find） ​

  • 作用：维护不相交集合，支持合并与查是否同集，常用于「判断是否成环」「连通分量个数」。
  • 实现：parent 数组 + find（带路径压缩）+ union（按秩或按大小合并）。
  • 冗余连接：给边列表，求删掉哪条边能使图变成树（或无向图删一条边去环）— 并查集加边，若两端已在同一集合则这条边即答案之一（或按题要求返回最后一条）。

四、拓扑排序 ​

  • 前提：有向无环图（DAG）。
  • 含义：一个顶点序列，使得每条有向边 (u,v) 都有 u 在 v 前。
  • 做法：统计入度，把所有入度为 0 的入队；每次出队一个点，把它连出去的点入度减 1，若变为 0 则入队；若最后出队数小于 n 则存在环（如 207 课程表）。
  • 应用：课程表、编译依赖、任务调度等。

五、最短路（概要） ​

算法适用复杂度（简记）
Dijkstra（朴素）非负权O(n²) 或 O(V²)
Dijkstra（堆优化）非负权O((V+E)log V)
Bellman-Ford有负权边、可判负环O(VE)
SPFA负权、Bellman-Ford 的队列优化最坏 O(VE)
Floyd全源最短路、稠密图O(V³)
  • Dijkstra：每次取当前距离最小的未确定点，用它松弛邻居；不能处理负权（会破坏「已取最小」的性质）。
  • Bellman-Ford：对边松弛 V 轮；第 V 轮若还能松弛则有负环。
  • Floyd：枚举中间点 k，用 d[i][j] = min(d[i][j], d[i][k] + d[k][j]) 更新全源。

六、最小生成树（MST） ​

  • Prim：从一点开始，每次选「当前连通块」到「外界」的最小边加入，直到连完 n-1 条边；可用堆优化。
  • Kruskal：边按权排序，从小到大加边，用并查集保证不成环，直到 n-1 条边。
  • 应用：卡码网「寻宝」等题。

七、LeetCode 常见图论题（思路） ​

  • 200 岛屿数量：网格 DFS/BFS，数连通块。
  • 994 腐烂的橘子：多源 BFS，层数即时间。
  • 207 课程表：有向图判环或输出拓扑序；拓扑排序或 DFS 染色判环。
  • 208 实现 Trie：字典树，非传统图论，但常和图论题一起出现在「图与字符串」分类。

八、图论小结 ​

问题类型首选方法
连通块、路径、回溯DFS / BFS
是否成环、连通分量并查集
依赖关系、顺序拓扑排序
非负权最短路Dijkstra（堆优化）
负权、判负环Bellman-Ford / SPFA
全源最短路Floyd
最小生成树Prim / Kruskal

建议：先掌握 DFS/BFS 写岛屿类、207 课程表；再掌握并查集模板；最短路和 MST 至少知道适用场景和一次实现（如堆优化 Dijkstra、Kruskal）。

附：核心代码模板 ​

DFS — 岛屿数量（200） ​

javascript
// JavaScript — 时间 O(m*n)
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  function dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') return;
    grid[i][j] = '0'; // 标记已访问
    dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') { count++; dfs(i, j); }
    }
  }
  return count;
}

BFS — 腐烂的橘子（994） ​

javascript
// JavaScript — 多源 BFS，时间 O(m*n)
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  const queue = [];
  let fresh = 0;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      else if (grid[i][j] === 1) fresh++;
    }
  if (!fresh) return 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let minutes = 0;
  while (queue.length) {
    const size = queue.length;
    for (let k = 0; k < size; k++) {
      const [x, y] = queue.shift();
      for (const [dx, dy] of dirs) {
        const nx = x + dx, ny = y + dy;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1) {
          grid[nx][ny] = 2;
          fresh--;
          queue.push([nx, ny]);
        }
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes - 1 : -1;
}

并查集模板 ​

javascript
// JavaScript
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];
  }
  union(x, y) {
    const px = this.find(x), 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;
  }
}
python
# Python — 并查集
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

拓扑排序 — 课程表（207） ​

javascript
// JavaScript — 时间 O(V+E)
function canFinish(numCourses, prerequisites) {
  const inDeg = new Array(numCourses).fill(0);
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDeg[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) queue.push(i);
  let count = 0;
  while (queue.length) {
    const node = queue.shift();
    count++;
    for (const next of graph[node]) {
      if (--inDeg[next] === 0) queue.push(next);
    }
  }
  return count === numCourses;
}

Copyright@ 2024 Luoye Zero