1. 什么时候想到图论
图论题不一定真的出现“图”这个词。只要问题中存在一批对象,以及对象之间的连接、移动、依赖或转换关系,就可以考虑把它建模成图:
1 2 3
| 对象 → 节点 对象之间的关系 → 边 从一个对象移动到另一个 → 沿边访问
|
常见题目信号:
| 题目描述 |
常用方法 |
| 能否从起点到终点、所有连通块 |
DFS、BFS、并查集 |
| 二维地图扩散、岛屿、迷宫 |
网格 DFS / BFS |
| 最少步数、边权都相同 |
BFS |
| 动态合并集合、判断是否成环 |
并查集 |
| 课程依赖、任务先后关系 |
拓扑排序 |
| 非负权最短路 |
Dijkstra + 小根堆 |
| 可能有负权边 |
Bellman-Ford |
| 所有节点两两最短路 |
Floyd-Warshall |
| 用最小代价连接所有节点 |
最小生成树 |
| 总从当前最低边界向外扩展 |
小根堆 + BFS |
选择算法之前先回答四个问题:
- 图是有向还是无向?
- 边是否带权?权重能否为负?
- 求的是可达性、连通性、最短路,还是连接所有节点的最小代价?
- 图是显式边集合,还是二维网格隐式形成的图?
2. 图的表示:先决定节点怎样找到邻居
2.1 邻接表
邻接表为每个节点保存可以直接到达的邻居,适合边比较少的稀疏图。
1 2 3 4 5 6 7 8 9 10 11
| def build_undirected_graph( node_count: int, edges: list[list[int]], ) -> list[list[int]]: graph = [[] for _ in range(node_count)]
for first, second in edges: graph[first].append(second) graph[second].append(first)
return graph
|
有向图只加入一个方向:
1 2 3 4 5 6 7 8 9 10
| def build_directed_graph( node_count: int, edges: list[list[int]], ) -> list[list[int]]: graph = [[] for _ in range(node_count)]
for source, target in edges: graph[source].append(target)
return graph
|
邻接表的空间复杂度:
1 2
| 无向图:O(V + 2E),通常写作 O(V + E) 有向图:O(V + E)
|
2.2 邻接矩阵与边列表
邻接矩阵使用 matrix[u][v] 表示节点 u 到 v 是否有边或边权是多少。
| 表示方式 |
空间 |
适用场景 |
| 邻接表 |
O(V+E) |
稀疏图、遍历邻居 |
| 邻接矩阵 |
O(V2) |
稠密图、频繁查询两点是否相连 |
| 边列表 |
O(E) |
Kruskal、Bellman-Ford 等按边扫描的算法 |
不要看到图就固定使用邻接表。Floyd-Warshall 天然使用矩阵;Kruskal 和 Bellman-Ford 则更适合直接保存边。
3. DFS 与 BFS:图遍历的两套基础模板
3.1 DFS:沿一条路走到底再回退
递归 DFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| def dfs_order(graph: list[list[int]], start: int) -> list[int]: visited = [False] * len(graph) order = []
def dfs(node: int) -> None: visited[node] = True order.append(node)
for neighbor in graph[node]: if not visited[neighbor]: dfs(neighbor)
dfs(start) return order
|
DFS 的核心不是递归语法,而是:
1 2 3
| 进入节点时标记 visited 枚举所有邻居 只访问尚未访问的邻居
|
图中可能存在环。如果不记录 visited,DFS 会在环中无限重复。
图很深时可以改用显式栈:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| def iterative_dfs_order( graph: list[list[int]], start: int, ) -> list[int]: visited = [False] * len(graph) stack = [start] order = []
while stack: node = stack.pop()
if visited[node]: continue
visited[node] = True order.append(node)
for neighbor in reversed(graph[node]): if not visited[neighbor]: stack.append(neighbor)
return order
|
3.2 BFS:按距离一层一层扩散
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| from collections import deque
def bfs_distance( graph: list[list[int]], start: int, ) -> list[int]: distance = [-1] * len(graph) distance[start] = 0 queue = deque([start])
while queue: node = queue.popleft()
for neighbor in graph[node]: if distance[neighbor] != -1: continue
distance[neighbor] = distance[node] + 1 queue.append(neighbor)
return distance
|
无权图中,BFS 第一次到达某个节点时走过的边数最少,因此可以直接得到最短距离。
最重要的细节是:入队时就标记访问。如果等到出队才标记,同一节点可能被多个前驱重复加入队列。
3.3 DFS 和 BFS 怎样选择
| 目标 |
更自然的方法 |
| 判断是否可达 |
DFS 或 BFS |
| 枚举一个连通块 |
DFS 或 BFS |
| 无权图最短距离 |
BFS |
| 所有路径、路径回溯 |
DFS |
| 按层扩散、同时传播 |
BFS |
| 递归深度可能非常大 |
迭代 DFS 或 BFS |
两者遍历整个邻接表的时间复杂度都是 O(V+E),区别主要是访问顺序。
4. 二维网格:把每个格子当作节点
二维网格通常不需要显式建立邻接表。每个格子就是节点,上下左右相邻就是边:
1 2 3 4 5 6
| DIRECTIONS = ( (-1, 0), (1, 0), (0, -1), (0, 1), )
|
判断邻居是否合法:
1 2
| 0 <= next_row < rows 0 <= next_col < cols
|
4.1 200. 岛屿数量:每发现一个新陆地就淹没一个连通块
先看最直观的递归 DFS。外层循环负责寻找一块尚未访问的新陆地;找到以后,岛屿数量加一,再从这个格子出发,把上下左右连通的整座岛屿全部“淹没”。
递归 DFS 写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| def num_islands_recursive(grid: list[list[str]]) -> int: if not grid or not grid[0]: return 0
rows = len(grid) cols = len(grid[0])
def flood(row: int, col: int) -> None: if not ( 0 <= row < rows and 0 <= col < cols ): return
if grid[row][col] != '1': return
grid[row][col] = '0'
flood(row - 1, col) flood(row + 1, col) flood(row, col - 1) flood(row, col + 1)
islands = 0
for row in range(rows): for col in range(cols): if grid[row][col] != '1': continue
islands += 1 flood(row, col)
return islands
|
递归函数中的两个停止条件分别负责“不能走”和“不需要再走”:
1 2
| 坐标越界 → 不能走 当前格子不是未访问的陆地 → 不需要再走
|
最关键的一行是先执行 grid[row][col] = ‘0’,再递归访问四个邻居。如果等递归返回以后才标记,两个相邻陆地会不断互相调用。
显式栈 DFS 写法
递归 DFS 使用 Python 的函数调用栈。整张地图接近一条很长的陆地路径时,递归层数可能过深,因此也可以把待访问坐标保存在自己维护的栈中:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| def num_islands(grid: list[list[str]]) -> int: if not grid or not grid[0]: return 0
rows = len(grid) cols = len(grid[0]) directions = ((-1, 0), (1, 0), (0, -1), (0, 1)) islands = 0
def flood(start_row: int, start_col: int) -> None: stack = [(start_row, start_col)] grid[start_row][start_col] = '0'
while stack: row, col = stack.pop()
for row_step, col_step in directions: next_row = row + row_step next_col = col + col_step
if ( 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == '1' ): grid[next_row][next_col] = '0' stack.append((next_row, next_col))
for row in range(rows): for col in range(cols): if grid[row][col] != '1': continue
islands += 1 flood(row, col)
return islands
|
外层循环负责发现新的连通块;DFS 负责把当前连通块全部标记。每个格子最多处理一次,时间复杂度是 O(mn)。
这段代码直接把访问过的陆地改成 ‘0’。如果题目不允许修改输入,就单独维护 visited。
| 写法 |
保存待处理节点的位置 |
特点 |
| 递归 DFS |
Python 函数调用栈 |
写法直观,但路径太深可能超过递归深度限制 |
| 显式栈 DFS |
自己维护的 list |
代码稍长,但不受递归层数限制 |
两种写法都让每个格子最多被处理一次,时间复杂度都是 O(mn);最坏情况下保存的搜索路径或待处理节点数量都是 O(mn)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| def max_area_of_island(grid: list[list[int]]) -> int: if not grid or not grid[0]: return 0
rows = len(grid) cols = len(grid[0]) directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
def area(start_row: int, start_col: int) -> int: stack = [(start_row, start_col)] grid[start_row][start_col] = 0 size = 0
while stack: row, col = stack.pop() size += 1
for row_step, col_step in directions: next_row = row + row_step next_col = col + col_step
if ( 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == 1 ): grid[next_row][next_col] = 0 stack.append((next_row, next_col))
return size
best = 0
for row in range(rows): for col in range(cols): if grid[row][col] == 1: best = max(best, area(row, col))
return best
|
岛屿题常见变体只是在“从哪里开始搜索”和“搜索结果怎样统计”上变化:
从每个格子向外模拟水流会重复搜索。更好的思路是从两个海洋边界反向搜索:
1 2
| 正向:高处可以流向不更高的邻居 反向:海洋可以走向不更低的邻居
|
下面用题目示例逐步执行两次反向 BFS。蓝色表示从太平洋边界能够反向到达,绿色表示从大西洋边界能够反向到达;同一个格子同时拥有两种颜色时,就是最终答案。
从海洋边界反向爬坡,再取两个可达集合的交集
heights = 5 × 5
阶段
动作
当前格
队列
太平洋可达
大西洋可达
两个海洋都可达
当前出队格
高度不足,不能反向走
visited = set(ocean_edges)
row, col = queue.popleft()
heights[next] >= heights[row][col]
visited.add(next); queue.append(next)
answer = pacific & atlantic
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| from collections import deque
def pacific_atlantic( heights: list[list[int]], ) -> list[list[int]]: if not heights or not heights[0]: return []
rows = len(heights) cols = len(heights[0]) directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
def reachable(starts: list[tuple[int, int]]) -> set[tuple[int, int]]: visited = set(starts) queue = deque(visited)
while queue: row, col = queue.popleft()
for row_step, col_step in directions: next_row = row + row_step next_col = col + col_step
if not ( 0 <= next_row < rows and 0 <= next_col < cols ): continue
if (next_row, next_col) in visited: continue
if heights[next_row][next_col] < heights[row][col]: continue
visited.add((next_row, next_col)) queue.append((next_row, next_col))
return visited
pacific_starts = ( [(row, 0) for row in range(rows)] + [(0, col) for col in range(cols)] ) atlantic_starts = ( [(row, cols - 1) for row in range(rows)] + [(rows - 1, col) for col in range(cols)] )
pacific = reachable(pacific_starts) atlantic = reachable(atlantic_starts)
return [ [row, col] for row in range(rows) for col in range(cols) if (row, col) in pacific and (row, col) in atlantic ]
|
反向搜索是网格题的重要技巧:如果“从所有起点分别走”代价太高,可以考虑从终点集合同时反向扩散。
5. 并查集:动态维护无向图的连通分量
并查集适合处理:
1 2 3
| 两个节点是否属于同一集合 合并两个集合 不断加边时判断是否产生环
|
它不保存具体路径,只保存集合关系。
5.1 路径压缩与按大小合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class DisjointSet: def __init__(self, size: int) -> None: self.parent = list(range(size)) self.component_size = [1] * size
def find(self, node: int) -> int: if self.parent[node] != node: self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, first: int, second: int) -> bool: first_root = self.find(first) second_root = self.find(second)
if first_root == second_root: return False
if ( self.component_size[first_root] < self.component_size[second_root] ): first_root, second_root = second_root, first_root
self.parent[second_root] = first_root self.component_size[first_root] += self.component_size[second_root] return True
def connected(self, first: int, second: int) -> bool: return self.find(first) == self.find(second)
|
两个优化分别解决:
- 路径压缩:查询以后让节点直接靠近根。
- 按大小合并:小树挂到大树下面,避免树变得过高。
两者同时使用时,单次操作的均摊复杂度接近 O(1),严格写作 O(α(n))。
并查集森林:查找、压缩、合并与判环
find(4) → union(4, 7) → union(1, 7)
操作准备
当前动作观察初始森林
根节点0、5
当前节点—
双圈是根
橙色是查找路径
绿色是新父指针
红色虚线会成环
parent[x] != x
递归找到 root
parent[x] = root
小树根 → 大树根
同根:拒绝合并
1 / 14
5.2 684. 冗余连接:第一条合并失败的边就是成环边
1 2 3 4 5 6 7 8 9 10 11
| def find_redundant_connection( edges: list[list[int]], ) -> list[int]: node_count = max(max(first, second) for first, second in edges) dsu = DisjointSet(node_count + 1)
for first, second in edges: if not dsu.union(first, second): return [first, second]
return []
|
加入一条边以前,如果两个端点已经连通,再加这条边就会形成环。并查集非常适合“边逐条到来”的无向图问题。
有向图的成环与冗余边需要同时考虑入度,不能直接照搬无向图模板。
6. 拓扑排序:把依赖关系排成合法顺序
拓扑排序解决的是一类“有先后依赖”的问题:当某些事情必须在另一些事情完成以后才能开始时,能否给所有事情安排出一个合法的执行顺序?如果可以,其中一种顺序是什么?
它不是按照节点的数值或名称从小到大排序,而是要求对每一条有向边:
最终结果中,u 必须出现在 v 前面。常见场景包括课程先修关系、软件包依赖、项目任务安排、编译构建顺序等。
如果依赖关系中存在环,例如 A 等 B、B 又等 A,那么没有任何任务能够率先完成,也就不存在拓扑序。因此拓扑排序还经常用来判断有向图是否成环。
拓扑排序只适用于有向无环图,也就是 DAG。同一张图可能有多种合法拓扑序;算法通常只需要返回其中一种。它只负责满足依赖先后关系,并不保证总耗时最短或资源安排最优。
把先修关系:
建成有向边。入度为 0 的节点表示当前没有未完成依赖,可以先执行。
6.1 Kahn 算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| from collections import deque
def find_course_order( num_courses: int, prerequisites: list[list[int]], ) -> list[int]: graph = [[] for _ in range(num_courses)] indegree = [0] * num_courses
for course, prerequisite in prerequisites: graph[prerequisite].append(course) indegree[course] += 1
queue = deque( course for course in range(num_courses) if indegree[course] == 0 ) order = []
while queue: course = queue.popleft() order.append(course)
for next_course in graph[course]: indegree[next_course] -= 1
if indegree[next_course] == 0: queue.append(next_course)
return order if len(order) == num_courses else []
|
判断是否存在环:
1 2
| 处理节点数 == 总节点数:存在拓扑序,没有环 处理节点数 < 总节点数:剩余节点互相依赖,存在环
|
207. 课程表只需判断能否完成,检查结果长度即可;210. 课程表 II需要返回具体顺序。
拓扑序可能不唯一。如果同时有多个入度为 0 的节点,选择顺序不同就可能得到不同合法答案。
7. 最短路:先根据边权选择算法
| 图的条件 |
推荐算法 |
典型复杂度 |
| 无权图或每条边权相同 |
BFS |
O(V+E) |
| 边权非负、单源 |
Dijkstra + 堆 |
O((V+E)logV) |
| 允许负权、单源 |
Bellman-Ford |
O(VE) |
| 所有点对最短路 |
Floyd-Warshall |
O(V3) |
7.1 743. 网络延迟时间:用 Dijkstra 确定当前距离最小的节点
Dijkstra:弹出最近节点,再松弛它的出边
n = 5,k = 1
堆顶弹出—
检查边—
候选距离dist[1] = 0
结果起点入堆
已入堆
当前弹出或检查
最短距离已确定
旧状态
heappop 最小距离
旧状态?continue
遍历 node 的出边
candidate < dist[v]
max(dist[1:])
1 / 18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| import heapq
def network_delay_time( times: list[list[int]], node_count: int, start: int, ) -> int: graph = [[] for _ in range(node_count + 1)]
for source, target, cost in times: graph[source].append((target, cost))
infinity = float('inf') distance = [infinity] * (node_count + 1) distance[start] = 0 heap = [(0, start)]
while heap: current_distance, node = heapq.heappop(heap)
if current_distance != distance[node]: continue
for neighbor, edge_cost in graph[node]: next_distance = current_distance + edge_cost
if next_distance >= distance[neighbor]: continue
distance[neighbor] = next_distance heapq.heappush( heap, (next_distance, neighbor), )
answer = max(distance[1:]) return -1 if answer == infinity else int(answer)
|
堆里可能同时存在同一节点的新旧距离。Python 的 heapq 不支持直接修改堆中元素,所以通常允许旧状态留在堆里;弹出时用下面的判断跳过:
1 2
| if current_distance != distance[node]: continue
|
Dijkstra 不能直接处理负权边。一个已经确定的最短距离可能被后面的负权边再次降低,破坏贪心前提。
7.2 Bellman-Ford:重复松弛所有边
下面的例子包含负权边 2 → 3 = -2,但不存在负权环。边按照 3→4、2→3、1→3、1→2、2→4 的固定顺序扫描;这个顺序会让更短距离一轮一轮向后传播,正好能看清“重复松弛”的意义。
Bellman–Ford 多轮松弛
允许负权边 · 额外一轮检测负权环
第 1 轮第 2 轮第 3 轮检测轮
正在检查成功松弛无需更新
固定扫描顺序
3→4 (+3)2→3 (-2)1→3 (+5)1→2 (+4)2→4 (+4)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| def bellman_ford( node_count: int, edges: list[tuple[int, int, int]], start: int, ) -> list[float]: infinity = float('inf') distance = [infinity] * node_count distance[start] = 0
for _ in range(node_count - 1): changed = False
for source, target, cost in edges: if distance[source] == infinity: continue
candidate = distance[source] + cost
if candidate < distance[target]: distance[target] = candidate changed = True
if not changed: break
return distance
|
一条最短简单路径最多包含 V−1 条边,因此最多扫描 V−1 轮。
如果再扫描一轮仍能更新距离,说明存在从起点可达的负权环。限制“最多经过 K 站”的题需要每轮读取上一轮距离副本,避免同一轮使用超过限制的边数。
7.3 Floyd-Warshall:枚举允许经过的中间节点
Floyd-Warshall 的关键不是“从哪个节点出发”,而是逐步扩大允许作为中间点的节点集合。处理节点 k 时,对每一对 i、j 都比较:直接使用当前的 distance[i][j],还是改走 i → k → j 更短。
Floyd–Warshall 中间点扩展
图上的绕行路径与距离矩阵同步变化
初始化k = 1k = 2k = 3k = 4完成
起点 i中间点 k终点 j
distance[i][j]行是起点 i,列是终点 j
d[i][k]d[k][j]d[i][j]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| def floyd_warshall( node_count: int, edges: list[tuple[int, int, int]], ) -> list[list[float]]: infinity = float('inf') distance = [ [infinity] * node_count for _ in range(node_count) ]
for node in range(node_count): distance[node][node] = 0
for source, target, cost in edges: distance[source][target] = min( distance[source][target], cost, )
for middle in range(node_count): for source in range(node_count): if distance[source][middle] == infinity: continue
for target in range(node_count): candidate = ( distance[source][middle] + distance[middle][target] )
if candidate < distance[source][target]: distance[source][target] = candidate
return distance
|
状态含义:
1 2 3
| 处理 middle 以后, distance[source][target] 表示允许经过 0...middle 作为中间节点时的最短距离。
|
无向图要同时写入两个方向。Floyd-Warshall 适合节点数较小、需要查询很多对节点距离的场景。
7.4 A*:用启发函数朝目标方向搜索
A* 适合已知起点和终点、只需要求这一对节点最短路的场景,尤其常见于网格寻路。它可以看作带有方向感的 Dijkstra:
1 2 3
| g(n):起点到当前节点 n 的真实代价 h(n):从 n 到终点的估计代价 f(n) = g(n) + h(n):小根堆中的优先级
|
Dijkstra 只比较已经走过的 g;A* 再加入 h,让搜索更愿意向目标方向推进。把 h(n) 全部设为 0,A* 就退化成 Dijkstra。
启发函数不能随便估计。要保证求出的路径仍然最短,h(n) 必须不高估从 n 到终点的真实最小代价;常见网格可以这样选择:
| 移动方式 |
单步代价 |
常用启发函数 |
| 只能上下左右 |
1 |
曼哈顿距离 abs(r-tr) + abs(c-tc) |
| 可以向八个方向移动 |
1 |
切比雪夫距离 max(abs(r-tr), abs(c-tc)) |
| 可以任意角度移动 |
欧氏距离 |
欧氏距离 |
先记住三句话:**更新距离时比较 g;决定先搜索谁时比较 f = g + h;parent 只用来恢复最终路径。*下面的 A 和 Dijkstra 使用同一张网格,可以直接对比启发函数如何减少与终点方向无关的搜索。
A* 网格寻路每次弹出小根堆中优先级最小的格子
两者最短路都是 步
开放集合(小根堆)左上角优先弹出
更新邻居:next_g < old_g
入堆优先级:f = g + h
f 相同:h 更小(g 更大)先出堆
回溯路径:parent[child] = current
为什么 goal 第一次出堆就是最短路
这里说的是第一次从小根堆弹出 goal,不是第一次发现 goal 或把 goal 放入堆。
假设出堆的 goal 路径代价为 C,但还存在一条代价为 C∗ 的更短路径,其中 C∗<C。在这条更短路径上,必然有一个已入堆但尚未扩展的节点 x。因为启发函数不高估:
1 2
| f(x) = g(x) + h(x) <= C* < C f(goal) = g(goal) + h(goal) = C + 0 = C
|
小根堆必须先弹出 f(x) 更小的 x,不可能先弹出 goal,与假设矛盾。因此,在边权非负、h 不高估、正确松弛并跳过堆中旧状态的前提下,goal 第一次出堆时就可以结束。四方向网格的曼哈顿距离满足这个条件。
f 相同时如何打破平局
只要始终先比较 f,平局规则不会改变最短路的正确性,但会影响实际扩展的节点数。
| 堆元素 |
f 相同时优先 |
搜索倾向 |
(f, g, row, col) |
较小的 g |
更靠近起点,容易横向展开 |
(f, -g, row, col) |
较大的 g |
更靠近终点,通常扩展更少 |
(f, h, g, row, col) |
较小的 h |
等价于较大的 g,且保留正数 g |
固定 f 时,g 越大就意味着 h = f - g 越小。因此下面代码使用 (f, h, g, row, col):先保证 f 最小,再优先更接近 goal 的节点;row、col 只用来让完全平局时的顺序确定。
下面是四方向网格的完整写法。0 表示可通行,1 表示障碍物,返回值是从起点到终点的路径:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| import heapq
def astar_grid_path( grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int], ) -> list[tuple[int, int]]: if not grid or not grid[0]: return []
rows = len(grid) cols = len(grid[0]) start_row, start_col = start goal_row, goal_col = goal
def is_valid(row: int, col: int) -> bool: return ( 0 <= row < rows and 0 <= col < cols and grid[row][col] == 0 )
if not is_valid(start_row, start_col): return []
if not is_valid(goal_row, goal_col): return []
def heuristic(row: int, col: int) -> int: return ( abs(row - goal_row) + abs(col - goal_col) )
infinity = float('inf') g_score = [ [infinity] * cols for _ in range(rows) ] g_score[start_row][start_col] = 0
start_h = heuristic(start_row, start_col) heap = [ ( start_h, start_h, 0, start_row, start_col, ) ] parent: dict[ tuple[int, int], tuple[int, int], ] = {} directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
while heap: _, _, current_g, row, col = heapq.heappop(heap)
if current_g != g_score[row][col]: continue
if (row, col) == goal: path = [] current = goal
while current != start: path.append(current) current = parent[current]
path.append(start) path.reverse() return path
for row_step, col_step in directions: next_row = row + row_step next_col = col + col_step
if not is_valid(next_row, next_col): continue
next_g = current_g + 1
if next_g >= g_score[next_row][next_col]: continue
g_score[next_row][next_col] = next_g parent[(next_row, next_col)] = (row, col) next_h = heuristic(next_row, next_col) next_f = next_g + next_h heapq.heappush( heap, ( next_f, next_h, next_g, next_row, next_col, ), )
return []
|
1091. 二进制矩阵中的最短路径允许八方向移动,可以把方向数组改成八个方向,并使用切比雪夫距离;这道题边权全部为 1,普通 BFS 已经足够,A* 的价值主要是减少面向单个终点时实际扩展的节点数。
A* 使用小根堆时,最坏时间复杂度仍可写作 O(ElogV),空间复杂度为 O(V)。好的启发函数通常能显著减少搜索范围,但不会改善最坏复杂度;图中存在负权边时不能直接使用 A*。
8. 最小生成树:用最小总代价连接所有节点
最小生成树针对的是连通无向带权图:
1 2 3 4
| 覆盖所有节点 只保留 V - 1 条边 不能形成环 边权总和最小
|
它和最短路不同:
- 最短路关注某个起点到其他节点的距离。
- 最小生成树关注连接整个图的总成本。
8.1 Kruskal:按边权从小到大选边
Kruskal 不关心当前生成树长在什么位置,而是从全图最便宜的边开始检查。下面的动画会同时展示排序后的边、当前连通分量,以及并查集为什么拒绝会成环的边。
Kruskal:排序边 + 并查集选择便宜且连接两个不同分量的边
正在检查已选入 MST成环,跳过
按权重升序相同权重顺序可交换
2—311—324—525—631—242—454—663—483—510
并查集中的连通分量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| def minimum_spanning_tree_cost( node_count: int, edges: list[tuple[int, int, int]], ) -> int: dsu = DisjointSet(node_count) total_cost = 0 used_edges = 0
for first, second, cost in sorted( edges, key=lambda edge: edge[2], ): if not dsu.union(first, second): continue
total_cost += cost used_edges += 1
if used_edges == node_count - 1: return total_cost
return -1
|
每次优先选择最便宜、并且不会形成环的边。并查集负责判断两个端点是否已经连通。
复杂度主要来自边排序,为 O(ElogE)。
8.2 Prim:不断把离生成树最近的节点拉进来
Prim 从某个节点开始,维护“当前生成树到外部节点的最小边”。它和 Dijkstra 都会使用小根堆,但堆中优先级含义不同:
Prim:从一棵树向外扩张小根堆只比较跨越当前边界的候选边
候选边已选入 MST两端都在树中
候选边小根堆左侧是当前堆顶
Prim 的边界条件
树内节点— 最便宜边 →树外节点
若弹出边的两个端点都已在树中,它就是旧候选,直接跳过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| import heapq
def minimum_spanning_tree_cost_prim( node_count: int, edges: list[tuple[int, int, int]], ) -> int: if node_count == 0: return 0
graph = [[] for _ in range(node_count)]
for first, second, cost in edges: graph[first].append((second, cost)) graph[second].append((first, cost))
visited = [False] * node_count heap = [(0, 0)] total_cost = 0 used_nodes = 0
while heap and used_nodes < node_count: edge_cost, node = heapq.heappop(heap)
if visited[node]: continue
visited[node] = True total_cost += edge_cost used_nodes += 1
for neighbor, cost in graph[node]: if not visited[neighbor]: heapq.heappush(heap, (cost, neighbor))
return total_cost if used_nodes == node_count else -1
|
| 算法 |
堆中的优先级 |
| Dijkstra |
起点到该节点的完整路径距离 |
| Prim |
当前生成树连接该节点的最小单边代价 |
稀疏图常用 Kruskal;已有邻接表并且希望按节点扩张时,Prim 更自然。
二维接雨水和 42. 一维接雨水 虽然名字相似,但不能继续使用单调栈;一维版本的完整解释和动画见单调栈笔记。
一维数组中,每个凹槽只需要寻找左右挡板;二维网格中的水可能从上下左右任意方向泄漏,一个格子的水位由包围它的整圈边界中最低的缺口决定。
因此需要:
1 2
| 最小堆:始终取出当前最低边界 BFS:从这条边界向相邻格子扩散
|
这个过程很像从地图四周向内部逐步“淹没”:
- 把所有边界格子加入小根堆。
- 弹出当前高度最低的边界格子。
- 查看它上下左右尚未访问的邻居。
- 邻居更低时,可以存下
boundary_height - neighbor_height 的水。
- 邻居加入堆时的有效边界高度是
max(boundary_height, neighbor_height)。
下面先用一个只有一个低点的 3×3 小坑建立直觉,再切换到题目的 3×6 示例。主视图使用二维俯视网格讲清访问顺序;三维图只在完整示例结束时展示最终水面。动画不会再无提示跳步:没有发现新邻居的连续出堆会合并成一句明确说明。
二维接雨水:最低边界向内扩散
小根堆
1. 弹出最低边界H = ?
2. 查看相邻格h = ?
3. 计算水深H - h
4. 更新有效边界H′ = max(H, h)
9.1 为什么入堆的是有效高度
假设当前最低边界高度为 4,内部邻居原高度为 1:
1 2 3
| 这个格子存水 4 - 1 = 3 格子的水面已经达到 4 它继续向内部扩展时,能够充当高度为 4 的新边界
|
因此不能把原高度 1 重新放进堆,而要放入有效高度 4。
9.2 完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| import heapq
def trap_rain_water( height_map: list[list[int]], ) -> int: if not height_map or not height_map[0]: return 0
rows = len(height_map) cols = len(height_map[0])
if rows < 3 or cols < 3: return 0
visited = [ [False] * cols for _ in range(rows) ] heap = []
def add_boundary(row: int, col: int) -> None: if visited[row][col]: return
visited[row][col] = True heapq.heappush( heap, (height_map[row][col], row, col), )
for row in range(rows): add_boundary(row, 0) add_boundary(row, cols - 1)
for col in range(1, cols - 1): add_boundary(0, col) add_boundary(rows - 1, col)
directions = ((-1, 0), (1, 0), (0, -1), (0, 1)) water = 0
while heap: boundary_height, row, col = heapq.heappop(heap)
for row_step, col_step in directions: next_row = row + row_step next_col = col + col_step
if not ( 0 <= next_row < rows and 0 <= next_col < cols ): continue
if visited[next_row][next_col]: continue
visited[next_row][next_col] = True neighbor_height = height_map[next_row][next_col]
if neighbor_height < boundary_height: water += boundary_height - neighbor_height
heapq.heappush( heap, ( max(boundary_height, neighbor_height), next_row, next_col, ), )
return water
|
小根堆保证我们永远从当前最低缺口向内推进。这与 Dijkstra 很像:已经弹出的最低边界可以安全确定,不会被更高边界推翻。
每个格子只访问一次,最多入堆和出堆一次。设网格大小为 m×n:
1 2
| 时间复杂度:O(mn log(mn)) 空间复杂度:O(mn)
|
这一题也是 堆与优先队列 和图搜索结合的典型例子。
9.3 一维和二维接雨水对比
| 对比 |
42. 一维接雨水 |
407. 二维接雨水 |
| 数据形态 |
一维柱高数组 |
二维高度网格 |
| 边界 |
左、右挡板 |
包围区域的整圈边界 |
| 核心结构 |
单调栈 |
小根堆 |
| 推进方式 |
当前高柱结算凹槽 |
当前最低边界向内 BFS |
| 复杂度 |
O(n) |
O(mnlog(mn)) |
不要因为题目名称相同就强行复用数据结构。决定算法的是边界关系,而不是题目标题。
10. 常见错误
10.1 无向边只加入一个方向
无向图的 u - v 必须同时加入:
1 2
| graph[u].append(v) graph[v].append(u)
|
只加一个方向会把无向图错误地变成有向图。
10.2 入队和出队时机混乱
BFS 通常在入队时标记访问。这样每个节点只会入队一次,避免队列里出现大量重复状态。
10.3 把 BFS 当作所有最短路的通用解法
BFS 只直接适用于无权图或所有边权相同的图。边权不同且非负时使用 Dijkstra;存在负权边时考虑 Bellman-Ford。
10.4 Dijkstra 忘记跳过旧状态
同一节点可能多次入堆。弹出的距离不是当前记录时必须跳过,否则会做大量无效松弛。
10.5 拓扑排序把边方向写反
课程依赖 [course, prerequisite] 应该建边:
同时增加 course 的入度。
10.6 并查集把节点值当成连续下标
节点编号不连续或从 1 开始时,要先映射或按最大编号分配数组,避免越界。
10.7 二维接雨水重复加入边界角点
四个角同时属于横向边界和纵向边界。加入边界时要用 visited 去重。
10.8 二维接雨水把邻居原高度直接入堆
已经存水的格子水面被抬高了。下一轮边界必须使用:
1
| max(boundary_height, neighbor_height)
|
否则会错误地从内部低点泄漏。
10.9 A* 的启发函数高估真实代价
启发函数如果高估剩余距离,A* 可能过早偏向一条看似便宜、实际并非最短的路径。想保留最短路保证,必须使用不高估真实最小代价的启发函数;如果无法构造可靠的 h,令 h = 0,退化为 Dijkstra 更安全。
11. 一份实用的图论检查清单
- 节点和边分别是什么?
- 图是有向还是无向?
- 是否需要给无向边加入两个方向?
- 边是否带权?权重是否可能为负?
- 求的是可达、连通、最短路还是最小生成树?
- DFS / BFS 的
visited 在什么时机设置?
- 网格搜索是否检查了四个边界?
- 是否可以从多个终点反向搜索?
- 拓扑排序的边方向和入度是否正确?
- Dijkstra 是否跳过了堆中的旧距离?
- 并查集的节点编号是否与数组下标一致?
- 最小生成树最终是否选中了恰好 V−1 条边?
- 二维接雨水入堆的是原高度还是有效边界高度?
- A* 的启发函数是否会高估真实剩余代价?
12. 复习总览
- 图由节点和边组成,第一步是确定有向性、边权和邻居表示。
- 邻接表适合稀疏图,邻接矩阵适合稠密图和多点距离,边列表适合按边扫描。
- DFS 适合连通块、路径和回溯;BFS 适合按层扩散和无权最短路。
- 网格是隐式图,每个格子是节点,上下左右移动是边。
- 岛屿题的核心是发现一个新连通块后把它完整标记。
- 并查集维护动态连通关系,适合合并集合和无向图成环判断。
- 拓扑排序不断处理入度为 0 的节点;无法处理全部节点说明存在环。
- 无权最短路用 BFS;非负权单源最短路用 Dijkstra;负权边考虑 Bellman-Ford。
- Floyd-Warshall 用三重循环计算所有节点对最短距离。
- A* 用
f = g + h 面向目标搜索;可靠的启发函数不能高估真实剩余代价。
- 最小生成树连接所有节点且总边权最小;Kruskal 排序全图边并用并查集判环,Prim 用小根堆从当前树向外扩张。
- 407 二维接雨水不是单调栈题,而是小根堆控制最低边界、BFS 向内部扩散。
- 二维接雨水中,邻居入堆时必须使用抬高后的有效边界高度。
图论题最容易混乱的地方不是代码长度,而是算法选择。先判断“连接关系、边权、目标”,再选 DFS/BFS、并查集、拓扑排序、最短路或最小生成树,模板才不会套错。