基于邻接表的深度优先遍历

邻接表是一种存储图结构的数据结构，其中每个节点的所有邻居节点都被存储为一个链表。深度优先遍历（Depth First Search, DFS）是一种图遍历算法，它从图中某个顶点开始遍历，沿着一条路走到底，直到不能再走为止，然后回退到上一个节点，再沿着另一条路走到底，直到所有节点都被访问过为止。

基于邻接表的深度优先遍历实现如下：

1. 创建一个栈S和一个布尔数组visited。

2. 将起始节点入栈S并标记为visited。

3. 取出栈顶节点v，访问它并将其未被访问的邻居节点入栈S并标记为visited。

4. 重复步骤3直到栈S为空。

5. 如果还有未被访问的节点，则从其中任选一个节点作为起始节点，重复以上步骤。

需要注意的是，如果图是非连通的，则需要从每个未被访问的节点开始重复以上步骤，直到所有节点都被访问过为止。

相关问题

基于邻接表的深度优先遍历代码

以下是基于邻接表的深度优先遍历代码（C++实现）：

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

const int MAXN = 100; // 最大顶点个数

vector<int> adj[MAXN]; // 邻接表存图
bool vis[MAXN]; // 标记数组，标记每个顶点是否已访问

void dfs(int u) { // 深度优先遍历函数
    vis[u] = true; // 标记当前顶点已访问
    cout << u << " "; // 输出当前顶点
    for (int i = 0; i < adj[u].size(); i++) { // 遍历所有邻接点
        int v = adj[u][i];
        if (!vis[v]) { // 如果未访问，则递归访问
            dfs(v);
        }
    }
}

int main() {
    int n, m; // n表示顶点个数，m表示边数
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // 存储边
        adj[v].push_back(u); // 无向图需要存储反向边
    }

    for (int i = 1; i <= n; i++) { // 按顺序遍历每个顶点
        if (!vis[i]) { // 如果未访问，则以该顶点为起点开始遍历
            dfs(i);
        }
    }

    return 0;
}

其中，`adj`为邻接表，`vis`为标记数组，`dfs`为深度优先遍历函数。主函数中按顺序遍历每个顶点，如果未访问，则以该顶点为起点开始遍历。在深度优先遍历函数中，先标记当前顶点已访问，然后输出当前顶点，最后遍历所有邻接点，如果未访问，则递归访问。

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。最后，我们枚举所有节点，如果某个节点未被访问，那么从该节点开始进行深度优先遍历。