返回算法笔记总览 上一篇:单调栈 下一篇:专题扩展(整理中)

1. 什么时候想到图论

图论题不一定真的出现“图”这个词。只要问题中存在一批对象,以及对象之间的连接、移动、依赖或转换关系,就可以考虑把它建模成图:

1
2
3
对象                 → 节点
对象之间的关系 → 边
从一个对象移动到另一个 → 沿边访问

常见题目信号:

题目描述 常用方法
能否从起点到终点、所有连通块 DFS、BFS、并查集
二维地图扩散、岛屿、迷宫 网格 DFS / BFS
最少步数、边权都相同 BFS
动态合并集合、判断是否成环 并查集
课程依赖、任务先后关系 拓扑排序
非负权最短路 Dijkstra + 小根堆
可能有负权边 Bellman-Ford
所有节点两两最短路 Floyd-Warshall
用最小代价连接所有节点 最小生成树
总从当前最低边界向外扩展 小根堆 + BFS

选择算法之前先回答四个问题:

  1. 图是有向还是无向?
  2. 边是否带权?权重能否为负?
  3. 求的是可达性、连通性、最短路,还是连接所有节点的最小代价?
  4. 图是显式边集合,还是二维网格隐式形成的图?

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(V + E) 稀疏图、遍历邻居
邻接矩阵 O(V2)O(V^2) 稠密图、频繁查询两点是否相连
边列表 O(E)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)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)O(mn)。

这段代码直接把访问过的陆地改成 ‘0’。如果题目不允许修改输入,就单独维护 visited。

写法 保存待处理节点的位置 特点
递归 DFS Python 函数调用栈 写法直观,但路径太深可能超过递归深度限制
显式栈 DFS 自己维护的 list 代码稍长,但不受递归层数限制

两种写法都让每个格子最多被处理一次,时间复杂度都是 O(mn)O(mn);最坏情况下保存的搜索路径或待处理节点数量都是 O(mn)O(mn)。

4.2 695. 岛屿的最大面积: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 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

岛屿题常见变体只是在“从哪里开始搜索”和“搜索结果怎样统计”上变化:

题目 起点与处理方式
200. 岛屿数量 遇到新陆地,连通块数量加一
695. 最大岛屿面积 统计每个连通块的格子数
1020. 飞地数量 先从边界陆地搜索,剩余陆地才是飞地
130. 被围绕的区域 先保护与边界相连的区域,再处理剩余区域
827. 最大人工岛 先给岛屿编号和面积,再尝试翻转每个水格

4.3 417. 太平洋大西洋水流问题:从海洋反向搜索

从每个格子向外模拟水流会重复搜索。更好的思路是从两个海洋边界反向搜索:

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
queue(队首 → 队尾)
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(1),严格写作 O(α(n))O(\alpha(n))。

并查集森林:查找、压缩、合并与判环 find(4) → union(4, 7) → union(1, 7)
操作准备 当前动作观察初始森林 根节点0、5 当前节点—
并查集森林变化 箭头从子节点指向父节点,逐步演示查找、路径压缩、按大小合并以及拒绝成环边。
双圈是根 橙色是查找路径 绿色是新父指针 红色虚线会成环
parent[x] != x 递归找到 root parent[x] = root 小树根 → 大树根 同根:拒绝合并
parent
size仅根有效
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. 拓扑排序:把依赖关系排成合法顺序

拓扑排序解决的是一类“有先后依赖”的问题:当某些事情必须在另一些事情完成以后才能开始时,能否给所有事情安排出一个合法的执行顺序?如果可以,其中一种顺序是什么?

它不是按照节点的数值或名称从小到大排序,而是要求对每一条有向边:

1
前置任务 u → 后续任务 v

最终结果中,u 必须出现在 v 前面。常见场景包括课程先修关系、软件包依赖、项目任务安排、编译构建顺序等。

如果依赖关系中存在环,例如 A 等 B、B 又等 A,那么没有任何任务能够率先完成,也就不存在拓扑序。因此拓扑排序还经常用来判断有向图是否成环。

拓扑排序只适用于有向无环图,也就是 DAG。同一张图可能有多种合法拓扑序;算法通常只需要返回其中一种。它只负责满足依赖先后关系,并不保证总耗时最短或资源安排最优。

把先修关系:

1
prerequisite → course

建成有向边。入度为 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)O(V + E)
边权非负、单源 Dijkstra + 堆 O((V+E)log⁡V)O((V + E)\log V)
允许负权、单源 Bellman-Ford O(VE)O(VE)
所有点对最短路 Floyd-Warshall O(V3)O(V^3)

7.1 743. 网络延迟时间:用 Dijkstra 确定当前距离最小的节点

Dijkstra:弹出最近节点,再松弛它的出边 n = 5,k = 1
堆顶弹出— 检查边— 候选距离dist[1] = 0 结果起点入堆
Dijkstra 有向带权图 从节点 1 出发,箭头表示传播方向,边旁数字表示传播耗时。 10 3 2 8 7 2 4 1 1 2 3 4 5
已入堆 当前弹出或检查 最短距离已确定 旧状态
heappop 最小距离 旧状态?continue 遍历 node 的出边 candidate < dist[v] max(dist[1:])
小根堆顶部在左
节点12345
dist
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 轮检测轮
4 5 -2 4 3 1 2 3 4
正在检查成功松弛无需更新
固定扫描顺序
  1. 3→4 (+3)
  2. 2→3 (-2)
  3. 1→3 (+5)
  4. 1→2 (+4)
  5. 2→4 (+4)
节点1234
轮开始
dist
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−1V-1 条边,因此最多扫描 V−1V-1 轮。

如果再扫描一轮仍能更新距离,说明存在从起点可达的负权环。限制“最多经过 K 站”的题需要每轮读取上一轮距离副本,避免同一轮使用超过限制的边数。

7.3 Floyd-Warshall:枚举允许经过的中间节点

Floyd-Warshall 的关键不是“从哪个节点出发”,而是逐步扩大允许作为中间点的节点集合。处理节点 k 时,对每一对 i、j 都比较:直接使用当前的 distance[i][j],还是改走 i → k → j 更短。

Floyd–Warshall 中间点扩展 图上的绕行路径与距离矩阵同步变化
允许中间点
正在计算
候选距离
结果
初始化k = 1k = 2k = 3k = 4完成
3 1 2 10 -1 1 2 3 4
起点 i中间点 k终点 j
distance[i][j]行是起点 i,列是终点 j
i\j1234
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 路径代价为 CC,但还存在一条代价为 C∗C^* 的更短路径,其中 C∗<CC^* < 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

# 堆元素:(f, h, g, row, col)
# f 相同时优先 h 更小的节点,等价于优先 g 更大。
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(Elog⁡V)O(E\log V),空间复杂度为 O(V)O(V)。好的启发函数通常能显著减少搜索范围,但不会改善最坏复杂度;图中存在负权边时不能直接使用 A*。

8. 最小生成树:用最小总代价连接所有节点

最小生成树针对的是连通无向带权图:

1
2
3
4
覆盖所有节点
只保留 V - 1 条边
不能形成环
边权总和最小

它和最短路不同:

  • 最短路关注某个起点到其他节点的距离。
  • 最小生成树关注连接整个图的总成本。

8.1 Kruskal:按边权从小到大选边

Kruskal 不关心当前生成树长在什么位置,而是从全图最便宜的边开始检查。下面的动画会同时展示排序后的边、当前连通分量,以及并查集为什么拒绝会成环的边。

Kruskal:排序边 + 并查集选择便宜且连接两个不同分量的边
当前边
并查集判断
操作
当前总代价
4 2 1 5 8 10 2 6 3 1 2 3 4 5 6
正在检查已选入 MST成环,跳过
按权重升序相同权重顺序可交换
  1. 2—31
  2. 1—32
  3. 4—52
  4. 5—63
  5. 1—24
  6. 2—45
  7. 4—66
  8. 3—48
  9. 3—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(Elog⁡E)O(E\log E)。

8.2 Prim:不断把离生成树最近的节点拉进来

Prim 从某个节点开始,维护“当前生成树到外部节点的最小边”。它和 Dijkstra 都会使用小根堆,但堆中优先级含义不同:

Prim:从一棵树向外扩张小根堆只比较跨越当前边界的候选边
堆顶边
当前树节点
操作
当前总代价
4 2 1 5 8 10 2 6 3 1 2 3 4 5 6
候选边已选入 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 更自然。

9. 407. 接雨水 II:最小堆控制二维水位边界

二维接雨水和 42. 一维接雨水 虽然名字相似,但不能继续使用单调栈;一维版本的完整解释和动画见单调栈笔记。

一维数组中,每个凹槽只需要寻找左右挡板;二维网格中的水可能从上下左右任意方向泄漏,一个格子的水位由包围它的整圈边界中最低的缺口决定。

因此需要:

1
2
最小堆:始终取出当前最低边界
BFS:从这条边界向相邻格子扩散

这个过程很像从地图四周向内部逐步“淹没”:

  1. 把所有边界格子加入小根堆。
  2. 弹出当前高度最低的边界格子。
  3. 查看它上下左右尚未访问的邻居。
  4. 邻居更低时,可以存下 boundary_height - neighbor_height 的水。
  5. 邻居加入堆时的有效边界高度是 max(boundary_height, neighbor_height)。

下面先用一个只有一个低点的 3×33\times3 小坑建立直觉,再切换到题目的 3×63\times6 示例。主视图使用二维俯视网格讲清访问顺序;三维图只在完整示例结束时展示最终水面。动画不会再无提示跳步:没有发现新邻居的连续出堆会合并成一句明确说明。

二维接雨水:最低边界向内扩散
小根堆
仍在堆中当前出堆正在检查已经存水
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×nm \times n:

1
2
时间复杂度:O(mn log(mn))
空间复杂度:O(mn)

这一题也是 堆与优先队列 和图搜索结合的典型例子。

9.3 一维和二维接雨水对比

对比 42. 一维接雨水 407. 二维接雨水
数据形态 一维柱高数组 二维高度网格
边界 左、右挡板 包围区域的整圈边界
核心结构 单调栈 小根堆
推进方式 当前高柱结算凹槽 当前最低边界向内 BFS
复杂度 O(n)O(n) O(mnlog⁡(mn))O(mn\log(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] 应该建边:

1
prerequisite → course

同时增加 course 的入度。

10.6 并查集把节点值当成连续下标

节点编号不连续或从 1 开始时,要先映射或按最大编号分配数组,避免越界。

10.7 二维接雨水重复加入边界角点

四个角同时属于横向边界和纵向边界。加入边界时要用 visited 去重。

10.8 二维接雨水把邻居原高度直接入堆

已经存水的格子水面被抬高了。下一轮边界必须使用:

1
max(boundary_height, neighbor_height)

否则会错误地从内部低点泄漏。

10.9 A* 的启发函数高估真实代价

启发函数如果高估剩余距离,A* 可能过早偏向一条看似便宜、实际并非最短的路径。想保留最短路保证,必须使用不高估真实最小代价的启发函数;如果无法构造可靠的 h,令 h = 0,退化为 Dijkstra 更安全。

11. 一份实用的图论检查清单

  1. 节点和边分别是什么?
  2. 图是有向还是无向?
  3. 是否需要给无向边加入两个方向?
  4. 边是否带权?权重是否可能为负?
  5. 求的是可达、连通、最短路还是最小生成树?
  6. DFS / BFS 的 visited 在什么时机设置?
  7. 网格搜索是否检查了四个边界?
  8. 是否可以从多个终点反向搜索?
  9. 拓扑排序的边方向和入度是否正确?
  10. Dijkstra 是否跳过了堆中的旧距离?
  11. 并查集的节点编号是否与数组下标一致?
  12. 最小生成树最终是否选中了恰好 V−1V-1 条边?
  13. 二维接雨水入堆的是原高度还是有效边界高度?
  14. A* 的启发函数是否会高估真实剩余代价?

12. 复习总览

  • 图由节点和边组成,第一步是确定有向性、边权和邻居表示。
  • 邻接表适合稀疏图,邻接矩阵适合稠密图和多点距离,边列表适合按边扫描。
  • DFS 适合连通块、路径和回溯;BFS 适合按层扩散和无权最短路。
  • 网格是隐式图,每个格子是节点,上下左右移动是边。
  • 岛屿题的核心是发现一个新连通块后把它完整标记。
  • 并查集维护动态连通关系,适合合并集合和无向图成环判断。
  • 拓扑排序不断处理入度为 0 的节点;无法处理全部节点说明存在环。
  • 无权最短路用 BFS;非负权单源最短路用 Dijkstra;负权边考虑 Bellman-Ford。
  • Floyd-Warshall 用三重循环计算所有节点对最短距离。
  • A* 用 f = g + h 面向目标搜索;可靠的启发函数不能高估真实剩余代价。
  • 最小生成树连接所有节点且总边权最小;Kruskal 排序全图边并用并查集判环,Prim 用小根堆从当前树向外扩张。
  • 407 二维接雨水不是单调栈题,而是小根堆控制最低边界、BFS 向内部扩散。
  • 二维接雨水中,邻居入堆时必须使用抬高后的有效边界高度。

图论题最容易混乱的地方不是代码长度,而是算法选择。先判断“连接关系、边权、目标”,再选 DFS/BFS、并查集、拓扑排序、最短路或最小生成树,模板才不会套错。

返回算法笔记总览 上一篇:单调栈 下一篇:专题扩展(整理中)
avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。
目录
  1. 1. 什么时候想到图论
  2. 2. 图的表示:先决定节点怎样找到邻居
    1. 2.1 邻接表
    2. 2.2 邻接矩阵与边列表
  3. 3. DFS 与 BFS:图遍历的两套基础模板
    1. 3.1 DFS:沿一条路走到底再回退
    2. 3.2 BFS:按距离一层一层扩散
    3. 3.3 DFS 和 BFS 怎样选择
  4. 4. 二维网格:把每个格子当作节点
    1. 4.1 200. 岛屿数量:每发现一个新陆地就淹没一个连通块
      1. 递归 DFS 写法
      2. 显式栈 DFS 写法
    2. 4.2 695. 岛屿的最大面积:DFS 返回当前连通块大小
    3. 4.3 417. 太平洋大西洋水流问题:从海洋反向搜索
  5. 5. 并查集:动态维护无向图的连通分量
    1. 5.1 路径压缩与按大小合并
    2. 5.2 684. 冗余连接:第一条合并失败的边就是成环边
  6. 6. 拓扑排序:把依赖关系排成合法顺序
    1. 6.1 Kahn 算法
  7. 7. 最短路:先根据边权选择算法
    1. 7.1 743. 网络延迟时间:用 Dijkstra 确定当前距离最小的节点
    2. 7.2 Bellman-Ford:重复松弛所有边
    3. 7.3 Floyd-Warshall:枚举允许经过的中间节点
    4. 7.4 A*:用启发函数朝目标方向搜索
      1. 为什么 goal 第一次出堆就是最短路
      2. f 相同时如何打破平局
  8. 8. 最小生成树:用最小总代价连接所有节点
    1. 8.1 Kruskal:按边权从小到大选边
    2. 8.2 Prim:不断把离生成树最近的节点拉进来
  9. 9. 407. 接雨水 II:最小堆控制二维水位边界
    1. 9.1 为什么入堆的是有效高度
    2. 9.2 完整代码
    3. 9.3 一维和二维接雨水对比
  10. 10. 常见错误
    1. 10.1 无向边只加入一个方向
    2. 10.2 入队和出队时机混乱
    3. 10.3 把 BFS 当作所有最短路的通用解法
    4. 10.4 Dijkstra 忘记跳过旧状态
    5. 10.5 拓扑排序把边方向写反
    6. 10.6 并查集把节点值当成连续下标
    7. 10.7 二维接雨水重复加入边界角点
    8. 10.8 二维接雨水把邻居原高度直接入堆
    9. 10.9 A* 的启发函数高估真实代价
  11. 11. 一份实用的图论检查清单
  12. 12. 复习总览
最新文章
网站信息
文章数目 :
18
最后更新时间 :