C++ 深度优先搜索 (DFS) 实现详解

在 C++ 中，可以使用递归函数来实现深度优先搜索（DFS）。下面是一个示例代码，演示了如何使用 DFS 来遍历一个图的所有节点：

#include <iostream>
#include <vector>

using namespace std;

// 定义图的邻接表表示
vector<vector<int>> adjList;

// 标记已访问的节点
vector<bool> visited;

// 深度优先搜索函数
void dfs(int node) {
    // 标记当前节点为已访问
    visited[node] = true;

    // 输出当前节点
    cout << node << ' ';

    // 遍历当前节点的所有邻接节点
    for (int neighbor : adjList[node]) {
        // 如果邻接节点未访问，则继续深度优先搜索
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

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

    // 初始化邻接表和visited数组
    adjList.resize(numNodes);
    visited.resize(numNodes, false);

    cout << "请输入边的连接关系: " << endl;
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        cin >> u >> v;

        // 添加边的连接关系到邻接表
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    // 从节点0开始进行深度优先搜索
    cout << "深度优先搜索结果: ";
    dfs(0);

    return 0;
}

这段代码首先通过输入获取图的节点数和边数，然后使用邻接表来表示图的连接关系。接下来，通过递归调用 dfs 函数来完成深度优先搜索的过程。最后，输出深度优先搜索的结果。