图¶
一句话总结：图算法几乎全部归结为 BFS 与 DFS 两大遍历模式，再叠加最短路 (Dijkstra)、拓扑排序、连通分量等变形，掌握这两把钥匙就能破解绝大多数图题。
图用来建模关系与连接：社交网络、路网、依赖链。 本节覆盖图的表示、广度优先搜索 (Breadth-First Search, BFS)、深度优先搜索 (Depth-First Search, DFS)、最短路径、拓扑排序与连通分量，以及主导图类面试题的遍历与寻路套路.
-
图论的基础我们在第 12 章 (邻接矩阵、拉普拉斯、谱性质) 与第 13 章 (树、平面性、着色) 已经讲过。 这里聚焦算法套路：如何在代码里遍历、搜索、优化图。
-
图的两大基本算法是 BFS 与 DFS. 几乎所有图题都能归约到二者之一，可能带一点小改造。 把这两个吃透，大部分图题都能解。
图的表示¶
- 邻接表 (adjacency list)：对每个节点存一份邻居列表。 空间 \(O(|V| + |E|)\). 适合稀疏图 (大多数现实中的图都是稀疏的).
# 无向图
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
# 从边列表构造
def build_graph(n, edges):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 有向图省略此行
return graph
-
邻接矩阵 (adjacency matrix): \(n \times n\) 的矩阵，若边 \((i, j)\) 存在则 \(A[i][j] = 1\). 空间 \(O(|V|^2)\). 适合稠密图，或需要 \(O(1)\) 查询边是否存在的场景。
-
何时用哪种：绝大多数场景用邻接表。 只有图很稠密 (\(|E| \approx |V|^2\)) 或必须常数时间判断边是否存在时才用矩阵。
套路：BFS (广度优先搜索)¶
- BFS 借助队列一层一层地探索节点。 它是以下问题的首选:
- 无权图上的最短路径
- 层序遍历
- 找连通分量
- 任何问"最少多少步"的问题
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
- 关键：在入队时加入
visited，而不是出队时。 如果出队才标记，同一个节点可能被不同前驱多次入队，既浪费时间，也可能导致结果不对。
简单：岛屿数量¶
-
问题：给定一个由 '1' (陆地) 和 '0' (水) 组成的二维网格，数一共有多少座岛屿。
-
套路：遍历网格。 每遇到一个 '1'，就用 BFS/DFS 把所有相连的陆地都标记为已访问。 每一次 BFS 启动就是一座岛。
from collections import deque
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
# BFS 标记整座岛
queue = deque([(r, c)])
grid[r][c] = '0' # 标记已访问
while queue:
cr, cc = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
return count
-
易错点:
directions = [(0,1),(0,-1),(1,0),(-1,0)]这一套四连通邻居模式几乎所有网格题都会用到。 背下来。 需要八连通时再加上四个对角线。 -
易错点：直接改输入网格 (
grid[r][c] = '0') 可以省掉单独的visited集合。 面试里可以这么做，但要说明代价 (会破坏输入).
中等：腐烂的橘子¶
-
问题：新鲜橘子只要相邻的橘子烂了就会跟着烂。 求所有橘子都烂掉需要的最短时间 (若不可能则返回 -1).
-
套路：多源 BFS. 把所有初始就烂了的橘子同时塞进队列。 BFS 的每一层就是一个时间步。
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
time = 0
while queue and fresh > 0:
time += 1
for _ in range(len(queue)):
cr, cc = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return time if fresh == 0 else -1
- 关键洞察：多源 BFS 把所有源头一起处理。 它给出的是到任意源头的最短距离，恰好就是"最后一颗新鲜橘子多久会烂".
套路：DFS (深度优先搜索)¶
- DFS 尽可能往深处走，走不动了再回溯。 它用栈 (显式栈，或者靠递归的调用栈). DFS 是这些问题的首选:
- 环检测
- 拓扑排序
- 连通分量
- 回溯 / 穷举搜索
- 带约束的路径搜索
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for neighbour in graph[node]:
if neighbour not in visited:
dfs(graph, neighbour, visited)
中等：课程表 (环检测)¶
-
问题：给定 \(n\) 门课程与它们的先修关系，判断能否修完所有课 (即是否存在循环依赖).
-
套路：在有向图里检测环。 用三种状态的 DFS：未访问、进行中 (在当前 DFS 路径上)、已完成。
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
for course, prereq in prerequisites:
graph[course].append(prereq)
# 0 = 未访问, 1 = 进行中, 2 = 已完成
state = [0] * num_courses
def has_cycle(node):
if state[node] == 1:
return True # 回边 → 有环
if state[node] == 2:
return False # 已完全探索过
state[node] = 1 # 标记为进行中
for neighbour in graph[node]:
if has_cycle(neighbour):
return True
state[node] = 2 # 标记为已完成
return False
for course in range(num_courses):
if has_cycle(course):
return False
return True
- 为什么要三种状态：只用两种状态 (访问过 / 没访问过) 区分不了"我正在探索这个节点"与"我已经探索完这个节点". 如果碰到一个正在被探索的节点 (状态 = 1)，就说明找到了环。 如果碰到已经完全探索完的节点 (状态 = 2)，那只是一条横叉边，不是环。
中等：课程表 II (拓扑排序)¶
-
问题：返回一个合法的修课顺序 (拓扑序).
-
套路 (Kahn 算法 —— 基于 BFS)：从没有入边 (入度为 0) 的节点开始。 处理它们，再把邻居的入度减 1. 重复。
from collections import deque
def find_order(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = deque([i for i in range(num_courses) if indegree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
indegree[neighbour] -= 1
if indegree[neighbour] == 0:
queue.append(neighbour)
return order if len(order) == num_courses else [] # 空结果 = 存在环
- 易错点：如果结果的节点数少于图的节点数，就说明有环 (某些节点的入度一直没有降到 0).
最短路径¶
Dijkstra 算法¶
- 从源点出发，求它到所有其他节点的最短路径，前提是图非负权. 用优先队列 (最小堆) 实现。
import heapq
def dijkstra(graph, start):
# graph: {node: [(neighbour, weight), ...]}
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue # 过期条目
for neighbour, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbour]:
dist[neighbour] = new_dist
heapq.heappush(heap, (new_dist, neighbour))
return dist
-
时间复杂度：用二叉堆时为 \(O((|V| + |E|) \log |V|)\).
-
易错点:
if d > dist[node]: continue这一行不能少。 少了就会去处理堆里的过期条目，复杂度可能退化到 \(O(|V|^2)\). -
易错点: Dijkstra 不适用于负权边。 一旦有负权，贪心假设 (一个节点一旦"敲定"其距离就是最优) 就崩了。 这时改用 Bellman-Ford.
Bellman-Ford 算法¶
-
贝尔曼-福特算法 (Bellman-Ford Algorithm)：支持负权边的单源最短路。 核心操作叫松弛 (relaxation)：对每条边 \((u, v, w)\)，若 \(dist[u] + w < dist[v]\) 就更新 \(dist[v]\). 把所有 \(|E|\) 条边松弛 \(|V| - 1\) 轮，就能得到最短路 (因为最短路最多经过 \(|V| - 1\) 条边).
-
再多松弛一轮：如果还能更新，说明图里存在负权环 (negative cycle)，最短路无定义。
def bellman_ford(edges, n, start):
# edges: [(u, v, w), ...], n = 节点数
dist = [float('inf')] * n
dist[start] = 0
# 松弛 n - 1 轮
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 再来一轮, 若还能松弛就有负环
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # 存在负权环
return dist
- 时间复杂度 \(O(|V| \cdot |E|)\)，比 Dijkstra 慢，但能处理负权边。 常用于货币套利检测、有 \(K\) 次中转限制的最短路 (改造版).
Floyd-Warshall 算法¶
-
弗洛伊德-沃舍尔算法 (Floyd-Warshall Algorithm): 全源最短路 (all-pairs shortest paths)，一次跑出任意两点间的最短距离。 三重循环，短短几行，但威力惊人。
-
核心思想 (动态规划): \(dist[i][j]\) 表示"只允许经过 \(\{0, 1, \dots, k\}\) 作为中间节点时，\(i\) 到 \(j\) 的最短距离". 外层枚举中转点 \(k\)，逐步放开可选中间节点的范围。
def floyd_warshall(n, edges):
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w # 有向图; 无向图再加 dist[v][u] = w
# k 必须放最外层! 表示"允许 k 作为中转"
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
-
时间复杂度 \(O(|V|^3)\)，空间 \(O(|V|^2)\). 图很小 (\(|V| \le 500\)) 或需要全源最短路时首选。 也可处理负权边 (但不能有负环).
-
易错点：三重循环里
k必须放最外层. 放错位置就不再是"逐步放开中转集合"，结果会错。
困难：网络延迟时间¶
- 问题：给定 \(n\) 个节点与有向带权边，求从源点出发信号传到所有节点所需的时间。 若无法到达全部节点则返回 -1.
def network_delay(times, n, k):
graph = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
graph[u].append((v, w))
dist = dijkstra(graph, k)
max_time = max(dist.values())
return max_time if max_time < float('inf') else -1
强连通分量¶
-
在有向图里，强连通分量 (Strongly Connected Component, SCC) 是一个极大的节点集合，集合内任意节点都能互相到达。
-
Kosaraju 算法: (1) 在原图上做 DFS，记录完成顺序。 (2) 转置图 (所有边反向). (3) 按完成顺序的逆序在转置图上做 DFS. 第 3 步中的每一棵 DFS 树就是一个 SCC.
-
何时用：找循环依赖、2-SAT、把有向图缩成 SCC 的有向无环图 (Directed Acyclic Graph, DAG).
-
Tarjan 算法 (Tarjan's SCC Algorithm)：与 Kosaraju 功能相同但只用一遍 DFS，不需要转置图。 它给每个节点记录两个时间戳：
disc(发现时间) 和low(能回溯到的最早的祖先的发现时间)，同时维护一个栈追踪当前路径上的节点。 当disc[u] == low[u]时，\(u\) 是一个 SCC 的根，从栈里弹出所有节点即构成一个 SCC.
def tarjan_scc(n, graph):
index = 0
stack = []
on_stack = [False] * n
disc = [-1] * n
low = [0] * n
sccs = []
def strongconnect(u):
nonlocal index
disc[u] = low[u] = index
index += 1
stack.append(u)
on_stack[u] = True
for v in graph[u]:
if disc[v] == -1: # 树边: 递归
strongconnect(v)
low[u] = min(low[u], low[v])
elif on_stack[v]: # 回边 / 栈中横叉边
low[u] = min(low[u], disc[v])
if low[u] == disc[u]: # u 是 SCC 根
comp = []
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u:
break
sccs.append(comp)
for v in range(n):
if disc[v] == -1:
strongconnect(v)
return sccs
- 关键区别: Tarjan 与 Kosaraju 都是 \(O(|V| + |E|)\)，但 Tarjan 一遍 DFS 搞定，常数更小，实际面试中更常用。 Kosaraju 思路更直观，需要两遍 DFS.
- ⚠️ low 的更新规则：对树边用
low[v]，对回边用disc[v](不是low[v]). 用low[v]更新回边可能导致跨越 SCC 边界的错误回溯。 - 何时用：需要缩点 (SCC 压缩为 DAG) 时；或像"最少添加几条边使图强连通"这类构造题。
常见易错点汇总¶
| 易错点 | 例子 | 修法 |
|---|---|---|
| 在出队时才标记 visited | 同一个节点被多次入队 | 入队时就标记 visited |
| 有向图里只用两种访问状态 | 分不清回边与横叉边 | 用三种状态：未访问 / 进行中 / 完成 |
| Dijkstra 遇到负权 | 最短路径算错 | 改用 Bellman-Ford |
忘写 if d > dist[node]: continue |
处理堆里的过期条目 | 当前距离更差就跳过 |
| 网格越界检查 | 下标越界 | 0 <= nr < rows and 0 <= nc < cols |
| 漏掉 time=0 的边界情况 | 腐烂橘子：一开始就没有新鲜橘子 | 在 BFS 之前先判断 fresh == 0 |
| 把有向图当无向图建 | 先修关系是单向的 | 只加一个方向的边 |
课后题 (NeetCode)¶
BFS 套路¶
- 岛屿数量 —— 网格 BFS/DFS
- 腐烂的橘子 —— 多源 BFS
- 克隆图 —— BFS + 哈希表克隆
- 太平洋大西洋水流问题 —— 从两个海洋同时 BFS
- 单词接龙 —— 在隐式图上做 BFS
DFS 套路¶
最短路径¶
- 网络延迟时间 —— Dijkstra
- K 站中转内最便宜的航班 —— 带约束的改造版 BFS / Bellman-Ford
- 水位上升的游泳池 —— 二分 + BFS 或网格上的 Dijkstra
进阶¶
- 外星字典 —— 根据字符顺序做拓扑排序
📌 本节要点¶
- BFS 与 DFS：图算法的两大基石，几乎所有图题都是二者的变体或组合。
- 邻接表 vs 邻接矩阵：稀疏图用邻接表 (\(O(|V| + |E|)\))，稠密图或需 \(O(1)\) 查边才用邻接矩阵 (\(O(|V|^2)\)).
- BFS 入队即标记：一定在入队时加入
visited，否则同一节点会被重复入队。 - 多源 BFS：把所有源头同时入队，得到的是"到任意源头"的最短距离，天然契合"所有目标最迟何时被覆盖"这类问题。
- DFS 三态法：有向图环检测必须用未访问 / 进行中 / 已完成三种状态，才能区分回边与横叉边。
- 拓扑排序 (Kahn 算法)：从入度为 0 的节点开始 BFS，若最终结果节点数少于总数就说明有环。
- Dijkstra 前提：只适用于非负权图；处理过期堆条目要靠
if d > dist[node]: continue那一行。 - 负权改用 Bellman-Ford：一旦有负权，Dijkstra 的贪心假设就失效；松弛 \(|V| - 1\) 轮，再多松一轮还能更新就说明有负权环。
- 全源最短路用 Floyd-Warshall: \(O(|V|^3)\) 三重循环，\(k\) 放最外层，图小 (\(|V| \le 500\)) 时首选。
- 强连通分量 (SCC): Kosaraju 两遍 DFS + 图转置，思路直观；Tarjan 一遍 DFS 用
disc / low时间戳 + 栈搞定，常数更小。 - 网格题 4 连通模板:
[(0,1),(0,-1),(1,0),(-1,0)]是所有网格 BFS/DFS 题的公共模板，务必背熟并配上越界检查。