一、引言——为什么图算法被低估了打开LeetCode题库图相关的题目约200道远少于数组和字符串。但面试中的图算法往往是区分会刷题和真正理解算法的分水岭。为什么因为图算法不考死记硬背它考的是抽象能力——你能不能把一个问题「翻译」成图的语言。比如一个网格中的岛屿 → 无向图的连通分量一个学期的选课安排 → 有向图的环检测本文精选两道题覆盖图算法两大核心范式200. 岛屿数量Number of Islands——图遍历DFS/BFS/并查集207. 课程表Course Schedule——拓扑排序环检测两道题都是Medium难度、大厂高频而且一道题吃透就能举一反三解决一大类问题。二、图的基础认知——面试需要知道什么在上手做题之前先建立图的核心认知框架。图的基本概念面试中你只需要知道这四个概念顶点Vertex图中的节点边Edge顶点之间的连接有向图 vs 无向图边是否有方向DAG有向无环图拓扑排序的前提图的存储方式面试中99%的场景用邻接表// 邻接表ListListInteger ListListInteger graph new ArrayList(n); for (int i 0; i n; i) graph.add(new ArrayList()); // 添加有向边 a - b graph.get(a).add(b);为什么不用邻接矩阵空间O(V²)太大V10⁴时矩阵有10⁸个元素邻接表只存实际边。两种遍历框架DFS递归/栈适合是否存在路径、连通分量BFS队列适合最短路径、拓扑排序三、200. 岛屿数量——DFS解法面试首选问题分析给一个二维网格1是陆地0是水相邻上下左右的陆地算同一个岛屿。问有多少个岛屿。输入: grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 输出: 3思路推导核心洞察每个岛屿就是一个连通分量找到所有连通分量的数量。DFS淹没法遍历网格遇到1就计数1然后从这个格子出发DFS把所有相邻的1都标记成0淹没。这样每个岛屿只会被计数一次。三语言实现Javaclass Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int m grid.length, n grid[0].length; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j, m, n); } } } return count; } private void dfs(char[][] grid, int i, int j, int m, int n) { if (i 0 || i m || j 0 || j n || grid[i][j] 0) return; grid[i][j] 0; // 淹没 dfs(grid, i - 1, j, m, n); dfs(grid, i 1, j, m, n); dfs(grid, i, j - 1, m, n); dfs(grid, i, j 1, m, n); } }Pythonclass Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 m, n len(grid), len(grid[0]) count 0 def dfs(i: int, j: int) - None: if i 0 or i m or j 0 or j n or 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 i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return countCclass Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j, m, n); } } } return count; } private: void dfs(vectorvectorchar grid, int i, int j, int m, int n) { if (i 0 || i m || j 0 || j n || grid[i][j] 0) return; grid[i][j] 0; dfs(grid, i - 1, j, m, n); dfs(grid, i 1, j, m, n); dfs(grid, i, j - 1, m, n); dfs(grid, i, j 1, m, n); } };复杂度分析时间复杂度O(M×N)每个格子最多访问一次空间复杂度O(M×N) 最坏递归栈深度面试追问递归栈溢出怎么办当网格很大如10000×10000时递归DFS可能栈溢出。解决方案改用BFS迭代队列或显式栈手动模拟递归。四、200. 岛屿数量——BFS解法面试备选思路推导用队列代替递归。每次遇到1把它入队然后逐层扩散。class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int m grid.length, n grid[0].length; int count 0; int[][] dirs {{-1,0}, {1,0}, {0,-1}, {0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; Queueint[] q new LinkedList(); q.offer(new int[]{i, j}); grid[i][j] 0; while (!q.isEmpty()) { int[] cur q.poll(); for (int[] d : dirs) { int ni cur[0] d[0], nj cur[1] d[1]; if (ni 0 ni m nj 0 nj n grid[ni][nj] 1) { grid[ni][nj] 0; q.offer(new int[]{ni, nj}); } } } } } } return count; } }复杂度分析时间复杂度O(M×N)空间复杂度O(min(M,N))队列中最多同时存对角线上的元素DFS vs BFS 对比维度DFSBFS代码简洁度⭐⭐⭐⭐⭐⭐⭐⭐空间效率差递归栈好队列大网格稳定性可能栈溢出稳定面试推荐度面试首选备选方案五、200. 岛屿数量——并查集解法进阶思路推导并查集Union-Find的核心思想每个1初始时是自己的集合相邻的1合并。最终集合的数量就是岛屿数。伪代码实现class UnionFind { int[] parent; int count; // 集合数量 public UnionFind(char[][] grid) { int m grid.length, n grid[0].length; parent new int[m * n]; count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { parent[i * n j] i * n j; count; } } } } public int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } public void union(int x, int y) { int rootX find(x), rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; count--; } } }复杂度分析时间复杂度O(M×N×α(MN))α 是阿克曼函数的反函数几乎为常数空间复杂度O(M×N)三种解法对比维度DFSBFS并查集代码量少中多空间可能栈溢出稳定稳定可扩展性低低高动态合并面试推荐⭐⭐⭐⭐⭐⭐⭐⭐六、200. 岛屿数量——变体与面试追问695. 岛屿的最大面积在DFS/BFS的同时记录每个岛屿的面积取最大值。// 只需要在DFS中返回面积 private int dfs(char[][] grid, int i, int j, int m, int n) { if (i 0 || i m || j 0 || j n || grid[i][j] 0) return 0; grid[i][j] 0; return 1 dfs(grid, i - 1, j, m, n) dfs(grid, i 1, j, m, n) dfs(grid, i, j - 1, m, n) dfs(grid, i, j 1, m, n); }463. 岛屿的周长每块陆地有4条边如果相邻也是陆地则减1条边。public int islandPerimeter(int[][] grid) { int m grid.length, n grid[0].length; int perimeter 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { perimeter 4; if (i 0 grid[i - 1][j] 1) perimeter - 2; if (j 0 grid[i][j - 1] 1) perimeter - 2; } } } return perimeter; }1905. 统计子岛屿如果网格2中岛屿的所有格子都在网格1的同一个岛屿中则是子岛屿。面试追问路线图七、207. 课程表——BFS拓扑排序面试首选问题分析给定numCourses门课和先修关系prerequisites[i] [ai, bi]先学bi才能学ai判断是否能完成所有课程。输入numCourses 2, prerequisites [[1,0]] 输出true先学0再学1 输入numCourses 2, prerequisites [[1,0],[0,1]] 输出false形成环0依赖11依赖0思路推导核心洞察将课程看作顶点先修关系看作有向边问题转化为检测有向图中是否有环。有环则无法完成无环则可以。Kahn算法BFS拓扑排序统计每个顶点的入度有多少条边指向它将入度为0的顶点入队这些课程没有前置依赖依次出队将其邻接点的入度减1如果邻接点入度变为0则入队如果最终入队过的顶点数等于总顶点数说明无环三语言实现Javaclass Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 构建邻接表和入度表 ListListInteger graph new ArrayList(numCourses); int[] inDegree new int[numCourses]; for (int i 0; i numCourses; i) graph.add(new ArrayList()); for (int[] p : prerequisites) { graph.get(p[1]).add(p[0]); // b → a inDegree[p[0]]; } // 2. 入度为0的节点入队 QueueInteger q new LinkedList(); for (int i 0; i numCourses; i) { if (inDegree[i] 0) q.offer(i); } // 3. BFS拓扑排序 int count 0; while (!q.isEmpty()) { int cur q.poll(); count; for (int next : graph.get(cur)) { inDegree[next]--; if (inDegree[next] 0) q.offer(next); } } return count numCourses; } }Pythonclass Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: # 1. 构建邻接表和入度表 graph [[] for _ in range(numCourses)] in_degree [0] * numCourses for a, b in prerequisites: graph[b].append(a) in_degree[a] 1 # 2. 入度为0的节点入队 q deque([i for i in range(numCourses) if in_degree[i] 0]) # 3. BFS拓扑排序 count 0 while q: cur q.popleft() count 1 for nxt in graph[cur]: in_degree[nxt] - 1 if in_degree[nxt] 0: q.append(nxt) return count numCoursesCclass Solution { public: bool canFinish(int numCourses, vectorvectorint prerequisites) { // 1. 构建邻接表和入度表 vectorvectorint graph(numCourses); vectorint inDegree(numCourses, 0); for (auto p : prerequisites) { graph[p[1]].push_back(p[0]); inDegree[p[0]]; } // 2. 入度为0的节点入队 queueint q; for (int i 0; i numCourses; i) { if (inDegree[i] 0) q.push(i); } // 3. BFS拓扑排序 int count 0; while (!q.empty()) { int cur q.front(); q.pop(); count; for (int next : graph[cur]) { if (--inDegree[next] 0) q.push(next); } } return count numCourses; } };复杂度分析时间复杂度O(VE)V是课程数E是先修关系数空间复杂度O(VE)存储邻接表和入度表八、207. 课程表——DFS环检测面试备选思路推导三色标记法0未访问还没遍历到1访问中在当前DFS路径上2已访问已经遍历完毕如果DFS过程中遇到状态为1的节点说明有环。class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { ListListInteger graph new ArrayList(numCourses); for (int i 0; i numCourses; i) graph.add(new ArrayList()); for (int[] p : prerequisites) graph.get(p[1]).add(p[0]); int[] visited new int[numCourses]; // 0:未访问 1:访问中 2:已访问 for (int i 0; i numCourses; i) { if (visited[i] 0 hasCycle(graph, visited, i)) return false; } return true; } private boolean hasCycle(ListListInteger graph, int[] visited, int cur) { if (visited[cur] 1) return true; // 发现环 if (visited[cur] 2) return false; // 已确认无环 visited[cur] 1; // 标记为访问中 for (int next : graph.get(cur)) { if (hasCycle(graph, visited, next)) return true; } visited[cur] 2; // 标记为已访问 return false; } }BFS vs DFS 对比维度BFSKahn算法DFS三色标记代码直观度高入度表直观中三色状态能否返回拓扑序能出队顺序需额外处理面试推荐度⭐⭐⭐⭐⭐⭐⭐⭐九、207. 课程表——变体与面试追问210. 课程表 II直接返回拓扑排序的结果出队顺序而不是只返回true/false。只需要在BFS中记录出队顺序即可。// 在BFS中记录 ListInteger order new ArrayList(); while (!q.isEmpty()) { int cur q.poll(); order.add(cur); // 记录拓扑序 // ... } return order.size() numCourses ? order : new int[0];630. 课程表 III加入时间维度每门课有持续时间duration和最晚截止时间lastDay。贪心 优先队列按截止时间排序用最大堆维护持续时间。269. 火星词典从已排序的单词列表中提取字符顺序关系构建有向图用拓扑排序还原字符顺序。这是拓扑排序在面试中的最高阶应用。面试追问方向十、总结——图算法面试的三板斧回顾本文图算法面试其实就三个核心范式第一板斧图遍历DFS/BFS解决连通性问题、路径问题、可达性问题代表题200. 岛屿数量 → 695. 最大面积 → 827. 最大人工岛第二板斧拓扑排序解决依赖关系问题、顺序约束问题代表题207. 课程表 → 210. 课程表 II → 269. 火星词典第三板斧并查集解决动态连通性问题、集合合并问题代表题200. 岛屿数量并查集版→ 684. 冗余连接 → 990. 等式方程DSA系列进度15/∞延伸阅读LeetCode 200 题解区LeetCode 207 题解区《算法导论》第22章图的基本算法LeetCode Explore图算法专题