深度优先搜索 DFS

用于：全排列、组合、连通块、树遍历、回溯、强连通分量（Tarjan）等。

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
}

回溯模板（排列 / 子集 / N 皇后）：

void backtrack(int step) {
    if (step == n) { record_answer(); return; }
    for (int choice : choices_at(step)) {
        if (!valid(choice)) continue;
        apply(choice);
        backtrack(step + 1);
        undo(choice);
    }
}

剪枝

• 可行性剪枝：当前状态已不可能得到合法解（如和已超过目标）
• 最优性剪枝：当前代价已 $\ge$ 已知最优解（求最小值时）
• 排序后搜索：分支按代价排序，配合最优性剪枝效果更好
• 记忆化：状态空间可哈希或编号时，避免重复 DFS

广度优先搜索 BFS

用于：无权图最短路、层次遍历、状态空间最短路（如棋盘最少步数）。

queue<int> q;
q.push(start); dist[start] = 0;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u])
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
}

状态 BFS：将「局面」编码为整数或结构体入队，注意去重（unordered_set 或 vis 数组）。

双向 BFS

起点、终点同时扩展，相遇时层数之和即为答案，状态空间呈指数时效果明显。

记忆化搜索

DFS + 数组缓存结果，是自顶向下 DP，适合状态多、转移写递归更直观（数位 DP、树形 DP）。

迭代加深 DFS（IDDFS）

在深度限制下反复 DFS，适合解可能在较深层但分支因子大的情况，空间 $O(d)$ 优于 BFS 的 $O(分支^d)$。

例题

例 1：迷宫最短路（BFS）
$n \times m$ 网格，. 可走 # 障碍，求 $(1,1)$ 到 $(n,m)$ 最少步数。四方向扩展，dist 初值 $-1$，第一次到达即最短。复杂度 $O(nm)$。

例 2：N 皇后（回溯 + 剪枝）
在 $n \times n$ 棋盘放 $n$ 个皇后互不攻击。按行 DFS 选列，用数组记录列、主对角线、副对角线是否占用；可行性剪枝跳过冲突列。$n=8$ 时即可秒出，$n \le 12$ 常用。