C++ 实现深度优先搜索

深度优先搜索（DFS）概述

深度优先搜索（Depth - First Search，DFS）是一种用于遍历或搜索图或树结构的算法。它的核心思想是尽可能深地探索一个分支，直到无法继续或达到目标节点，然后回溯到前一个节点，继续探索其他分支。

想象你在一个迷宫中，DFS 就像是沿着一条通道一直走，直到遇到死胡同或者出口。当遇到死胡同的时候，就退回到上一个岔路口，尝试另一条通道。这种搜索策略优先深入到图或树的内部，而不是在同一层广泛地探索。

在图中，DFS 从给定的起始节点开始，标记该节点为已访问，然后递归地访问与它相邻且未被访问的节点。对于树结构，DFS 从根节点开始，递归地探索左子树和右子树（对于二叉树而言）。

C++ 实现深度优先搜索

图的表示

在实现 DFS 之前，我们需要先确定如何在 C++ 中表示图。常见的图表示方法有邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一个二维数组 graph[n][n]，其中 n 是图中节点的数量。如果节点 i 和节点 j 之间有边相连，则 graph[i][j] = 1（对于无向图，graph[j][i] 也为 1）；如果没有边相连，则 graph[i][j] = 0。以下是一个简单的邻接矩阵表示图的示例代码：

#include <iostream>
#include <vector>

const int MAXN = 100;
bool graph[MAXN][MAXN];

void addEdge(int u, int v) {
    graph[u][v] = true;
    graph[v][u] = true;
}

邻接表

邻接表则是一种更加节省空间的表示方法，尤其是对于稀疏图（边的数量远小于节点数量的平方）。它使用一个数组 adj，其中 adj[i] 是一个链表（或 std::vector），存储了与节点 i 相邻的所有节点。以下是用 std::vector 实现邻接表的代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[MAXN];

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

递归实现 DFS

在 C++ 中，使用递归实现 DFS 非常直观。以下是基于邻接表的递归 DFS 实现代码：

#include <iostream>
#include <vector>
#include <cstring>

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    cout << "请输入节点数量 n 和边数量 m: ";
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cout << "请输入边的两个端点 u 和 v: ";
        cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));
    cout << "深度优先搜索结果: ";
    dfs(0); // 从节点 0 开始搜索
    return 0;
}

在上述代码中：

1. visited 数组用于记录每个节点是否被访问过。
2. dfs 函数是递归实现的核心。它首先标记当前节点 u 为已访问，然后输出该节点。接着，遍历与 u 相邻的所有节点 v，如果 v 未被访问，则递归调用 dfs(v)。
3. 在 main 函数中，我们首先读取图的节点数量 n 和边数量 m，然后读取每条边的两个端点，并构建邻接表。最后，从节点 0 开始调用 dfs 进行深度优先搜索。

非递归实现 DFS

虽然递归实现简洁明了，但对于大型图，可能会导致栈溢出问题。此时，可以使用栈来实现非递归的 DFS。以下是基于邻接表的非递归 DFS 实现代码：

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfsNonRecursive(int u) {
    stack<int> stk;
    stk.push(u);
    visited[u] = true;

    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();
        cout << current << " ";

        for (int i = adj[current].size() - 1; i >= 0; --i) {
            int v = adj[current][i];
            if (!visited[v]) {
                stk.push(v);
                visited[v] = true;
            }
        }
    }
}

int main() {
    int n, m;
    cout << "请输入节点数量 n 和边数量 m: ";
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cout << "请输入边的两个端点 u 和 v: ";
        cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));
    cout << "深度优先搜索结果: ";
    dfsNonRecursive(0); // 从节点 0 开始搜索
    return 0;
}

在非递归实现中：

1. 使用 std::stack 来模拟递归调用栈。
2. 首先将起始节点 u 压入栈，并标记为已访问。
3. 在 while 循环中，不断弹出栈顶元素 current 并输出。然后，逆序遍历与 current 相邻的节点 v，如果 v 未被访问，则将其压入栈并标记为已访问。

DFS 在实际问题中的应用

迷宫求解

迷宫可以看作是一个图，每个格子是一个节点，相邻格子之间的通道是边。通过 DFS 可以找到从起点到终点的路径。以下是一个简单的迷宫求解示例代码：

#include <iostream>
#include <vector>
#include <cstring>

const int ROWS = 5;
const int COLS = 5;
char maze[ROWS][COLS] = {
    {'S', '.', '.', '.', '.'},
    {'.', '#', '.', '#', '.'},
    {'.', '.', '.', '.', '.'},
    {'.', '#', '#', '#', '.'},
    {'.', '.', '.', '#', 'E'}
};
bool visited[ROWS][COLS];
std::vector<std::pair<int, int>> path;

bool isValid(int x, int y) {
    return x >= 0 && x < ROWS && y >= 0 && y < COLS && maze[x][y] != '#' &&!visited[x][y];
}

bool dfs(int x, int y) {
    if (x < 0 || x >= ROWS || y < 0 || y >= COLS || maze[x][y] == '#' || visited[x][y]) {
        return false;
    }

    visited[x][y] = true;
    path.push_back({x, y});

    if (maze[x][y] == 'E') {
        return true;
    }

    if (dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1)) {
        return true;
    }

    path.pop_back();
    return false;
}

int main() {
    memset(visited, false, sizeof(visited));
    if (dfs(0, 0)) {
        std::cout << "找到路径: " << std::endl;
        for (const auto& p : path) {
            std::cout << "(" << p.first << ", " << p.second << ") ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "未找到路径" << std::endl;
    }
    return 0;
}

在上述代码中：

1. maze 数组表示迷宫，S 表示起点，E 表示终点，# 表示墙壁，. 表示通道。
2. visited 数组用于记录每个格子是否被访问过。
3. path 向量用于存储从起点到终点的路径。
4. isValid 函数用于判断一个格子是否合法（在迷宫范围内且不是墙壁且未被访问）。
5. dfs 函数递归地探索从当前格子出发的所有可能路径。如果找到终点，则返回 true，并将路径记录在 path 中。如果没有找到，则回溯并将当前格子从路径中移除。

连通分量检测

在一个无向图中，连通分量是指图中相互连通的子图。可以通过 DFS 来检测图中的连通分量。以下是基于邻接表的连通分量检测示例代码：

#include <iostream>
#include <vector>
#include <cstring>

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int componentCount = 0;

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    std::cout << "请输入节点数量 n 和边数量 m: ";
    std::cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cout << "请输入边的两个端点 u 和 v: ";
        std::cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
            componentCount++;
        }
    }

    std::cout << "图中的连通分量数量为: " << componentCount << std::endl;
    return 0;
}

在上述代码中：

1. 从图的每个未访问节点出发调用 dfs。
2. 每次从一个未访问节点开始调用 dfs 并完成搜索后，说明找到了一个新的连通分量，componentCount 加 1。

拓扑排序（针对有向无环图 - DAG）

拓扑排序是将有向无环图（DAG）的所有节点排成一个线性序列，使得对于任意一条有向边 (u, v)，节点 u 都排在节点 v 之前。可以使用 DFS 来实现拓扑排序。以下是基于邻接表的拓扑排序示例代码：

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
stack<int> topoOrder;

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
    topoOrder.push(u);
}

int main() {
    int n, m;
    std::cout << "请输入节点数量 n 和边数量 m: ";
    std::cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cout << "请输入边的两个端点 u 和 v: ";
        std::cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    std::cout << "拓扑排序结果: ";
    while (!topoOrder.empty()) {
        std::cout << topoOrder.top() << " ";
        topoOrder.pop();
    }
    std::cout << std::endl;
    return 0;
}

在上述代码中：

1. 从每个未访问节点出发调用 dfs。
2. 在 dfs 函数中，当一个节点及其所有邻接节点都被访问后，将该节点压入栈 topoOrder。
3. 最后，栈中元素的顺序即为拓扑排序的结果。

优化与注意事项

剪枝优化

在一些实际应用中，如迷宫求解或路径搜索问题，可以通过剪枝来减少不必要的搜索。例如，在迷宫求解中，如果当前路径长度已经超过了已知的最短路径长度，则可以停止继续探索该路径。

#include <iostream>
#include <vector>
#include <cstring>

const int ROWS = 5;
const int COLS = 5;
char maze[ROWS][COLS] = {
    {'S', '.', '.', '.', '.'},
    {'.', '#', '.', '#', '.'},
    {'.', '.', '.', '.', '.'},
    {'.', '#', '#', '#', '.'},
    {'.', '.', '.', '#', 'E'}
};
bool visited[ROWS][COLS];
std::vector<std::pair<int, int>> path;
std::vector<std::pair<int, int>> shortestPath;
int minPathLength = ROWS * COLS;

bool isValid(int x, int y) {
    return x >= 0 && x < ROWS && y >= 0 && y < COLS && maze[x][y] != '#' &&!visited[x][y];
}

void dfs(int x, int y, int currentLength) {
    if (x < 0 || x >= ROWS || y < 0 || y >= COLS || maze[x][y] == '#' || visited[x][y] || currentLength >= minPathLength) {
        return;
    }

    visited[x][y] = true;
    path.push_back({x, y});

    if (maze[x][y] == 'E') {
        if (currentLength < minPathLength) {
            minPathLength = currentLength;
            shortestPath = path;
        }
    } else {
        dfs(x + 1, y, currentLength + 1);
        dfs(x - 1, y, currentLength + 1);
        dfs(x, y + 1, currentLength + 1);
        dfs(x, y - 1, currentLength + 1);
    }

    path.pop_back();
}

int main() {
    memset(visited, false, sizeof(visited));
    dfs(0, 0, 0);
    if (!shortestPath.empty()) {
        std::cout << "最短路径: " << std::endl;
        for (const auto& p : shortestPath) {
            std::cout << "(" << p.first << ", " << p.second << ") ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "未找到路径" << std::endl;
    }
    return 0;
}

在上述代码中，minPathLength 记录已知的最短路径长度，当当前路径长度 currentLength 大于等于 minPathLength 时，直接返回，不再继续探索该路径，从而减少了不必要的搜索。

处理环

在有向图中，如果存在环，拓扑排序将无法进行。在实现 DFS 进行拓扑排序时，需要额外的机制来检测环。一种常见的方法是使用两个数组，一个 visited 数组记录节点是否被访问过，另一个 recStack 数组记录当前递归调用栈中是否包含该节点。如果在递归调用过程中发现某个节点已经在 recStack 中，说明存在环。

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
bool recStack[MAXN];
stack<int> topoOrder;
bool hasCycle = false;

void dfs(int u) {
    visited[u] = true;
    recStack[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        } else if (recStack[v]) {
            hasCycle = true;
        }
    }
    if (!hasCycle) {
        topoOrder.push(u);
    }
    recStack[u] = false;
}

int main() {
    int n, m;
    std::cout << "请输入节点数量 n 和边数量 m: ";
    std::cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cout << "请输入边的两个端点 u 和 v: ";
        std::cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));
    memset(recStack, false, sizeof(recStack));

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    if (hasCycle) {
        std::cout << "图中存在环，无法进行拓扑排序" << std::endl;
    } else {
        std::cout << "拓扑排序结果: ";
        while (!topoOrder.empty()) {
            std::cout << topoOrder.top() << " ";
            topoOrder.pop();
        }
        std::cout << std::endl;
    }
    return 0;
}

在上述代码中，recStack 数组用于检测环。如果发现环，则设置 hasCycle 为 true，并停止拓扑排序。

空间复杂度优化

在使用邻接表表示图时，对于稀疏图，邻接表比邻接矩阵节省空间。然而，如果图非常大，邻接表中的 std::vector 可能仍然占用大量内存。可以考虑使用更紧凑的数据结构，如哈希表来存储邻接关系，以进一步优化空间复杂度。

另外，在递归实现 DFS 时，递归调用栈的深度可能会达到图的深度，对于非常深的图，可能会导致栈溢出。非递归实现通过使用 std::stack 可以更好地控制内存使用，但 std::stack 也会占用一定的内存空间。在极端情况下，可以考虑使用手动模拟栈来精确控制内存使用。

例如，手动模拟栈可以使用数组来实现：

#include <iostream>
#include <vector>
#include <cstring>

const int MAXN = 100;
const int MAX_STACK_SIZE = 100;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfsNonRecursiveManualStack(int u) {
    int stack[MAX_STACK_SIZE];
    int top = -1;
    stack[++top] = u;
    visited[u] = true;

    while (top >= 0) {
        int current = stack[top--];
        std::cout << current << " ";

        for (int i = adj[current].size() - 1; i >= 0; --i) {
            int v = adj[current][i];
            if (!visited[v]) {
                stack[++top] = v;
                visited[v] = true;
            }
        }
    }
}

int main() {
    int n, m;
    std::cout << "请输入节点数量 n 和边数量 m: ";
    std::cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cout << "请输入边的两个端点 u 和 v: ";
        std::cin >> u >> v;
        addEdge(u, v);
    }

    memset(visited, false, sizeof(visited));
    std::cout << "深度优先搜索结果: ";
    dfsNonRecursiveManualStack(0); // 从节点 0 开始搜索
    return 0;
}

在上述代码中，使用数组 stack 手动模拟栈，通过 top 变量来控制栈的操作。这种方式可以更精确地控制内存使用，但代码相对复杂一些。

通过上述优化和注意事项，可以使 C++ 实现的深度优先搜索在不同场景下更加高效和稳定。无论是在图论问题、路径搜索还是其他相关领域，DFS 都是一种非常强大且常用的算法，深入理解其实现和优化方法对于解决实际问题具有重要意义。