C++回溯算法之深度优先搜索详细介绍

什么是深度优先搜索

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，我们按深度优先顺序访问每个节点，尽可能深地探索每个节点的分支，直到达到最深处，然后返回到该节点的上一级分支。

深度优先搜索的算法框架

深度优先搜索的算法框架可以表示成以下伪代码：

dfs(node)
{
    if (node is a leaf node)
        print result
    else
        for each child of node
            dfs(child)
}

C++实现深度优先搜索

下面的C++代码展现了如何用深度优先搜索算法遍历一颗树：

// 用于存储节点的值
vector<int> nodes;

// 深度优先搜索遍历树的函数
void dfs(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    nodes.push_back(node->val); // 存储节点的值
    dfs(node->left);  // 遍历左子树
    dfs(node->right); // 遍历右子树
}

上面代码中，vector nodes 存储了遍历到的每个节点的值，函数 dfs 接受一个指向根节点的指针 node 作为参数，遍历整个树。当节点为空时直接返回，否则存储当前节点的值，接着递归访问其左右子树。

深度优先搜索用于解决问题

深度优先搜索算法与回溯算法紧密相关，因为回溯算法的核心就是深度优先搜索。回溯算法属于暴力求解算法中的一种，主要用于解决一些求所有解或最优解问题。通过深度优先搜索，回溯算法可以快速遍历所有可能的情况，并找出最优解或所有可能的解。

示例1：N皇后问题

下面我们以N皇后问题为例讲解回溯算法的应用。

在N皇后问题中，给定一个N*N大小的棋盘，要求放置N个皇后，使得每个皇后都不在同一行、同一列或同一斜线上。

下面是N皇后问题的代码实现：

const int N = 20; // 棋盘大小
int board[N][N]; // 棋盘
vector<vector<int>> res; // 存储所有的解

// 检查在(x,y)位置放置皇后是否合法
bool isValid(int x, int y) {
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == 1 && (j == y || abs(x - i) == abs(y - j))) {
                return false;
            }
        }
    }
    return true;
}

// 回溯算法，通过深度优先搜索解决N皇后问题
void dfs(int x) {
    if (x == N) {
        vector<int> v;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (board[i][j] == 1) {
                    v.push_back(j+1); // 存储皇后的位置
                }
            }
        }
        res.push_back(v); // 存储解
        return;
    }

    for (int j = 0; j < N; ++j) {
        if (isValid(x, j)) {
            board[x][j] = 1; // 放置皇后
            dfs(x+1); // 遍历下一行
            board[x][j] = 0; // 撤销皇后
        }
    }
}

int main() {
    memset(board, 0, sizeof(board));
    dfs(0); // 从第0行开始遍历
    return 0;
}

上面代码中，我们用一个二维数组 board 存储棋盘，用 1 表示有皇后，0 表示没有皇后。在函数 isValid 中，我们检查在 (x,y) 位置放置皇后是否合法，如果不合法返回 false，否则返回 true。在函数 dfs 中，我们从第0行开始遍历，对于每行，在每个列中遍历，找到可行的位置放置一个皇后，并递归到下一行继续遍历，如果所有行都遍历完了，就存储一组解，然后返回上一行撤回皇后，接着在该行继续遍历下一个位置。

示例2：连通图问题

下面我们以连通图问题为例讲解如何用深度优先搜索算法找到连通分量。

在连通图问题中，我们需要找到图中的所有连通分量。连通图的定义是：无向图中，如果从节点A到节点B有路径相通，则称A和B是连通的。

下面是连通图问题的代码实现：

const int N = 100; // 图中的最大节点数
int vis[N]; // 记录每个节点是否被访问过

// 深度优先搜索访问整个连通分量
void dfs(int x, vector<int>& v, vector<vector<int>>& res, vector<vector<int>>& g) {
    vis[x] = 1; // 标记为访问过
    v.push_back(x); // 存储节点
    for (auto y : g[x]) { // 遍历所有相邻节点
        if (vis[y] == 0) { // 如果该节点未被访问过
            dfs(y, v, res, g); // 递归遍历
        }
    }
}

// 找到图中所有的连通分量
vector<vector<int>> findConnectedComponents(vector<vector<int>>& g) {
    vector<vector<int>> res; // 存储所有连通分量
    memset(vis, 0, sizeof(vis)); // 初始化访问状态
    for (int i = 0; i < g.size(); ++i) { // 遍历所有的节点
        if (vis[i] == 0) { // 如果该节点未被访问过
            vector<int> v; // 存储连通分量
            dfs(i, v, res, g); // 访问该连通分量
            res.push_back(v); // 存储该连通分量
        }
    }
    return res;
}

int main() {
    // 定义一个无向图
    vector<vector<int>> g = {{1, 2}, {0, 2}, {0, 1}, {3, 4}, {3, 5}, {4}};
    // 找到所有连通分量
    vector<vector<int>> res = findConnectedComponents(g);
    // 输出所有连通分量
    for (auto v : res) {
        for (auto x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}

上面代码中，我们用一个二维数组 g 存储无向图，每个节点都是一个数字，相邻节点之间用 vector 存储。函数 dfs 负责访问所有连通节点，递归访问与当前节点相邻的所有节点，存储该节点，并标记为访问过。函数 findConnectedComponents 从根节点遍历整个图，找到所有的连通分量。当图中还有未被访问的节点时，就说明还有一个连通分量，递归访问该连通分量，并将该连通分量存储于 res 向量中。最后，函数返回所有的连通分量。

总结

本文介绍了深度优先搜索（DFS）的基本算法和实现方法，以及深度优先搜索用于解决问题的方法和示例。深度优先搜索常用于解决回溯算法类问题和图论问题。深度优先搜索的时间复杂度为 $O(V+E)$，其中 $V$ 表示节点数，$E$ 表示边数。若表示方式为邻接表，空间复杂度为 $O(V+E)$。要注意，深度优先搜索算法会占用较大的程序堆栈空间，如果树或图比较大，可能导致栈溢出的问题。