C++实现基于邻接表的深度优先遍历

邻接表是一种表示图的数据结构，深度优先遍历是一种遍历图的算法。下面是C++实现基于邻接表的深度优先遍历的示例代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int maxn = 100;
vector<int> G[maxn];   //邻接表存储图
bool vis[maxn];        //标记每个节点是否被访问过

void dfs(int u)        //从节点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);     //递归访问节点v
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;      //输入节点数n和边数m
    memset(vis, false, sizeof(vis));  //初始化所有节点均未被访问
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;  //输入边的起点和终点
        G[u].push_back(v);  //将边加入邻接表
        G[v].push_back(u);  //无向图需添加反向边
    }
    for (int i = 1; i <= n; i++)  //枚举所有节点
    {
        if (!vis[i])   //如果节点i未被访问
        {
            dfs(i);    //从节点i开始深度优先遍历
        }
    }
    return 0;
}

在这个示例代码中，我们使用邻接表存储图，其中`G[u]`表示节点u的邻接表，即与节点u有直接边相连的所有节点。然后我们使用`dfs`函数进行深度优先遍历，从节点u开始遍历，首先标记节点u已访问，然后输出节点u，接着遍历节点u的所有邻接节点，如果某个邻接节点v未被访问，那么递归访问节点v。最后，我们枚举所有节点，如果某个节点未被访问，那么从该节点开始进行深度优先遍历。