用c++代码实现把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树

下面是将图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树的 C++ 代码实现：

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

using namespace std;

// 定义图的邻接表表示法
class Graph {
public:
    int V; // 顶点数量
    vector<int>* adj; // 邻接表数组

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

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

    // 深度优先遍历，输出深度优先生成树
    void DFS(int v, bool visited[], int parent[]) {
        visited[v] = true;
        for (int i = 0; i < adj[v].size(); i++) {
            int w = adj[v][i];
            if (!visited[w]) {
                parent[w] = v;
                DFS(w, visited, parent);
            }
        }
    }

    // 广度优先遍历，输出广度优先生成树
    void BFS(int s, int parent[]) {
        bool* visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }
        queue<int> q;
        visited[s] = true;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int i = 0; i < adj[v].size(); i++) {
                int w = adj[v][i];
                if (!visited[w]) {
                    visited[w] = true;
                    parent[w] = v;
                    q.push(w);
                }
            }
        }
        delete[] visited;
    }

    // 输出生成树
    void printTree(int parent[]) {
        for (int i = 0; i < V; i++) {
            if (parent[i] != -1) {
                cout << parent[i] << " -> " << i << endl;
            }
        }
    }
};

int main() {
    Graph g(6); // 创建一个有 6 个节点的图

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

    // 深度优先遍历，输出深度优先生成树
    bool* visited = new bool[g.V];
    int* parent1 = new int[g.V];
    for (int i = 0; i < g.V; i++) {
        visited[i] = false;
        parent1[i] = -1;
    }
    for (int i = 0; i < g.V; i++) {
        if (!visited[i]) {
            g.DFS(i, visited, parent1);
        }
    }
    cout << "深度优先生成树：" << endl;
    g.printTree(parent1);
    delete[] visited;
    delete[] parent1;

    // 广度优先遍历，输出广度优先生成树
    int* parent2 = new int[g.V];
    for (int i = 0; i < g.V; i++) {
        parent2[i] = -1;
    }
    g.BFS(0, parent2);
    cout << "广度优先生成树：" << endl;
    g.printTree(parent2);
    delete[] parent2;

    return 0;
}

代码中先定义了一个 `Graph` 类，用邻接表表示法来存储图，并实现了深度优先遍历、广度优先遍历、输出生成树的方法。

在主函数中，先创建了一个有 6 个节点的图，并添加了边。然后调用深度优先遍历方法和广度优先遍历方法来输出深度优先生成树和广度优先生成树。

需要注意的是，在深度优先遍历中，我们需要记录每个节点的父节点，所以定义了一个 `parent` 数组来存储。在遍历时，每当访问到一个未访问过的节点时，就将该节点的父节点设置为当前节点，并递归访问该节点的邻居节点。

在广度优先遍历中，我们使用一个队列来存储待访问的节点。首先将起点加入队列，并标记为已访问。然后不断从队列中取出一个节点，并遍历该节点的所有邻居节点。对于每个未访问过的邻居节点，将其加入队列，并标记为已访问，同时记录其父节点。最后输出生成树即可。