采用邻接表表示图的深度优先搜索遍历c++代码实现

在C++中，使用邻接表表示图的深度优先搜索（DFS）遍历通常涉及创建一个队列用于存储待访问的节点，以及一个辅助函数来标记节点的状态。这里是一个简单的代码实现示例：

#include <iostream>
#include <vector>
#include <queue>

// 定义图的节点结构
struct Node {
    int value;
    std::vector<int> neighbors; // 邻居列表
};

void dfs(Node* node, bool visited[], std::queue<Node*>& queue) {
    if (visited[node->value]) return; // 如果已经访问过，则跳过
    visited[node->value] = true; // 标记当前节点已访问

    std::cout << "Visiting node: " << node->value << "\n";
    
    // 将未访问的邻居加入队列
    for (int neighbor : node->neighbors) {
        if (!visited[neighbor]) {
            queue.push(*node); // 使用引用传递避免复制
            dfs(node, visited, queue);
        }
    }
}

int main() {
    // 假设我们有如下的邻接表表示的图
    Node graph[] = { {1, {2}},   // 节点1 -> 节点2
                    {2, {1, 3}}, // 节点2 -> 节点1 和 节点3
                    {3, {2, 4}}, // 节点3 -> 节点2 和 节点4
                    {4, {3}}     // 节点4 -> 节点3
                  };
    const int numNodes = sizeof(graph) / sizeof(graph[0]);

    bool visited[numNodes] = {false}; // 初始化所有节点未访问
    std::queue<Node*> q;

    // 从任意节点开始（例如，节点1）
    q.push(graph[0]);
    dfs(graph[0], visited, q);

    return 0;
}

当你运行这个程序时，它会按照深度优先顺序打印出每个节点的值。