登录以参加训练计划

好的！DFS（深度优先搜索）和BFS（广度优先搜索）是图/树遍历的两种核心策略，就像探索迷宫的两种不同方式。下面用超多图解+生活化案例帮你彻底掌握它们！🚀

---

🌟 核心对比

	DFS（深度优先）	BFS（广度优先）
策略	一条路走到黑，再回溯	层层推进，地毯式搜索
数据结构	栈（递归隐式栈）	队列
适用场景	寻找所有解、连通性问题	最短路径、状态层次遍历
空间复杂度	O(h)（h为深度）	O(w)（w为最宽层的节点数）
类比	走迷宫优先钻到底	水波纹扩散式搜索

---

🎮 图解理解

DFS示例（数字为访问顺序）：

   1
  / \
 2   5
/ \   \
3 4   6

访问顺序：1→2→3→4→5→6

BFS示例（数字为访问顺序）：

   1
  / \
 2   3
/ \   \
4 5   6

访问顺序：1→2→3→4→5→6

---

📚 DFS深度优先搜索

核心思想：递归 + 回溯

// 伪代码模板
void dfs(当前状态) {
    if(到达终止条件) {
        记录结果;
        return;
    }
    for(所有可能的选择) {
        if(选择合法) {
            做选择;
            dfs(新状态);
            撤销选择; // 回溯
        }
    }
}

经典应用：迷宫问题

// 迷宫矩阵：0可走，1障碍
int maze[5][5] = {
    {0,1,0,0,0},
    {0,1,0,1,0},
    {0,0,0,0,0},
    {0,1,1,1,0},
    {0,0,0,1,0}
};

bool dfs(int x, int y) {
    if(x<0 || x>=5 || y<0 || y>=5 || maze[x][y]==1) return false;
    if(x==4 && y==4) return true; // 到达终点
    
    maze[x][y] = 1; // 标记已访问
    // 四个方向探索
    if(dfs(x+1,y) || dfs(x-1,y) || dfs(x,y+1) || dfs(x,y-1)) {
        return true;
    }
    maze[x][y] = 0; // 回溯（如果需要找所有路径）
    return false;
}

---

🌊 BFS广度优先搜索

核心思想：队列 + 层级扩展

// 伪代码模板
void bfs(起始状态) {
    队列初始化;
    while(队列不空) {
        当前节点 = 队首出队;
        if(是目标状态) return;
        for(所有相邻节点) {
            if(未访问过且合法) {
                入队并标记;
            }
        }
    }
}

经典应用：最短路径问题

struct Node {
    int x, y, step;
};

int bfs() {
    queue<Node> q;
    q.push({0,0,0});
    maze[0][0] = 1; // 标记已访问
    
    int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        if(cur.x==4 && cur.y==4) return cur.step;
        
        for(int i=0; i<4; i++) {
            int nx = cur.x + dir[i][0];
            int ny = cur.y + dir[i][1];
            if(nx>=0 && nx<5 && ny>=0 && ny<5 && maze[nx][ny]==0) {
                maze[nx][ny] = 1;
                q.push({nx, ny, cur.step+1});
            }
        }
    }
    return -1; // 不可达
}

---

💡 应用场景对比

问题类型	DFS适用性	BFS适用性
所有可能路径	✅（全遍历）	❌
最短路径	❌（可能找到但非最优）	✅（保证最短）
连通块数量	✅（每个连通块启动一次DFS）	✅（同理）
拓扑排序	✅（后序遍历逆序）	✅（入度表+Kahn算法）

---

🚀 性能优化技巧

1. DFS剪枝

• 可行性剪枝：提前排除不可能的解
• 最优性剪枝：当前路径已不如已知最优解时停止

// 例：组合问题中剩余元素不足时提前返回
if(当前选择数 + 剩余元素数 < 需要总数) return;

2. BFS双向搜索

• 从起点和终点同时开始BFS，相遇时路径最短
• 适合状态空间大的问题（如八数码）

3. 记忆化搜索

• 记录已访问状态，避免重复计算

unordered_map<string, bool> visited; // 状态→是否访问

---

🌰 生活化案例

DFS：破解密码锁（暴力穷举）

• 每次转动一个数字轮盘，尝试所有组合
• 递归深度为密码位数

BFS：社交网络好友推荐

• 先推荐你的直接好友（1度关系）
• 再推荐好友的好友（2度关系）
• 以此类推，层次分明

---

📝 经典练习题

1. 岛屿数量（DFS/BFS均可）

   • 输入：二维网格，'1'陆地，'0'水
   • 输出：连通陆地的数量

2. 二叉树层序遍历（BFS经典）

   vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> res;
       queue<TreeNode*> q;
       if(root) q.push(root);
       while(!q.empty()) {
           int size = q.size();
           vector<int> level;
           for(int i=0; i<size; i++) {
               auto node = q.front(); q.pop();
               level.push_back(node->val);
               if(node->left) q.push(node->left);
               if(node->right) q.push(node->right);
           }
           res.push_back(level);
       }
       return res;
   }
   

3. 全排列问题（DFS回溯）

   vector<vector<int>> permute(vector<int>& nums) {
       vector<vector<int>> res;
       vector<bool> used(nums.size(), false);
       vector<int> path;
       function<void()> dfs = [&]() {
           if(path.size() == nums.size()) {
               res.push_back(path);
               return;
           }
           for(int i=0; i<nums.size(); i++) {
               if(!used[i]) {
                   used[i] = true;
                   path.push_back(nums[i]);
                   dfs();
                   path.pop_back();
                   used[i] = false;
               }
           }
       };
       dfs();
       return res;
   }
   

---

❗ 注意事项

1. DFS栈溢出：递归深度过大时改用迭代DFS或BFS
2. BFS空间爆炸：当分支因子大时，内存可能不足
3. 访问标记：无论是DFS还是BFS，必须标记已访问节点（尤其图遍历时）

需要哪道题的详细解析或更多代码示例吗？ 😊