深度优先搜索（DFS）详解及C++实现

输出结果： DFS 遍历结果（递归）：0 1 2 3 4

说明：从节点 0 出发，先深入探索 1→2 分支，回溯后再探索 3→4 分支，最终遍历所有节点。

案例 2：二叉树的前序遍历（DFS）

二叉树的前序遍历（根→左→右）是 DFS 的典型应用，递归实现非常简洁。

#include <iostream>
using namespace std;

// 二叉树节点定义
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

// 递归实现前序遍历（DFS）
void preorderDFS(TreeNode* root){
    // 递归终止条件：节点为空
    if(root == nullptr){
        return;
    }
    // 访问根节点
    cout << root->val << " ";
    // 递归遍历左子树
    preorderDFS(root->left);
    // 递归遍历右子树
    preorderDFS(root->right);
}

int main(){
    // 构建一棵二叉树：
    // 1
    //  \ 
    //   2
    //  / 
    // 3
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    cout << "二叉树前序遍历（DFS）：";
    preorderDFS(root);
    cout << endl;
    // 释放内存（简化处理，实际应手动遍历释放）
    delete root->right->left;
    delete root->right;
    delete root;
    return 0;
}

输出结果： 二叉树前序遍历（DFS）：1 2 3

2. 非递归实现（手动栈）

当递归深度过大时（如遍历深度为 1e4 的树），会导致栈溢出（C++默认递归栈大小有限），此时需要用手动栈实现 DFS。核心逻辑与递归一致，只是将递归调用栈替换为手动维护的栈。

非递归实现步骤：

1. 将起始节点压入栈，标记为已访问；
2. 弹出栈顶节点，访问该节点；
3. 将该节点的所有未访问邻接节点压入栈（注意：为保证遍历顺序与递归一致，需逆序压入，因为栈是先进后出）；
4. 重复步骤 2-3，直到栈为空。

案例 1：无向图的 DFS 遍历（非递归）

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

vector<vector<int>> adj;
vector<bool> visited;

// 非递归实现 DFS（手动栈）
void dfsNonRecursive(int start){
    stack<int> st;
    // 压入起始节点，标记为已访问
    st.push(start);
    visited[start] = true;
    while(!st.empty()){
        // 弹出栈顶节点
        int u = st.top();
        st.pop();
        // 访问当前节点
        cout << u << " ";
        // 遍历邻接节点（逆序压入，保证遍历顺序与递归一致）
        for(auto it = adj[u].rbegin(); it != adj[u].rend();++it){
            int v = *it;
            if(!visited[v]){
                visited[v] = true;
                st.push(v);
            }
        }
    }
}

int main(){
    int n = 5;
    adj.resize(n);
    visited.resize(n, false);
    // 构建无向图（同递归案例）
    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[0].push_back(3); adj[3].push_back(0);
    adj[3].push_back(4); adj[4].push_back(3);
    cout << "DFS 遍历结果（非递归）：";
    dfsNonRecursive(0);
    cout << endl;
    return 0;
}

输出结果： DFS 遍历结果（非递归）：0 1 2 3 4

说明：这里对邻接节点逆序遍历（rbegin()和 rend()），是因为栈是'先进后出'的。如果直接正序压入，遍历顺序会变成 0→3→4→1→2，虽然也是 DFS，但与递归实现的顺序不一致（不影响遍历完整性，仅影响顺序）。

案例 2：二叉树的前序遍历（非递归 DFS）

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

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

// 非递归实现前序遍历（DFS）
void preorderDFSNonRecursive(TreeNode* root){
    if(root == nullptr){
        return;
    }
    stack<TreeNode*> st;
    // 压入根节点
    st.push(root);
    while(!st.empty()){
        // 弹出栈顶节点，访问
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        // 注意：先压右子树，再压左子树（栈先进后出，保证左子树先访问）
        if(node->right != nullptr){
            st.push(node->right);
        }
        if(node->left != nullptr){
            st.push(node->left);
        }
    }
}

int main(){
    // 构建与递归案例相同的二叉树
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    cout << "二叉树前序遍历（非递归 DFS）：";
    preorderDFSNonRecursive(root);
    cout << endl;
    // 释放内存
    delete root->right->left;
    delete root->right;
    delete root;
    return 0;
}

输出结果： 二叉树前序遍历（非递归 DFS）：1 2 3

四、DFS 的经典应用：回溯法求解 N 皇后问题

DFS 的核心是'探索 - 回溯'，而回溯法是 DFS 的一种延伸应用，常用于解决'选择 - 验证 - 回溯 - 再选择'的组合优化问题。N 皇后问题是回溯法的经典案例：在 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后不处于同一行、同一列或同一斜线上。

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

vector<vector<string>> result;
// 存储所有合法解

// 检查当前位置 (row, col) 是否可以放置皇后
bool isValid(int n,int row,int col, vector<string>& board){
    // 检查同一列是否有皇后
    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 < n;--i,++j){
        if(board[i][j]=='Q'){
            return false;
        }
    }
    return true;
}

// DFS 回溯函数：当前处理第 row 行
void backtrack(int n,int row, vector<string>& board){
    // 递归终止条件：所有行都处理完毕（找到一个合法解）
    if(row == n){
        result.push_back(board);
        return;
    }
    // 遍历当前行的每一列，尝试放置皇后
    for(int col = 0; col < n;++col){
        if(isValid(n, row, col, board)){
            // 选择：在当前位置放置皇后
            board[row][col]='Q';
            // 探索：处理下一行
            backtrack(n, row +1, board);
            // 回溯：撤销选择，恢复原状
            board[row][col]='.';
        }
    }
}

// 求解 N 皇后问题
vector<vector<string>> solveNQueens(int n){
    result.clear();
    // 初始化棋盘：n 行 n 列，全部为'.'
    vector<string>board(n,string(n,'.'));
    backtrack(n,0, board);
    return result;
}

// 打印所有解
void printResult(const vector<vector<string>>& result){
    for(auto& solution : result){
        cout << "=====================" << endl;
        for(auto& row : solution){
            cout << row << endl;
        }
    }
}

int main(){
    int n = 4;
    // 求解 4 皇后问题
    vector<vector<string>> solutions = solveNQueens(n);
    cout << n << "皇后问题共有 " << solutions.size() << " 个解：" << endl;
    printResult(solutions);
    return 0;
}

输出结果（4 皇后问题的 2 个解）：

4 皇后问题共有 2 个解：

.Q... ..Q. Q... ...Q

..Q. Q... ...Q .Q..

说明：该代码通过 DFS 回溯，逐行尝试放置皇后，每放置一个皇后就验证合法性，若合法则继续探索下一行，若不合法则回溯到上一行重新选择列。最终遍历出所有合法的放置方案。

五、DFS 的常见注意事项

• 避免重复访问：必须使用 visited 数组（或其他标记方式）标记已访问的节点，否则会陷入无限循环（尤其是图中有环的情况）；
• 递归深度控制：递归实现时，若问题规模过大（如 n=1e4），会导致栈溢出，此时需改用非递归实现；
• 回溯的撤销操作：回溯法中，每次选择后必须撤销选择（如 N 皇后问题中恢复 board[row][col]为'.'），否则会影响后续探索；
• 邻接表的构建：图的 DFS 遍历中，邻接表比邻接矩阵更高效（空间复杂度 O(V+E) vs O(V²)），适合稀疏图；
• 多连通分量处理：若图不连通，需遍历所有节点，对每个未访问的节点调用 DFS（如：for(int i=0; i<n; i++) if(!visited[i]) dfs(i);）。

六、总结

DFS 是一种基于'深度优先、回溯探索'的遍历算法，核心依赖栈（递归栈或手动栈）实现。其代码简洁、思想直观，广泛应用于图遍历、树遍历、排列组合、回溯优化等问题。

在 C++ 实现中，递归版本适合小规模问题，代码易写；非递归版本适合大规模问题，避免栈溢出。学习 DFS 的关键是理解'探索 - 回溯'的思想，以及如何通过标记和撤销操作控制遍历过程。