图的深度优先遍历邻接表c++

图的深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索树形结构和图的数据结构的算法。在C++中，当我们用邻接表表示图时，DFS通常会通过递归或栈来实现，因为邻接表提供了方便地访问每个顶点的邻居。

以下是使用邻接表和栈实现深度优先遍历的基本步骤：

1. 定义一个函数dfs，接受当前节点作为参数。
2. 将起始节点（通常是顶点的编号或引用）压入栈中。
3. 当栈非空时，弹出栈顶节点，并检查其是否已访问过：
- 如果未访问，则标记为已访问，并将其所有未访问的邻居（从邻接列表中获取）压入栈。
- 对于每个邻居，递归地调用dfs函数。
4. 遍历完成后，如果仍有节点在栈中，说明有环存在，因为DFS不会回溯已经访问过的节点。

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

void dfs(int node, vector<int> adj[], bool visited[]) {
    // 标记当前节点为已访问
    visited[node] = true;
    cout << node << " "; // 输出节点

    // 将未访问的邻居压入栈
    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfs(neighbor, adj, visited);
    }
}

int main() {
    int num_nodes;
    cin >> num_nodes;
    vector<int> adj[num_nodes]; // 创建邻接表
    // ... (读取边并填充邻接表)

    bool visited[num_nodes]; // 初始化所有节点为未访问
    for (int i = 0; i < num_nodes; ++i) {
        visited[i] = false;
    }

    dfs(0, adj, visited); // 从起始节点0开始遍历
    return 0;
}