C++ 深度优先搜索 (DFS) 算法详解及代码实现

深度优先搜索 (Depth-First Search, DFS) 是一种图遍历算法，它从一个节点开始，沿着一条路径尽可能地向下遍历，直到无法继续遍历为止，然后回溯到上一个节点，再选择另一条路径继续遍历。

以下是一个使用 C++ 实现的深度优先搜索算法的示例代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[1000]; // 邻接表
bool visited[1000]; // 记录是否访问过

void dfs(int u) {
    visited[u] = true; // 标记为已访问
    cout << u << ' '; // 输出当前节点
    for (int i = 0; i < adj[u].size(); i++) { // 遍历当前节点的邻居节点
        int v = adj[u][i];
        if (!visited[v]) { // 如果邻居节点未被访问过
            dfs(v); // 继续递归深度优先搜索
        }    
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入边的起点和终点
        adj[u].push_back(v); // 将边加入邻接表
        adj[v].push_back(u); // 无向图需要将边反向加入邻接表
    }
    dfs(1); // 从节点1开始深度优先搜索
    return 0;
}

该代码使用了邻接表来存储图数据。visited 数组用于标记节点是否已被访问过。dfs 函数接受一个节点 u 作为参数，并执行以下操作：

将节点 u 标记为已访问。
输出节点 u。
遍历节点 u 的所有邻居节点 v。
如果邻居节点 v 未被访问过，则递归调用 dfs(v)。

在 main 函数中，首先从输入中读取节点数和边数，然后构建邻接表。最后，从节点 1 开始执行深度优先搜索。

该算法的优势在于其简洁性和易于实现。它可以用于解决许多图论问题，例如：

寻找连通分量
拓扑排序
最短路径问题 (例如，使用 A* 搜索算法)

注意：

以上代码示例假设图是无向图，如果图是有向图，则不需要将边反向加入邻接表。
深度优先搜索的效率取决于图的结构。在最坏情况下，其时间复杂度为 O(V + E)，其中 V 是节点数，E 是边数。