c++写个深度优先搜索

深度优先搜索 (Depth-First Search, DFS) 是一种用于遍历或搜索树或图的算法，其基本思想是从根节点或起始节点开始，沿着一条路径一直走到底，然后返回回溯到上一个节点，再沿着另外一条路径走到底，直到所有节点都被访问过为止。

下面是一个简单的 C++ 实现：

#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

vector<int> g[N]; // 存储图的邻接表
bool vis[N]; // 标记每个节点是否被访问过

void dfs(int u)
{
    vis[u] = true; // 标记节点 u 已经被访问过
    cout << u << " "; // 访问节点 u

    for (int i = 0; i < g[u].size(); i++) // 遍历节点 u 的相邻节点
    {
        int v = g[u][i];
        if (!vis[v]) // 如果节点 v 还没被访问过，则继续遍历它的相邻节点
            dfs(v);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u); // 无向图需要存储反向边
    }

    dfs(1); // 从节点 1 开始遍历

    return 0;
}

该程序可以输入一个无向图，然后从节点 1 开始进行深度优先遍历，最终输出遍历的结果。其中，g 数组存储了图的邻接表，vis 数组用于标记每个节点是否被访问过。dfs 函数实现了深度优先遍历的核心逻辑，它从节点 u 开始遍历，并遍历它的所有相邻节点，如果某个相邻节点 v 还没被访问过，则继续从 v 开始遍历。