🚀 DFS、BFS 与回溯算法模板整理

---

一、图的 DFS 模板（递归）

void dfs(Node node, Set<Node> visited) {
    // 1. 终止条件
    if (node == null || visited.contains(node)) return;

    // 2. 标记访问
    visited.add(node);

    // 3. 访问当前节点
    System.out.println(node.val);

    // 4. 访问邻居节点
    for (Node neighbor : node.neighbors) {
        dfs(neighbor, visited);
    }
}

说明

• 使用 递归 + visited 集合 防止重复访问。
• 用于：图的连通性检测、路径搜索、环检测等。

class Node {
    String val;
    List<Node> neighbors;

    Node(String val) {
        this.val = val;
        this.neighbors = new ArrayList<>();
    }
}

---

二、树的 DFS 模板（递归）

void dfs(TreeNode root) {
    if (root == null) return;

    // 前序位置：访问节点
    System.out.println(root.val);

    dfs(root.left);
    dfs(root.right);
}

遍历类型说明

• 前序遍历：在递归前访问节点。
• 中序遍历：在左子树后、右子树前访问。
• 后序遍历：递归结束后访问节点。

---

三、图的 BFS 模板（通用）

void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.val);

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

要点

• 使用 队列（FIFO） 实现层级遍历。
• 每一层的节点都在队列中。
• 适用于 最短路径、层序遍历 等问题。

---

四、BFS 模板（带层次遍历）

void bfsWithLevel(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();  // 当前层的节点数
        System.out.print("Level " + level + ": ");

        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            System.out.print(node.val + " ");

            for (Node neighbor : node.neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        System.out.println();
        level++;
    }
}

---

五、树的 BFS 模板（层序遍历）

void levelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        System.out.println();
    }
}

---

六、DFS vs BFS 对比

维度	DFS	BFS
数据结构	栈 / 递归	队列
访问顺序	深入到底再回溯	一层层扩展
适用场景	连通性检测、路径搜索、拓扑排序	最短路径、层次遍历
空间复杂度	O(V)（递归深度）	O(V)（队列大小）
实现难度	简洁但容易栈溢出	稍复杂但稳定

---

七、模板使用技巧总结

技巧	说明
✅ visited 一定要在入队/入栈时标记	避免重复加入
✅ 图中有环必须判重	否则无限循环
✅ 树结构可省略 visited	因为树无环
✅ BFS 常配合“层计数”解决最短路径	常见于迷宫、网络传播
✅ DFS 可配合回溯（Backtracking）	常见于排列组合、路径问题

---

八、回溯算法（Backtracking）模板

回溯是一种 暴力搜索 + 剪枝优化 的算法思想。
其本质是：

DFS（深度优先搜索） + 状态恢复

通俗地说：

“选中一个 → 递归探索 → 不行撤销 → 换下一个”

通用模板（带剪枝优化）

void backtrack(路径 path, int start, 选择列表 choices) {
    if (满足结束条件) {
        保存结果(path);
        return;
    }

    for (int i = start; i < choices.length; i++) {
        // 剪枝：若不满足条件，直接跳过
        if (不合法(choices[i])) continue;

        // 做选择
        path.add(choices[i]);

        // 进入下一层
        backtrack(path, i + 1, choices);

        // 撤销选择（回溯）
        path.remove(path.size() - 1);
    }
}

---

九、回溯算法常见应用

类型	示例	关键点
组合问题	LeetCode 77 组合	不考虑顺序，使用 start 控制重复
排列问题	LeetCode 46 全排列	考虑顺序，需 used[] 数组标记
子集问题	LeetCode 78 子集	每层都可以收集结果
棋盘搜索	N 皇后、数独	二维递归 + 剪枝关键
字符串切割	分割回文串	注意递归中切割位置变化

---