1. 图算法从LeetCode小白到高手的必经之路如果你刚开始刷LeetCode看到“图”这个字眼是不是有点发怵觉得它比链表、二叉树要抽象得多代码写起来也复杂别担心这种感觉我太懂了。十年前我刚接触算法时也觉得图算法是座难以翻越的大山。但实战下来我发现图算法其实有很强的套路性一旦掌握了几个核心“武器库”很多难题都能迎刃而解。图算法在面试和工程中到底有多重要我举两个身边的例子。我的一位同事面试国内一家大厂时连续三轮都遇到了图相关的题目从简单的连通性判断到复杂的最短路径优化最终顺利拿到了offer。另一个例子是我们团队之前做的一个社交网络推荐功能核心就是分析用户关系图找出潜在的好友这背后用的就是图的连通分量和社区发现算法。所以无论你是为了求职面试还是为了解决实际工程问题图算法都是一项绕不开的硬核技能。这篇文章我就把自己在LeetCode上刷了上百道图题的经验以及在实际项目中应用的体会系统地分享给你。我们不搞枯燥的理论堆砌就聚焦在连通性和最短路径这两个最核心、最高频的考点上。我会用最直白的语言配合大量代码示例带你从DFS/BFS/并查集这些基础操作一直深入到状态压缩、拓扑排序等高级技巧。目标很简单让你看完就能上手遇到图题不再心虚。2. 连通性判断你的图是“一盘散沙”还是“铁板一块”连通性问题是图论中最基础的问题之一简单说就是判断图中的节点是否能通过边相互到达。这听起来简单但在LeetCode里却能变出各种花样。核心的解题“三板斧”就是深度优先搜索DFS、广度优先搜索BFS和并查集Union-Find。选对工具事半功倍。2.1 DFS/BFS最直观的“地毯式搜索”DFS和BFS是探索图的两种基本策略就像走迷宫。DFS是一条路走到黑碰壁再回头BFS是一圈一圈向外扩散。对于连通性问题两者常常可以互换。拿经典的LeetCode 547. 省份数量来说题目给了你一个城市的邻接矩阵问你一共有多少个省份连通分量。我第一次做这题时直觉就是DFS从一个城市出发把所有能直接间接到达的城市都标记为“已访问”这就找到了一个省。然后找下一个未访问的城市重复这个过程。class Solution: def findCircleNum(self, isConnected: List[List[int]]) - int: n len(isConnected) visited [False] * n province_count 0 def dfs(city: int): # 标记当前城市已访问 visited[city] True # 遍历所有城市找到与当前城市相连且未访问的继续深搜 for neighbor in range(n): if isConnected[city][neighbor] 1 and not visited[neighbor]: dfs(neighbor) for i in range(n): if not visited[i]: # 发现一个新的未访问城市意味着发现一个新的省份 dfs(i) province_count 1 return province_count这里有个小技巧因为题目给的是邻接矩阵我们不需要额外建图直接遍历矩阵行即可。DFS递归栈的深度最大可能是城市数量n所以空间复杂度是O(n)时间复杂度是O(n²)因为最坏要检查每个矩阵元素。BFS的写法也很类似只是把递归栈换成队列from collections import deque class Solution: def findCircleNum(self, isConnected: List[List[int]]) - int: n len(isConnected) visited [False] * n count 0 for i in range(n): if not visited[i]: count 1 queue deque([i]) visited[i] True while queue: city queue.popleft() for neighbor in range(n): if isConnected[city][neighbor] 1 and not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return count实战中如果图非常“深”比如一条长链DFS递归可能导致栈溢出这时用BFS更安全。反之如果图很“宽”BFS队列可能占用更多内存。对于简单的连通性判断两者效率差不多选你顺手的使用就行。2.2 并查集高效管理“朋友圈”的神器DFS/BFS虽然直观但每次查询两个节点是否连通都需要遍历在需要频繁进行连通性判断的场景下效率不高。这时就该并查集登场了。它的思想非常巧妙把相互连通的节点放到同一个集合里每个集合选一个“老大”代表元。判断两个节点是否连通就看他们的“老大”是不是同一个人合并两个连通区域就是把其中一个集合的“老大”认另一个集合的“老大”做大哥。还是“省份数量”这道题用并查集怎么写我们初始化时每个城市自成一家。然后遍历邻接矩阵如果两个城市相连就把它们所在的集合合并。最后统计有多少个不同的“老大”就是省份的数量。class UnionFind: def __init__(self, n): self.parent list(range(n)) # 初始时每个人的父亲是自己 self.rank [1] * n # 秩用于优化合并 self.count 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): rootX self.find(x) rootY self.find(y) if rootX rootY: return # 已经在同一集合 # 按秩合并将矮树合并到高树上保持平衡 if self.rank[rootX] self.rank[rootY]: rootX, rootY rootY, rootX self.parent[rootY] rootX if self.rank[rootX] self.rank[rootY]: self.rank[rootX] 1 self.count - 1 # 合并后连通分量减少一个 class Solution: def findCircleNum(self, isConnected: List[List[int]]) - int: n len(isConnected) uf UnionFind(n) for i in range(n): for j in range(i 1, n): # 矩阵是对称的遍历一半即可 if isConnected[i][j] 1: uf.union(i, j) return uf.count并查集的两个核心优化——路径压缩和按秩合并——能让每次操作的均摊时间复杂度接近常数级O(α(n))其中α是增长极慢的反阿克曼函数。这在处理大规模图比如数万个节点时优势巨大。我印象很深的是在做LeetCode 952. 按公因数计算最大组件的大小时需要根据数字间的公因数关系建图。如果两两数字去算公因数再DFS铁定超时。而用并查集对每个数字枚举其因数并进行合并效率就高得多。2.3 实战进阶封闭岛屿与恶意软件传播掌握了基础工具我们来看两个稍微复杂点的连通性问题体会一下如何组合运用这些技术。LeetCode 1254. 统计封闭岛屿的数目这道题在DFS的基础上增加了一个条件岛屿必须完全被水1包围接触边界的不算。很多新手在这里会踩坑在DFS过程中一旦碰到边界就立刻返回False认为不是封闭岛屿。但这样可能提前终止搜索导致部分陆地没有被正确标记从而被重复计算。正确的做法是设置一个标志位。在DFS遍历一个岛屿的所有陆地时如果遇到边界只标记“这个岛屿不是封闭的”但继续完成整个岛屿的遍历把所有陆地都标记为已访问比如改成水避免后续重复访问。class Solution: def closedIsland(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) if rows 3 or cols 3: # 至少3x3才可能有封闭岛屿 return 0 def dfs(x, y): # 如果越界说明触碰到地图边界这个岛屿不封闭 if x 0 or x rows or y 0 or y cols: return False # 如果是水返回True可视为边界 if grid[x][y] 1: return True # 当前是未访问的陆地将其标记为已访问改为水 grid[x][y] 1 # 关键四个方向都必须搜索完不能中途返回 # 用标志位记录四个方向是否都封闭 is_closed True for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]: if not dfs(x dx, y dy): # 如果任何一个方向碰到边界 is_closed False # 岛屿就不封闭 return is_closed # 返回这个岛屿是否封闭 count 0 for i in range(rows): for j in range(cols): if grid[i][j] 0: # 发现一块新陆地 if dfs(i, j): # 如果DFS返回True说明是封闭岛屿 count 1 return count另一个经典问题是LeetCode 924. 尽量减少恶意软件的传播。题目抽象一下一个网络中有一些初始感染节点病毒会沿着边传播到所有连通节点。如果只能移除一个初始感染节点问移除哪个能使最终被感染的节点总数最少这题的关键在于理解如果在一个连通分量里有多个初始感染节点那么移除其中任何一个病毒还是会从其他感染节点传遍整个分量于事无补。所以我们只关心那些独占一个连通分量的初始感染节点。移除它们才能拯救整个分量的节点。解题步骤很清晰用DFS或并查集找出所有连通分量并给每个分量染色编号。统计每个连通分量的大小节点数。统计每个连通分量中包含的初始感染节点数量。遍历初始感染节点只考虑那些所在连通分量中感染节点数量为1的节点。选择能拯救节点数最多即其所在连通分量大小最大的那个。如果有多个返回索引最小的。class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) - int: n len(graph) # 步骤1: DFS染色标记连通分量 colors [-1] * n color 0 def dfs(node, color): colors[node] color for neighbor in range(n): if graph[node][neighbor] 1 and colors[neighbor] -1: dfs(neighbor, color) for i in range(n): if colors[i] -1: dfs(i, color) color 1 # 步骤2: 计算每个颜色连通分量的大小 size [0] * color for c in colors: size[c] 1 # 步骤3: 计算每个颜色中初始感染节点的数量 color_count [0] * color for node in initial: color_count[colors[node]] 1 # 步骤4: 找出最优解 ans min(initial) # 默认返回索引最小的 max_saved -1 for node in initial: c colors[node] if color_count[c] 1: # 只考虑独占一个分量的感染节点 if size[c] max_saved: max_saved size[c] ans node elif size[c] max_saved and node ans: ans node return ans这种“染色统计”的思路在解决网络感染、社区划分等问题时非常实用。它把复杂的全局传播问题分解成了对独立连通分量的分析大大简化了思考难度。3. 最短路径找到两点之间的“最优解”如果说连通性关心的是“能不能到”那么最短路径关心的就是“怎么走最快/最省”。这是图算法中另一大类核心问题在导航、网络路由、任务调度等领域应用极广。LeetCode上相关题目也很多从单源最短路径到全源最短路径从无权图到带权图考察得非常全面。3.1 BFS无权图的“最短步数”法宝在边的权值都相同通常视为1的图上求最短路径最简单的方法就是BFS。因为BFS天然按距离源点的层次遍历第一次到达目标节点的路径一定是最短的。LeetCode 847. 访问所有节点的最短路径是一个经典的变体它要求访问所有节点可以重复访问节点和边。这相当于在状态空间中进行搜索状态定义为(当前节点, 已访问节点集合)。直接暴力BFS状态会爆炸因为节点集合有2^n种可能。这里就需要用到状态压缩——用一个整数的二进制位来表示哪些节点已访问。例如有4个节点访问了节点0和2状态可以用二进制0101十进制5表示。from collections import deque class Solution: def shortestPathLength(self, graph: List[List[int]]) - int: n len(graph) # 目标状态所有n位都是1即 (1 n) - 1 target (1 n) - 1 # 队列元素(当前节点, 已访问状态掩码, 路径长度) queue deque() # 访问标记避免重复状态。seen[node][mask] seen [[False] * (1 n) for _ in range(n)] # 初始化可以从任何一个节点出发 for i in range(n): mask 1 i queue.append((i, mask, 0)) seen[i][mask] True while queue: node, mask, dist queue.popleft() if mask target: # 所有节点都已访问 return dist for neighbor in graph[node]: new_mask mask | (1 neighbor) # 将邻居节点加入已访问集合 if not seen[neighbor][new_mask]: seen[neighbor][new_mask] True queue.append((neighbor, new_mask, dist 1)) return -1 # 理论上不会走到这里因为题目保证连通这个解法的时间复杂度是O(n * 2^n)因为最多有n * 2^n种状态。空间复杂度也一样。当n12时状态数约为12*409649152是可接受的。这是BFS结合状态压缩的典型应用在解决需要记录访问历史的图搜索问题时非常有效。3.2 Dijkstra算法带权图的“单源最优”解当图中的边带有不同的权重如距离、时间、成本时BFS就不适用了。这时需要Dijkstra算法。它的核心思想是贪心每次从“未确定最短距离”的节点中选择一个距离起点最近的节点然后用它来更新其邻居的距离。LeetCode上有一道变形题882. 细分图中的可到达节点。题目在原始图的边上增加了许多“细分节点”问在最大移动步数内能从节点0到达多少节点包括原始节点和细分节点。我们可以把细分节点看作边上的权重。先使用Dijkstra算法求出从节点0到所有原始节点的最短距离然后对于每条边计算从两端点出发还能“覆盖”多少个细分节点。import heapq class Solution: def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) - int: # 1. 建图 graph [[] for _ in range(n)] for u, v, cnt in edges: graph[u].append((v, cnt 1)) # 权重是细分节点数1 graph[v].append((u, cnt 1)) # 2. Dijkstra求最短距离 dist [float(inf)] * n dist[0] 0 pq [(0, 0)] # (距离, 节点) while pq: d, node heapq.heappop(pq) if d dist[node]: continue for neighbor, weight in graph[node]: new_dist d weight if new_dist dist[neighbor]: dist[neighbor] new_dist heapq.heappush(pq, (new_dist, neighbor)) # 3. 统计可达的原始大节点 ans sum(1 for d in dist if d maxMoves) # 4. 统计每条边上可达的细分节点 for u, v, cnt in edges: # 从u端还能走的步数 a max(maxMoves - dist[u], 0) if dist[u] maxMoves else 0 # 从v端还能走的步数 b max(maxMoves - dist[v], 0) if dist[v] maxMoves else 0 # 两边加起来最多覆盖cnt个细分节点 ans min(a b, cnt) return ans这里使用优先队列最小堆来优化Dijkstra将时间复杂度从O(V²)降到了O(E log V)。关键点在于理解细分节点的可达数取决于从这条边两个端点出发在扣除到达端点所需步数后各自还能富余多少步。两者之和不能超过边上细分节点的总数。3.3 Floyd算法与动态规划多源与状态压缩对于需要求所有点对之间最短路径的问题或者像上面“访问所有节点最短路径”的另一种思路我们可以用Floyd算法或结合动态规划。Floyd算法基于动态规划定义d[k][i][j]为只经过前k个节点作为中间节点时从i到j的最短路径。通过三重循环逐步松弛最终得到所有点对的最短路径。其核心转移方程是d[i][j] min(d[i][j], d[i][k] d[k][j])。对于“访问所有节点最短路径”问题除了BFS状态压缩还可以用状压DP。定义dp[u][mask]为从任意节点出发最终停在节点u并且已经访问过mask所表示节点集合的最短路径长度。那么状态转移就是dp[u][mask] min(dp[v][mask ^ (1u)] dist[v][u])其中v是mask中已访问的另一个节点dist[v][u]是v到u的最短距离可以用Floyd预处理。最后答案就是min(dp[u][(1n)-1])。class Solution: def shortestPathLength(self, graph: List[List[int]]) - int: n len(graph) # 用Floyd预处理所有点对最短距离这里图是无权图距离为1或无穷 INF n * n dist [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] 0 for j in graph[i]: dist[i][j] 1 for k in range(n): for i in range(n): for j in range(n): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]) # 状压DP dp [[INF] * (1 n) for _ in range(n)] for i in range(n): dp[i][1 i] 0 # 从自己出发只访问自己距离为0 for mask in range(1 n): for u in range(n): if not (mask (1 u)): continue for v in range(n): if (mask (1 v)) and u ! v: dp[u][mask] min(dp[u][mask], dp[v][mask ^ (1 u)] dist[v][u]) ans min(dp[u][(1 n) - 1] for u in range(n)) return ans这种DP解法的时间复杂度是O(n² * 2^n)在n较小比如15时比BFS更优。它体现了将路径问题转化为状态机问题的思想在很多需要遍历特定集合的优化问题中都有应用。4. 拓扑排序与关键路径处理有依赖关系的“任务调度”很多实际问题中节点之间存在依赖关系比如课程A必须先于课程B学习任务X必须在任务Y完成后才能开始。这种关系可以用**有向无环图DAG**来表示。拓扑排序和关键路径分析是处理这类问题的利器。4.1 拓扑排序给任务排个“先来后到”拓扑排序能将DAG中的所有顶点排成一个线性序列使得对于任何有向边(u, v)u在序列中都出现在v之前。算法通常使用BFSKahn算法实现不断移除入度为0的节点并更新其邻居的入度。LeetCode 1136. 并行课程 III是一个很好的例子有n门课每门课有修读时间并且有先修关系。问修完所有课最少需要多少时间你可以同时上任意多门课但必须等先修课都完成。这其实是一个关键路径问题。一门课的最早完成时间等于其所有先修课中最晚的完成时间加上这门课本身的耗时。整个项目的最短完成时间就是所有课程完成时间的最大值。from collections import deque, defaultdict class Solution: def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) - int: # 建图并记录入度和逆邻接表用于找前置课程 graph defaultdict(list) indegree [0] * (n 1) prev defaultdict(list) # 逆邻接表课程 - 它的所有先修课 for prev_course, next_course in relations: graph[prev_course].append(next_course) prev[next_course].append(prev_course) indegree[next_course] 1 # dp[i] 表示完成课程i的最早时间 dp [0] * (n 1) queue deque() # 初始化入度为0的课程可以立刻开始 for i in range(1, n 1): if indegree[i] 0: queue.append(i) dp[i] time[i - 1] # 注意time索引从0开始 while queue: course queue.popleft() # 遍历该课程的后继课程 for next_course in graph[course]: indegree[next_course] - 1 # 关键后继课程的最早开始时间是所有先修课完成时间的最大值 # 这里在入度减为0时才计算是因为此时所有先修课都已处理完 if indegree[next_course] 0: # 计算所有先修课中最晚的完成时间 max_prev_time 0 for p in prev[next_course]: max_prev_time max(max_prev_time, dp[p]) dp[next_course] max_prev_time time[next_course - 1] queue.append(next_course) # 答案是所有课程完成时间的最大值 return max(dp)这个解法巧妙地将拓扑排序和动态规划结合了起来。dp数组在节点入度变为0时更新确保了计算顺序符合依赖关系。时间复杂度是O(VE)。4.2 有向图中带权值的复杂问题拓扑排序还能解决更复杂的问题比如LeetCode 1857. 有向图中最大颜色值。给定一个有向图每个节点有一个颜色小写字母求图中任意路径上出现次数最多的颜色的最大数目。如果图中有环返回-1。这题需要我们在保证图是DAG无环的前提下进行动态规划。定义dp[u][c]为以节点u结尾的路径中颜色c出现的最大次数。状态转移方程为dp[u][c] max(dp[pre][c]) (color[u] c ? 1 : 0)其中pre是u的所有前驱节点。我们可以用拓扑排序的顺序来更新dp值确保在计算dp[u]时其所有前驱节点的dp值都已计算完毕。from collections import deque, defaultdict class Solution: def largestPathValue(self, colors: str, edges: List[List[int]]) - int: n len(colors) graph defaultdict(list) indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 # dp[i][j]: 以节点i结尾的路径中颜色j0-25出现的最大次数 dp [[0] * 26 for _ in range(n)] queue deque() # 初始化入度为0的节点 for i in range(n): if indegree[i] 0: queue.append(i) dp[i][ord(colors[i]) - ord(a)] 1 visited 0 ans 0 while queue: u queue.popleft() visited 1 ans max(ans, max(dp[u])) # 更新全局答案 for v in graph[u]: indegree[v] - 1 # 更新v的dp值继承所有前驱路径中的最大值 for c in range(26): dp[v][c] max(dp[v][c], dp[u][c]) # 加上v节点自身的颜色 color_idx ord(colors[v]) - ord(a) dp[v][color_idx] max(dp[v][color_idx], dp[u][color_idx] 1) if indegree[v] 0: queue.append(v) # 如果访问过的节点数不等于总节点数说明有环 return ans if visited n else -1这个解法的时间复杂度是O((VE)26)因为每个节点都要维护一个长度为26的数组。空间复杂度是O(V26)。它展示了如何在拓扑排序的框架下进行多维度的动态规划是处理DAG上复杂统计问题的通用思路。5. 最小生成树与并查集高级应用最小生成树MST是连接图中所有节点且总边权最小的树。Kruskal和Prim是两大经典算法其中Kruskal算法因其简单和易于实现在LeetCode中更常见。它的核心是贪心按边权从小到大排序每次选择一条不会构成环的边加入生成树直到选了n-1条边。判断是否成环正是并查集的用武之地。5.1 关键边与伪关键边LeetCode 1489. 找到最小生成树的关键边和伪关键边这道题将MST和并查集的应用提升到了一个更深的层次。题目要求找出所有关键边删除它会导致所有MST权重增加和伪关键边存在于某些MST中但非所有。暴力思路是先计算标准MST的权重std_weight。然后对于每条边判断是否为关键边强制排除这条边重新计算MST权重。如果无法形成MST图不连通或权重变大则是关键边。判断是否为伪关键边在非关键边中强制包含这条边重新计算MST权重。如果权重等于std_weight则是伪关键边。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return True class Solution: def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) - List[List[int]]: m len(edges) # 给边加上原始索引方便最后返回答案 for i in range(m): edges[i].append(i) # 按权重排序 edges.sort(keylambda x: x[2]) # 计算标准MST权重 def kruskal(blocked_edge_idxNone, must_include_edge_idxNone): uf UnionFind(n) weight 0 edges_used 0 # 如果必须包含某条边先加上 if must_include_edge_idx is not None: for u, v, w, idx in edges: if idx must_include_edge_idx: if uf.union(u, v): weight w edges_used 1 break # 遍历所有边 for u, v, w, idx in edges: if idx blocked_edge_idx: continue # 跳过被禁用的边 if uf.union(u, v): weight w edges_used 1 if edges_used n - 1: break # 如果生成的树边数不足n-1说明图不连通 if edges_used n - 1: return float(inf) return weight std_weight kruskal() critical [] pseudo_critical [] for i in range(m): # 测试是否为关键边禁用这条边 if kruskal(blocked_edge_idxi) std_weight: critical.append(edges[i][3]) # 添加原始索引 continue # 关键边不可能是伪关键边 # 测试是否为伪关键边强制包含这条边 if kruskal(must_include_edge_idxi) std_weight: pseudo_critical.append(edges[i][3]) return [critical, pseudo_critical]这个解法虽然调用了多次Kruskal但每次都是O(E log E)或O(E α(V))在题目限制下n 100是可以接受的。它清晰地展示了如何利用并查集来动态测试边的必要性是理解MST性质的绝佳练习题。5.2 并查集在复杂约束下的应用并查集不仅能判断连通性还能处理带有复杂约束的连通问题。比如LeetCode 1627. 带阈值的图的连通性两个节点连通的条件是它们存在一个公因数大于某个阈值。直接两两判断会超时。巧妙的做法是对于每个大于阈值的数z把所有z的倍数在1~n范围内用并查集合并起来。因为如果x和y都是z的倍数那么z就是它们的一个公因数且z threshold满足连通条件。这样我们只需要枚举z和其倍数复杂度是O(n log n)级别的调和级数而不是O(n²)。class UnionFind: # ... 并查集实现同上 ... class Solution: def areConnected(self, n: int, threshold: int, queries: List[List[int]]) - List[bool]: if threshold 0: # 如果阈值为0任何两个数都有公因数1但1不大于0所以不满足 # 实际上当阈值为0时题目退化为判断是否连通通常全连通 # 这里根据题意1和任何数公因数为1不大于0所以应该不连通 # 但示例显示阈值为0时全连通。我们按常规并查集处理从1开始合并即可。 # 更稳妥的实现是特殊处理threshold0的情况。 uf UnionFind(n1) for i in range(1, n1): for j in range(2*i, n1, i): uf.union(i, j) else: uf UnionFind(n1) # 从threshold1开始枚举可能的公因数z for z in range(threshold 1, n 1): # 将所有z的倍数合并 for multiple in range(2*z, n1, z): uf.union(z, multiple) ans [] for a, b in queries: ans.append(uf.find(a) uf.find(b)) return ans这种“枚举因数/倍数”来建立连接的思想在解决数论相关的图论问题时非常高效。它避免了直接检查每对节点而是通过中间桥梁公因数来间接建立连通性。6. 状态压缩与记忆化搜索应对指数级状态空间当问题规模较小通常n 20但状态复杂时状态压缩和记忆化搜索是强大的组合拳。状态压缩通常用一个整数的二进制位来表示一个集合将集合操作转化为位运算极大提升效率。6.1 并行课程与最小学期数LeetCode 1494. 并行课程 II要求在最少的学期内修完所有课程每学期最多上k门课且必须先修课已修完。n最大为15提示我们可以用状态压缩DP。定义dp[mask]为修完mask所表示课程集合所需的最小学期数。初始状态dp[0]0。对于每个状态mask我们找出所有在当前状态下可以学习的课程先修课已满足且未修得到集合canTake。然后我们需要从canTake中选出最多k门课来学习枚举canTake的所有子集subset大小k那么新状态mask | subset就可以从dp[mask] 1转移而来。class Solution: def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) - int: # pre[i]的二进制位表示课程i的先修课集合 pre [0] * n for prev_c, next_c in relations: # 课程编号从1开始转为从0开始 pre[next_c - 1] | 1 (prev_c - 1) total_states 1 n INF n 1 dp [INF] * total_states dp[0] 0 # 预计算每个状态中1的个数这学期上的课数 pop_count [0] * total_states for i in range(1, total_states): pop_count[i] pop_count[i 1] (i 1) for mask in range(total_states): if dp[mask] n: # 不可达状态 continue # 找出在当前mask状态下可以学习的课程 can_take 0 for i in range(n): # 如果课程i还没学且它的所有先修课都已学完 if not (mask (1 i)) and (pre[i] mask) pre[i]: can_take | 1 i # 枚举can_take的所有子集选择大小不超过k的子集进行学习 # 技巧sub can_take; sub (sub - 1) can_take 可以枚举所有子集 sub can_take while sub: if pop_count[sub] k: next_mask mask | sub dp[next_mask] min(dp[next_mask], dp[mask] 1) sub (sub - 1) can_take return dp[total_states - 1]这个解法的时间复杂度是O(3^n)因为对于每个状态mask需要枚举其可学习集合的所有子集。当n15时状态数约3.2万子集枚举虽然是指数级但在约束下仍可接受。它展示了如何用位运算高效地表示和操作课程集合是状压DP的典型应用。6.2 猫和老鼠博弈与记忆化搜索LeetCode 913. 猫和老鼠是一道Hard题堪称图论博弈问题的巅峰。两个玩家在无向图上移动猫不能进洞有平局规则。问双方都最优玩法下老鼠是否能赢。这种博弈问题通常用记忆化搜索来解决。状态定义为(回合数, 老鼠位置, 猫位置)。由于状态可能重复出现形成环我们需要记录每个状态的结果老鼠赢、猫赢或平局。根据游戏规则进行DFS并利用记忆化避免重复计算。from functools import lru_cache class Solution: def catMouseGame(self, graph: List[List[int]]) - int: n len(graph) lru_cache(maxsizeNone) def dfs(t, mouse, cat): 返回当前状态的结果。 0: 平局1: 老鼠赢2: 猫赢 t: 回合数0表示老鼠的回合1表示猫的回合 if t 2 * n: # 平局条件状态重复出现 return 0 if mouse 0: return 1 # 老鼠进洞 if mouse cat: return 2 # 猫抓到老鼠 if t % 2 0: # 老鼠的回合 # 老鼠想赢所以只要有一个选择能赢它就选那个 best_result 2 # 默认最坏情况是猫赢 for next_mouse in graph[mouse]: result dfs(t 1, next_mouse, cat) if result 1: # 老鼠找到必胜策略 return 1 if result 0: # 至少有个平局的选择 best_result 0 return best_result else: # 猫的回合 # 猫想赢所以只要有一个选择能赢它就选那个 best_result 1 # 默认最坏情况是老鼠赢 for next_cat in graph[cat]: if next_cat 0: # 猫不能进洞 continue result dfs(t 1, mouse, next_cat) if result 2: # 猫找到必胜策略 return 2 if result 0: # 至少有个平局的选择 best_result 0 return best_result return dfs(0, 1, 2)这个解法用了Python的lru_cache自动实现记忆化。关键点在于老鼠回合它优先寻找能直接获胜的走法其次寻找能导致平局的走法最坏情况才是猫赢。猫回合同理。由于状态空间是O(n² * 2n)级别在n 50时可以通过。这类博弈问题考察的是对状态空间的全面分析和最优策略的模拟需要仔细处理平局条件这里用回合数上限2n来判定因为超过2n步大概率是循环了。7. 总结与实战心得刷了这么多图算法题我最大的感受是图论问题虽然变化多端但核心思想就那么几个。DFS/BFS用于遍历和搜索并查集管理连通分量拓扑排序处理依赖关系最短路径算法找最优解状态压缩应对小规模复杂状态。真正难的是如何识别问题本质并选择、组合合适的工具。在实际面试或竞赛中我建议按以下步骤思考建模把问题抽象成图。节点是什么边是什么是有向还是无向带权还是无权定性这属于哪类问题连通性、最短路径、拓扑排序、最小生成树、还是网络流选型根据数据规模选择算法。n小20考虑状压n中等考虑DFS/BFS/并查集/Dijkstran大考虑优化或近似算法。实现套用模板但注意边界条件和优化点比如并查集的路径压缩。验证用简单例子测试尤其是边界情况空图、单节点、环等。最后分享一个我自己的教训早期我总想追求最“优美”的解法结果往往把简单问题复杂化。后来我意识到在面试或限时比赛中正确性和可读性远比巧妙性重要。先用最稳妥的方法比如暴力DFS确保做出来如果有时间再优化。图算法尤其如此一个清晰的、哪怕稍慢的解法也比一个精巧但容易出错的解法得分更高。希望这篇长文能帮你建立起图算法的知识框架。真正的掌握离不开动手实践建议你把文中提到的经典题目都在LeetCode上亲手敲一遍遇到卡壳的地方再回来看解析。坚持下去你会发现图算法从“拦路虎”慢慢变成了“送分题”。