LeetCode图算法实战：从省份数量到猫和老鼠的5种必会解法

LeetCode图算法精要5种核心解法与实战技巧1. 图算法基础与高频问题分类图算法是算法面试中的核心考察点掌握常见解题模式能显著提升解题效率。我们将LeetCode高频图问题分为以下几类连通性问题省份数量、封闭岛屿统计路径问题最短路径、最大路径价值拓扑排序课程安排、继承顺序并查集应用冗余连接、保证图可遍历特殊博弈问题猫和老鼠# 邻接表表示法示例 graph { 0: [1, 2], 1: [0, 3], 2: [0], 3: [1] }关键指标对比算法类型时间复杂度空间复杂度适用场景DFS/BFSO(VE)O(V)连通性、路径查找DijkstraO(ElogV)O(V)带权最短路径拓扑排序O(VE)O(V)依赖关系排序并查集O(α(n))O(n)动态连通性2. 深度优先搜索的进阶应用DFS不仅是简单的遍历工具通过巧妙设计能解决复杂图问题封闭岛屿统计技巧边界陆地标记为非封闭采用染色法标记已访问节点使用标志位避免提前终止递归def closedIsland(grid): def dfs(x, y): if x 0 or y 0 or x len(grid) or y len(grid[0]): return False if grid[x][y] ! 0: return True grid[x][y] 1 # 标记为已访问 res True for dx, dy in directions: res dfs(xdx, ydy) return res directions [(-1,0),(1,0),(0,-1),(0,1)] count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 0 and dfs(i, j): count 1 return count易错点警示忘记处理边界条件导致错误标记递归时未及时更新访问状态错误使用或运算替代与运算判断封闭性3. 并查集的优化实践并查集是解决连通性问题的利器优化版本能显著提升性能带权并查集实现class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [1] * size 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): x_root self.find(x) y_root self.find(y) if x_root y_root: return False if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 return True实战案例省份数量def findCircleNum(isConnected): n len(isConnected) uf UnionFind(n) for i in range(n): for j in range(i1, n): if isConnected[i][j] 1: uf.union(i, j) return len(set(uf.find(i) for i in range(n)))性能优化技巧路径压缩使find操作接近O(1)按秩合并保持树结构平衡即时更新连通分量计数4. 拓扑排序的典型场景拓扑排序特别适合处理依赖关系问题以下是关键实现细节课程安排问题解法def canFinish(numCourses, prerequisites): adj [[] for _ in range(numCourses)] indegree [0] * numCourses for dest, src in prerequisites: adj[src].append(dest) indegree[dest] 1 queue [i for i in range(numCourses) if indegree[i] 0] count 0 while queue: node queue.pop() count 1 for neighbor in adj[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return count numCourses并行课程III的DP解法def minimumTime(n, relations, time): adj [[] for _ in range(n1)] rev_adj [[] for _ in range(n1)] indegree [0]*(n1) for prev, next_ in relations: adj[prev].append(next_) rev_adj[next_].append(prev) indegree[next_] 1 dp [0]*(n1) queue [i for i in range(1,n1) if indegree[i]0] for node in queue: dp[node] time[node-1] res 0 while queue: node queue.pop(0) res max(res, dp[node]) for neighbor in adj[node]: max_prev 0 for prev in rev_adj[neighbor]: max_prev max(max_prev, dp[prev]) dp[neighbor] max_prev time[neighbor-1] indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return res5. 状态压缩与记忆化搜索对于复杂博弈问题如猫和老鼠状态压缩是必要手段关键实现要素定义三维状态 (回合数, 猫位置, 鼠位置)使用记忆化存储已计算状态考虑平局条件的终止判断def catMouseGame(graph): n len(graph) memo [[[-1]*n for _ in range(n)] for __ in range(2*n)] def dfs(k, a, b): if k 2*n*n: return 0 if a 0: return 1 if a b: return 2 if memo[k][a][b] ! -1: return memo[k][a][b] if k % 2 0: # 鼠的回合 draw False for nei in graph[a]: res dfs(k1, nei, b) if res 1: memo[k][a][b] 1 return 1 if res 0: draw True memo[k][a][b] 0 if draw else 2 else: # 猫的回合 draw False for nei in graph[b]: if nei 0: continue res dfs(k1, a, nei) if res 2: memo[k][a][b] 2 return 2 if res 0: draw True memo[k][a][b] 0 if draw else 1 return memo[k][a][b] return dfs(0, 1, 2)优化方向使用位运算压缩状态表示提前终止不必要的搜索分支对称性剪枝减少状态空间掌握这五种核心解法后面对LeetCode中90%的图算法问题都能找到解决思路。实际解题时需要根据问题特点灵活组合这些方法并注意边界条件的处理。