c++编程由邻接表生成深度和广度优先序列

以下是使用邻接表生成深度和广度优先序列的C++代码示例：

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

using namespace std;

// 用于表示图中的节点
struct Node {
    int val;
    vector<Node*> neighbors;

    Node(int x) : val(x) {}
};

// 深度优先遍历
void dfs(Node* node, vector<bool>& visited, vector<int>& res) {
    if (!node || visited[node->val]) {
        return;
    }
    visited[node->val] = true;
    res.push_back(node->val);
    for (Node* neighbor : node->neighbors) {
        dfs(neighbor, visited, res);
    }
}

// 广度优先遍历
void bfs(Node* node, vector<bool>& visited, vector<int>& res) {
    queue<Node*> q;
    q.push(node);
    visited[node->val] = true;

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        res.push_back(curr->val);
        for (Node* neighbor : curr->neighbors) {
            if (!visited[neighbor->val]) {
                visited[neighbor->val] = true;
                q.push(neighbor);
            }
        }
    }
}

// 生成深度优先序列
vector<int> generateDFS(Node* node) {
    vector<int> res;
    if (!node) {
        return res;
    }
    vector<bool> visited(1000, false); // 用于标记节点是否已经访问过
    dfs(node, visited, res);
    return res;
}

// 生成广度优先序列
vector<int> generateBFS(Node* node) {
    vector<int> res;
    if (!node) {
        return res;
    }
    vector<bool> visited(1000, false); // 用于标记节点是否已经访问过
    bfs(node, visited, res);
    return res;
}

int main() {
    // 创建一个有向图
    Node* node0 = new Node(0);
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    node0->neighbors = {node1, node2};
    node1->neighbors = {node3, node4};
    node2->neighbors = {node4, node5};

    // 生成深度优先序列
    vector<int> dfs_res = generateDFS(node0);
    cout << "DFS: ";
    for (int i : dfs_res) {
        cout << i << " ";
    }
    cout << endl;

    // 生成广度优先序列
    vector<int> bfs_res = generateBFS(node0);
    cout << "BFS: ";
    for (int i : bfs_res) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

以上代码中，我们先定义了一个 `Node` 结构体，用于表示图中的节点。`Node` 结构体包含一个 `val` 属性和一个 `neighbors` 向量，其中 `val` 表示节点的值，`neighbors` 向量表示节点的邻居。

然后我们定义了两个函数 `dfs` 和 `bfs`，分别用于进行深度优先遍历和广度优先遍历。这两个函数都使用了一个 `visited` 向量，用于标记节点是否已经访问过。当遍历到一个节点时，首先将该节点标记为已访问，并将其值加入结果向量中，然后递归或迭代地遍历该节点的所有邻居。这两个函数的主要区别在于遍历顺序的不同。

最后，我们定义了两个函数 `generateDFS` 和 `generateBFS`，分别用于生成深度优先序列和广度优先序列。这两个函数都调用了 `dfs` 和 `bfs` 函数，并返回遍历结果。

在 `main` 函数中，我们创建了一个有向图，并分别生成了深度优先序列和广度优先序列，并打印输出结果。