Appearance
图搜索、回溯与并查集
本章处理“状态之间存在连接关系”的问题:DFS/BFS 遍历显式或隐式图,回溯枚举决策树,并查集维护动态连通分量。三者都涉及搜索空间,但解决目标和状态维护方式不同。
图、网格与 Flood Fill
网格题可把每个格点视为图节点。开始前先确定方向数(四方向或八方向)、访问条件、访问标记,以及是否允许修改原网格。
cpp
constexpr int dr[] = {-1, 1, 0, 0};
constexpr int dc[] = {0, 0, -1, 1};
void dfs(int row, int col) {
visited[row][col] = true; // 进入时立即标记,防止环中重复访问
for (int direction = 0; direction < 4; ++direction) {
const int nr = row + dr[direction];
const int nc = col + dc[direction];
if (inside(nr, nc) && !visited[nr][nc] && allowed(nr, nc)) {
dfs(nr, nc);
}
}
}- 岛屿数量 / 面积:扫描到未访问陆地就计数一次并 flood fill;
- 被围绕区域:从边界合法节点反向标记,最后处理未标记区域;
- 多源 BFS:把所有起点同时入队,例如腐烂橘子、最近距离;
- 最短无权路径:使用 BFS,并在入队时标记,避免重复入队;
- 带非负权最短路:使用 Dijkstra,而不是普通 BFS。
递归 DFS 在深图或大网格上可能栈溢出,需要时改用显式 std::stack;图中存在环时必须维护访问状态。
回溯:枚举决策树
回溯用于组合、排列、子集、切分和棋盘搜索。每层明确当前路径、候选集合、终止条件与剪枝规则:
cpp
void backtrack(int start) {
if (is_complete()) {
answers.push_back(path);
return;
}
for (int i = start; i < static_cast<int>(choices.size()); ++i) {
if (!valid(choices[i])) continue;
path.push_back(choices[i]);
backtrack(next_start(i));
path.pop_back(); // 撤销选择
}
}- 排列:用
used[i]保证一个元素只选一次,下一层通常仍从 0 开始; - 组合 / 子集:传
start,下一层从i + 1开始,避免顺序不同造成重复; - 允许重复选取:下一层可以仍从
i开始; - 含重复元素去重:先排序,同一递归层使用
i > start && nums[i] == nums[i - 1]跳过; - 棋盘题:选择后要恢复现场;可用列和对角线集合把合法性检查降为 O(1)。
回溯最坏通常是指数级。排序、剩余元素不足、目标上下界和可行性预判等剪枝决定实际效率;剪枝前要证明不会丢失合法解。
并查集(Union-Find)
并查集适合动态维护“哪些节点属于同一连通块”,常用于连通块数量、冗余边检测、账户合并和 Kruskal 最小生成树。
cpp
class DSU {
public:
explicit DSU(int n) : parent_(n), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
return parent_[x] == x ? x : parent_[x] = find(parent_[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size_[a] < size_[b]) std::swap(a, b);
parent_[b] = a;
size_[a] += size_[b];
return true;
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};路径压缩加按大小 / 按秩合并后,单次操作均摊为 O(α(n)),其中反阿克曼函数增长极慢。并查集擅长连通性,不直接给出具体路径,也不能高效处理任意删边;这类需求通常需要其他动态图结构或离线逆序技巧。
如何选择
| 目标 | 常见选择 |
|---|---|
| 遍历所有可达状态 | DFS / BFS |
| 无权图最短路径 | BFS |
| 枚举所有满足约束的方案 | 回溯 + 剪枝 |
| 反复合并集合并查询连通性 | 并查集 |
| 非负权图最短路径 | Dijkstra |