C++ DFS深度优先搜索全解

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索树的分支，直到无法继续为止，然后回溯到上一个节点继续搜索。以下将详细讲解DFS在各类问题中的应用及优化方法。

---

DFS走迷宫

迷宫问题通常涉及从起点到终点的路径搜索。DFS通过递归或栈结构实现路径探索。

算法步骤：

• 定义迷宫矩阵，标记起点和终点。
• 从起点出发，依次尝试四个方向（上、下、左、右）。
• 若当前方向可走且未被访问，则标记为已访问并递归进入下一步。
• 若到达终点，记录路径；否则回溯并尝试其他方向。

代码示例：

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> maze = {
    {0, 1, 0, 0},
    {0, 1, 1, 0},
    {0, 0, 0, 0},
    {0, 1, 1, 0}
};
vector<vector<bool>> visited(4, vector<bool>(4, false));

bool dfs(int x, int y, int endX, int endY) {
    if (x == endX && y == endY) return true;
    if (x < 0 || x >= 4 || y < 0 || y >= 4 || maze[x][y] == 1 || visited[x][y]) 
        return false;
    visited[x][y] = true;
    if (dfs(x + 1, y, endX, endY) || dfs(x - 1, y, endX, endY) || 
        dfs(x, y + 1, endX, endY) || dfs(x, y - 1, endX, endY)) 
        return true;
    visited[x][y] = false;
    return false;
}

---

DFS解决八皇后问题

八皇后问题要求在8×8棋盘上放置8个皇后，使其互不攻击。DFS通过回溯尝试所有可能的放置方式。

算法步骤：

• 按行放置皇后，依次尝试每一列。
• 检查当前位置是否与已放置皇后冲突（同列、对角线）。
• 若冲突则跳过；否则递归放置下一行。
• 若所有行放置完成，记录解。

代码示例：

#include <vector>
#include <iostream>
using namespace std;

vector<vector<string>> solutions;

bool isValid(vector<string>& board, int row, int col) {
    for (int i = 0; i < row; ++i) 
        if (board[i][col] == 'Q') return false;
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) 
        if (board[i][j] == 'Q') return false;
    for (int i = row - 1, j = col + 1; i >= 0 && j < 8; --i, ++j) 
        if (board[i][j] == 'Q') return false;
    return true;
}

void dfs(vector<string>& board, int row) {
    if (row == 8) {
        solutions.push_back(board);
        return;
    }
    for (int col = 0; col < 8; ++col) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            dfs(board, row + 1);
            board[row][col] = '.';
        }
    }
}

---

DFS图的遍历

DFS可用于遍历图中的所有节点，适用于无向图和有向图。

算法步骤：

• 从起始节点开始，标记为已访问。
• 递归访问所有未访问的相邻节点。
• 使用邻接表或邻接矩阵存储图结构。

代码示例：

#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};
vector<bool> visited(4, false);

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) 
        if (!visited[neighbor]) dfs(neighbor);
}

---

DFS无效路径优化与剪枝

剪枝通过提前终止无效分支提升效率，常见于组合优化问题。

剪枝策略：

• 可行性剪枝：当前路径不满足约束条件时终止。
• 最优性剪枝：当前路径已劣于已知最优解时终止。

示例：数独求解

bool isValid(vector<vector<char>>& board, int row, int col, char c) {
    for (int i = 0; i < 9; ++i) {
        if (board[row][i] == c) return false;
        if (board[i][col] == c) return false;
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) 
            return false;
    }
    return true;
}

bool solveSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; ++c) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solveSudoku(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

---

DFS的回溯机制

回溯是DFS的核心特性，通过撤销选择尝试其他可能性。

关键点：

• 选择：尝试一个候选解。
• 约束：检查是否满足条件。
• 目标：确认是否完成解。
• 撤销：回溯到上一步。

示例：全排列问题

void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& path) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int num : nums) {
        if (find(path.begin(), path.end(), num) != path.end()) continue;
        path.push_back(num);
        backtrack(nums, res, path);
        path.pop_back();
    }
}

---

DFS在社会中的普及

DFS不仅是算法竞赛的必备技能，还广泛应用于实际场景：

• 路径规划：GPS导航、机器人寻路。
• 游戏开发：迷宫生成、AI决策树。
• 网络爬虫：深度优先抓取网页链接。
• 社交网络分析：好友关系链的深度探索。

案例：社交网络好友推荐 DFS可用于遍历用户的好友关系链，发现潜在好友或社区结构。例如，通过深度遍历用户A的好友列表，推荐其好友的好友中未直接关联的用户。

---

总结

DFS通过递归或栈实现深度遍历，适用于路径搜索、组合问题、图遍历等场景。结合剪枝和回溯可大幅提升效率，其思想在技术和社会领域均有深远影响。

以下是DFSC++风格的伪代码实现，采用递归和迭代两种常见写法，并附简要说明：

C++伪代码

递归实现

void DFS_recursive(int node, vector<bool>& visited, const vector<vector<int>>& graph) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            DFS_recursive(neighbor, visited, graph);
        }
    }
}

• 标记当前节点为已访问
• 遍历所有未访问的相邻节点递归调用

迭代实现（使用栈）

void DFS_iterative(int start, vector<bool>& visited, const vector<vector<int>>& graph) {
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                s.push(neighbor);
            }
        }
    }
}

• 初始化栈并压入起始节点
• 每次弹出栈顶节点处理
• 将未访问的邻居压入栈并标记

参数说明

• graph：邻接表表示的图结构（vector<vector<int>>）
• visited：记录节点访问状态的布尔数组
• node/start：当前处理的节点索引

复杂度分析

• 时间：O(V+E)（V为顶点数，E为边数）
• 空间：递归实现受调用栈深度影响，迭代实现显式使用栈结构

实际使用时需根据图的具体表示法调整邻接节点的访问方式。对于大规模图，迭代实现通常更安全以避免栈溢出。