回溯框架
DFS 搜索决策树，试探 + 回退。
def subsets(nums):
out, path = [], []
def dfs(start):
out.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
排列：每层选未 used 元素。组合：start 递增避免重复。剪枝：排序后 if i > start and nums[i]==nums[i-1]: continue。
N 皇后 / 数独
按行放皇后，列与对角线用 set 标记冲突。数独：找空格，试 1-9，失败回溯。
图表示
- 邻接表：稀疏图，空间 O(V+E)。
- 邻接矩阵：稠密图，O(1) 查边。
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)BFS / DFS 图遍历
需 visited 防环。无权最短路 BFS；连通分量 DFS/BFS 计数。
拓扑排序
课程表：检测环 + 输出顺序。
def topo_sort(n, edges):
indeg = [0] * n
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
indeg[v] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
order = []
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else []并查集 Union-Find
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.r = [0] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.r[ra] < self.r[rb]:
ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra] == self.r[rb]:
self.r[ra] += 1
return True
用于：连通性、Kruskal 最小生成树、冗余连接。
最短路径预习
Dijkstra（非负权）、Bellman-Ford（负权）。Week 7 分布式不展开，算法岗可加深。
练习
回溯：子集、组合总和、全排列、括号生成。图：岛屿数量、课程表、冗余连接。与 week02-tree-dfs-bfs 对比：图需 visited，树可无。
剪枝与复杂度分析
回溯时间复杂度常写 O(2^n) 或 O(n!)，面试应说明 搜索树节点数上界 与剪枝如何缩小。N 皇后按列放，列/对角线 O(1) 判冲突。组合总和可排序后 if i>start and nums[i]==nums[i-1]: continue 去重。图 DFS 注意 递归栈深度，大图改迭代栈或显式路径数组。
并查集与最小生成树
Kruskal：边排序 + union 判环，适合稀疏图。Prim：堆优化稠密图。面试常问「何时 BFS 优于 DFS」→ 无权最短路、层数；DFS 适合路径存在性、连通分量计数。拓扑排序检测环是 课程表 标准解，与后端任务依赖调度场景类比。
工程联系
编译器依赖分析、Makefile 目标、服务启动顺序都可用拓扑。并查集在 连通网络、冗余连接、朋友圈 题出现。完成本篇后做 LeetCode 中等回溯 2 题 + 图 BFS 1 题，口述状态空间树。
补充要点
图染色、岛屿系列是 DFS/BFS 模板题。Dijkstra 用堆优化最短路，负权边不能用。拓扑 BFS 入度数组写法要熟练。回溯排列用 used 数组，组合用 start 参数。
经典题型拆解
全排列：每层从 0..n-1 选未 used 下标，复杂度 O(n×n!)。组合总和：排序后剪枝 if sum>target: break。子集：每个元素选或不选，DFS 深度 n。单词搜索：网格 DFS + 回溯，同 cell 不能重复使用 visited。岛屿数量：网格四连通 DFS 计数。面试写代码前先说明状态变量与回溯撤销，避免漏 path.pop()。
图论口述模板
无向图邻接表存双向边；有向图注意入度。BFS 模板 dist[start]=0 队列扩展。拓扑失败即存在环。并查集 find 路径压缩，union 按秩合并。与 week02-tree-dfs-bfs 对比：树无环，图必须 visited 防 infinite loop。