DFS与BFS深度对比：选对搜索策略，解题快人一步

你已经认识了深度优先搜索（DFS）和广度优先搜索（BFS）这两位“搜索员”。它们都是在图或树中寻找目标的算法，但性格完全不同：DFS像冒险家，喜欢一条路走到黑；BFS像稳重的前锋，一圈一圈向前推进。了解它们的区别，能帮助你在解题时选择最合适的策略。

核心思想详解

深度优先搜索（DFS）—— 勇往直前，不撞南墙不回头

DFS 会从起点出发，沿着一条路径尽可能深地探索，直到无法继续（遇到死胡同或找到目标），然后回溯到上一个岔路口，换另一条路径继续。

生活例子：玩迷宫游戏时，你选择一直走右边的墙，碰到死路就退回来换一个方向。你只管往深处钻，直到把整个迷宫走遍。

用到的工具：栈（或递归）。栈记录了“回头路” —— 每当走到一个岔路口，就把当前岔路口压入栈，这样当你走到死路时，可以从栈顶弹出上一个岔路口，回到那里继续探索。递归本质上也使用了系统栈。

简单步骤（以图为例）：

从起点开始，标记已访问。
对于当前节点的每个未访问的邻居，递归地执行DFS。
如果所有邻居都已访问，则返回上一个节点（回溯）。

广度优先搜索（BFS）—— 稳扎稳打，步步为营

BFS 从起点出发，先探索所有与起点距离为1的节点，再探索距离为2的节点，以此类推，如同水波一样一圈一圈扩散。

生活例子：你在公园里找走失的小伙伴，会先检查周围的花坛、长椅，然后扩大范围到小树林、游乐场……确保不遗漏近处的地方。

用到的工具：队列。队列记录了“下一步该去哪里” —— 把当前层的所有节点依次放入队列，然后逐个取出，再放入它们的下一层邻居，先进先出，保证按层遍历。

简单步骤（以图为例）：

将起点放入队列并标记已访问。
当队列不为空时，取出队首节点。
对于该节点的每个未访问的邻居，将其放入队列并标记。
重复直到队列为空或找到目标。

深入对比：两位探险家的工作方式

项目	DFS	BFS
核心数据结构	栈（递归）	队列
搜索顺序	沿着一条路走到黑	一层一层扩散
空间占用	通常较小（只存当前路径上的节点）	可能很大（存所有下一层节点，尤其树很宽时）
是否找最短路径	否，可能绕远路，不一定最短	是，第一个找到的目标一定是路径最短的（在无权图中）
适用场景	解数独、全排列、检测连通性、寻找所有解	最短路径、网络广播、单词接龙、层次遍历

注意：在有权图中，BFS找的不一定是最短路径（需要Dijkstra算法），但在无权图（所有边代价相同）或迷宫移动一步代价为1时，BFS一定能找到最短路径。

新手常见错误

1. DFS递归导致栈溢出

DFS如果递归深度过大（例如图有几千层），系统栈会爆掉。解决方法：改用显式栈实现DFS，或者增加递归深度限制（不建议暴力增大）。

2. 忘记标记已访问节点

无论是DFS还是BFS，如果不标记已访问节点，会导致无限循环（把同一个节点反复入队/递归）。尤其在有环的图中，这是致命的错误。

错误示例（BFS中）：

while (!q.empty()) {
    int cur = q.front(); q.pop();
    for (int neighbor : graph[cur]) {
        q.push(neighbor);  // 忘记检查是否已访问，可能会死循环
    }
}

3. BFS中忘记按层处理

如果需要在BFS中记录路径长度，应该同时维护一个step变量，每处理完一层才增加，否则可能统计出错。

4. DFS回溯时状态恢复不当

在DFS回溯法中（如解数独、走迷宫），修改状态后一定要在递归返回后恢复，否则会影响其他分支的搜索。

完整可运行示例：迷宫找路

假设有一个5×5的迷宫，0表示空地，1表示障碍，2表示起点，3表示终点。我们用DFS找一条路径（任意一条），用BFS找最短路径（步数最少）。

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;

int maze[5][5] = {  // 迷宫地图，0空地，1障碍，2起点，3终点
    {2, 0, 1, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 1, 3}
};

int rows = 5, cols = 5;  // 行数和列数
int dx[] = {-1, 1, 0, 0};  // 上下左右四个方向的行偏移
int dy[] = {0, 0, -1, 1};  // 上下左右四个方向的列偏移

// ---------- DFS：找一条通往终点的路径（不保证最短） ----------
bool dfs(int x, int y, vector<vector<bool>>& visited, vector<pair<int,int>>& path) {
    // x, y：当前位置，visited：访问标记，path：记录路径
    if (x < 0 || x >= rows || y < 0 || y >= cols) return false;  // 出界
    if (maze[x][y] == 1 || visited[x][y]) return false;  // 障碍或已访问
    path.push_back({x, y});  // 记录当前点
    visited[x][y] = true;  // 标记已访问

    if (maze[x][y] == 3) return true;  // 到达终点

    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (dfs(nx, ny, visited, path)) return true;
    }

    // 四个方向都没找到终点，回溯：从路径中移除当前点
    path.pop_back();
    // 注意：这里不需要将 visited 重置为 false，因为这条路径不通，但其他路径可能经过这个点吗？
    // 在找任意一条路径时，通常不重置 visited，因为点已经走过，不走回头路。
    // 如果需要找所有路径，则要重置 visited。
    return false;
}

// ---------- BFS：找最短路径（最少步数） ----------
struct Point {
    int x, y;  // 坐标
    int step;  // 从起点到该点的步数
    Point* prev;  // 前驱节点，用于回溯路径（可选）
};

vector<pair<int,int>> bfs(int startX, int startY) {
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    queue<Point*> q;  // 队列中存放指向 Point 的指针，方便记录前驱

    // 起点
    Point* start = new Point{startX, startY, 0, nullptr};
    q.push(start);
    visited[startX][startY] = true;

    while (!q.empty()) {
        Point* cur = q.front(); q.pop();
        int x = cur->x, y = cur->y;

        if (maze[x][y] == 3) {  // 到达终点
            // 从终点沿前驱回溯路径
            vector<pair<int,int>> path;
            Point* p = cur;
            while (p != nullptr) {
                path.push_back({p->x, p->y});
                p = p->prev;
            }
            // 反转得到从起点到终点的顺序
            reverse(path.begin(), path.end());
            // 清理队列中剩余的指针（简单起见，此处省略，实际应该统一释放）
            return path;
        }

        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;  // 越界
            if (maze[nx][ny] == 1 || visited[nx][ny]) continue;  // 障碍或已访问
            visited[nx][ny] = true;
            Point* next = new Point{nx, ny, cur->step + 1, cur};
            q.push(next);
        }
    }
    // 没有找到终点，返回空路径
    return {};
}

int main() {
    // 找到起点位置（值为2）
    int startX, startY;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (maze[i][j] == 2) { startX = i; startY = j; }

    // ------ DFS ------
    cout << "DFS: 寻找一条路径（不保证最短）" << endl;
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> dfsPath;
    if (dfs(startX, startY, visited, dfsPath)) {
        cout << "找到路径，经过的坐标：";
        for (auto p : dfsPath)
            cout << "(" << p.first << "," << p.second << ") ";
        cout << endl;
    } else {
        cout << "没有路径！" << endl;
    }

    // ------ BFS ------
    cout << "BFS: 寻找最短路径" << endl;
    vector<pair<int,int>> bfsPath = bfs(startX, startY);
    if (!bfsPath.empty()) {
        cout << "最短路径步数：" << bfsPath.size() - 1 << " 步" << endl;  // 步数 = 节点数-1
        cout << "路径坐标：";
        for (auto p : bfsPath)
            cout << "(" << p.first << "," << p.second << ") ";
        cout << endl;
    } else {
        cout << "没有路径！" << endl;
    }

    return 0;
}

运行结果（示例）：

DFS: 寻找一条路径（不保证最短）
找到路径，经过的坐标：(0,0) (1,0) (1,1) (2,1) (3,1) (3,2) (3,3) (4,3) (4,4) 
BFS: 寻找最短路径
最短路径步数：6 步
路径坐标：(0,0) (1,0) (2,0) (3,0) (3,1) (3,2) (3,3) (4,3) (4,4)

可以看到，DFS找到的路径可能比BFS长（本例中DFS路径9个节点，步数8；BFS路径9个节点，步数8？实际上两者都是8步，但路径不同；如果迷宫更复杂，BFS一定能得到最短的）。

什么时候用谁？—— 决策指南

问题是“有没有路”（连通性）：例如迷宫是否有出口，图中两点是否连通。DFS更简单，代码量少，通常用递归即可。
问题是“最短的路是哪里”：例如从学校回家最少走几步，发消息到目标最少经过几个人。BFS是最佳选择（权重相同的图）。
搜索空间巨大，答案在深层：例如一个非常深的树，目标在叶子节点。DFS可能直接一路冲下去快速找到，而BFS可能需要遍历很多上层节点。
需要枚举所有解：例如全排列、八皇后、解数独。DFS配合回溯可以系统地列举所有可能性。
游戏中的逐层扩散：例如“六度空间”理论、感染传播。BFS可以模拟逐层传播的过程。

DFS与BFS比较：两条不同的探索之路