搜索算法详解：DFS 与 BFS

搜索的本质

搜索算法本质上是在一个"状态空间"中寻找目标。想象你在迷宫中找出口：

• DFS（深度优先）：一条路走到底，走不通再回头
• BFS（广度优先）：从近到远，逐层探索

两种策略各有优势，适用于不同场景。

深度优先搜索（DFS）

基本思想

DFS 使用栈（或递归）来实现：

1. 从起点出发，沿着一条路径一直走
2. 遇到死路就回退（回溯）
3. 尝试其他分支
4. 直到找到目标或遍历完所有路径

经典模板

递归实现

int n, m;
char maze[105][105];
bool visited[105][105];

int dx[] = {0, 0, 1, -1};  // 四个方向
int dy[] = {1, -1, 0, 0};

bool dfs(int x, int y) {
    // 到达终点
    if (maze[x][y] == 'E') return true;
    
    // 标记已访问
    visited[x][y] = true;
    
    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 检查边界和是否可通行
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
            !visited[nx][ny] && maze[nx][ny] != '#') {
            if (dfs(nx, ny)) return true;
        }
    }
    
    return false;  // 没找到
}

栈实现

#include <stack>

bool dfs_stack(int startX, int startY) {
    stack<pair<int, int>> st;
    st.push({startX, startY});
    visited[startX][startY] = true;
    
    while (!st.empty()) {
        auto [x, y] = st.top();
        st.pop();
        
        if (maze[x][y] == 'E') return true;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                !visited[nx][ny] && maze[nx][ny] != '#') {
                visited[nx][ny] = true;
                st.push({nx, ny});
            }
        }
    }
    
    return false;
}

DFS 的典型应用

经典例题：全排列

int n;
int perm[10];
bool used[10];

void dfs(int pos) {
    if (pos == n) {
        // 输出排列
        for (int i = 0; i < n; i++) cout << perm[i] << " ";
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[pos] = i;
            dfs(pos + 1);
            used[i] = false;  // 回溯
        }
    }
}

广度优先搜索（BFS）

基本思想

BFS 使用队列来实现：

1. 从起点出发，先访问所有相邻节点
2. 然后访问这些节点的相邻节点
3. 一层一层向外扩展
4. 直到找到目标或遍历完所有节点

经典模板

#include <queue>

int n, m;
char maze[105][105];
int dist[105][105];  // 记录距离

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(int startX, int startY) {
    memset(dist, -1, sizeof(dist));
    
    queue<pair<int, int>> q;
    q.push({startX, startY});
    dist[startX][startY] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 到达终点
        if (maze[x][y] == 'E') {
            return dist[x][y];
        }
        
        // 扩展四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                dist[nx][ny] == -1 && maze[nx][ny] != '#') {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 无法到达
}

BFS 的典型应用

经典例题：迷宫最短路径

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

int shortestPath(int startX, int startY) {
    queue<Node> q;
    q.push({startX, startY, 0});
    visited[startX][startY] = true;
    
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        
        if (maze[cur.x][cur.y] == 'E') {
            return cur.steps;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                !visited[nx][ny] && maze[nx][ny] != '#') {
                visited[nx][ny] = true;
                q.push({nx, ny, cur.steps + 1});
            }
        }
    }
    
    return -1;
}

DFS vs BFS 对比

双向 BFS

对于状态空间很大的问题，可以使用双向 BFS 优化：

// 从起点和终点同时开始搜索
int bidirectionalBfs(int startX, int startY, int endX, int endY) {
    map<pair<int,int>, int> distFromStart, distFromEnd;
    queue<pair<int,int>> qStart, qEnd;
    
    qStart.push({startX, startY});
    qEnd.push({endX, endY});
    distFromStart[{startX, startY}] = 0;
    distFromEnd[{endX, endY}] = 0;
    
    while (!qStart.empty() || !qEnd.empty()) {
        // 从起点扩展一层
        if (!qStart.empty()) {
            auto [x, y] = qStart.front(); qStart.pop();
            if (distFromEnd.count({x, y})) {
                return distFromStart[{x, y}] + distFromEnd[{x, y}];
            }
            // ... 扩展邻居
        }
        
        // 从终点扩展一层
        if (!qEnd.empty()) {
            auto [x, y] = qEnd.front(); qEnd.pop();
            if (distFromStart.count({x, y})) {
                return distFromStart[{x, y}] + distFromEnd[{x, y}];
            }
            // ... 扩展邻居
        }
    }
    
    return -1;
}

实战技巧

1. 状态压缩

对于网格问题，可以用 visited[x][y] 标记。但对于复杂状态，需要编码：

// 例如：位置 + 剩余步数
int state = x * 1000 + y * 10 + steps;

2. 剪枝

// 剪枝：如果当前路径已经不可能更优，直接返回
if (currentSteps >= best) return;

3. 记忆化

int memo[105][105];

int dfs(int x, int y) {
    if (memo[x][y] != -1) return memo[x][y];
    // ... 计算
    return memo[x][y] = result;
}

练习建议

---

核心要点：DFS 善于"深挖"，BFS 善于"广撒"。选择哪种取决于问题需求！