数据结构邻接表的深度优先遍历和广度优先遍历编程（c/c++）

在使用数据结构邻接表（如图的邻接矩阵的稀疏版本，通常用于表示无向图或有向图）进行图形算法时，深度优先搜索（DFS）和广度优先搜索（BFS）是常用的遍历策略。以下是这两种遍历方法的简单C++实现：

**深度优先搜索（DFS）：**

#include <iostream>
using namespace std;

// 图节点结构体
struct Node {
    int value;
    vector<Node*> neighbors; // 邻居列表
};

void dfs(Node* node) {
    cout << node->value << " "; // 访问当前节点
    for (Node* neighbor : node->neighbors) {
        dfs(neighbor); // 对未访问过的邻居递归调用DFS
    }
}

int main() {
    // 初始化图节点
    Node a{1}, b{2}, c{3}, d{4};
    a.neighbors.push_back(&b);
    a.neighbors.push_back(&d);
    b.neighbors.push_back(&c);
    c.neighbors.push_back(&a);

    dfs(&a); // 从节点a开始遍历
    return 0;
}

**广度优先搜索（BFS）：**

#include <queue>
using namespace std;

void bfs(Node* start) {
    queue<Node*> q;
    q.push(start);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        cout << node->value << " "; // 访问当前节点
        for (Node* neighbor : node->neighbors)
            q.push(neighbor);
    }
}

int main() {
    // 同样的初始化过程...
    bfs(&a); // 从节点a开始遍历
    return 0;
}

在上述代码中，`dfs`和`bfs`函数分别实现了深度优先和广度优先的遍历。每个节点都维护了一个邻居列表，通过这个列表在遍历时进行递归或队列操作。