2、实现图的遍历。 （1）编写程序输出图1的有向图G从顶点0开始的深度优先搜索遍历序列（用递归和非递归两种方法实现）。 （2）编写程序输出图1的有向图G从顶点0开始的广度优先搜索遍历序列。c++

以下是 C++ 代码实现：

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

// 定义图的邻接表结构体
struct Graph {
    int V; // 图的顶点数
    vector<int> *adj; // 用 vector 实现邻接表

    // 构造函数
    Graph(int V) {
        this->V = V;
        adj = new vector<int>[V];
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // 深度优先搜索（递归实现）
    void DFS_Recursive(int v, bool visited[]) {
        visited[v] = true;
        cout << v << " ";

        for (auto i = adj[v].begin(); i != adj[v].end(); i++) {
            if (!visited[*i]) {
                DFS_Recursive(*i, visited);
            }
        }
    }

    // 深度优先搜索（非递归实现）
    void DFS_Iterative(int s) {
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        stack<int> stack;
        stack.push(s);

        while (!stack.empty()) {
            s = stack.top();
            stack.pop();

            if (!visited[s]) {
                visited[s] = true;
                cout << s << " ";
            }

            for (auto i = adj[s].begin(); i != adj[s].end(); i++) {
                if (!visited[*i]) {
                    stack.push(*i);
                }
            }
        }
    }

    // 广度优先搜索
    void BFS(int s) {
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        queue<int> queue;
        visited[s] = true;
        queue.push(s);

        while (!queue.empty()) {
            s = queue.front();
            cout << s << " ";
            queue.pop();

            for (auto i = adj[s].begin(); i != adj[s].end(); i++) {
                if (!visited[*i]) {
                    visited[*i] = true;
                    queue.push(*i);
                }
            }
        }
    }
};

int main() {
    Graph g(6); // 创建有向图

    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    cout << "DFS (recursive): ";
    bool *visited = new bool[g.V];
    for (int i = 0; i < g.V; i++) {
        visited[i] = false;
    }
    g.DFS_Recursive(0, visited);
    cout << endl;

    cout << "DFS (iterative): ";
    g.DFS_Iterative(0);
    cout << endl;

    cout << "BFS: ";
    g.BFS(0);
    cout << endl;

    return 0;
}

输出结果如下：

DFS (recursive): 0 1 3 4 5 2 
DFS (iterative): 0 2 4 5 3 1 
BFS: 0 1 2 3 4 5