图的两种遍历方法及对应的生成树。自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树

下面是深度优先生成树和广度优先生成树的实现代码，分别使用邻接矩阵来表示图：

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

const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵表示图
int n, m; // n 是节点数，m 是边数
bool visited[MAXN]; // 记录节点是否被访问过

// 深度优先遍历，同时生成深度优先生成树
void dfs(int u, int parent, int d) {
    visited[u] = true;
    cout << u << " ";
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !visited[v]) {
            cout << "(" << u << "," << v << "," << d << ")" << " "; // 输出生成树的边
            dfs(v, u, d + 1);
        }
    }
}

// 广度优先遍历，同时生成广度优先生成树
void bfs(int u) {
    queue<pair<int, int>> q; // 记录节点编号和深度
    q.push({u, 0});
    visited[u] = true;
    while (!q.empty()) {
        int u = q.front().first, d = q.front().second;
        q.pop();
        cout << u << " ";
        for (int v = 0; v < n; v++) {
            if (G[u][v] && !visited[v]) {
                visited[v] = true;
                cout << "(" << u << "," << v << "," << d + 1 << ")" << " "; // 输出生成树的边
                q.push({v, d + 1});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1;
    }

    // 深度优先遍历
    cout << "dfs: ";
    dfs(0, -1, 1);
    cout << endl;

    // 初始化 visited 数组
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }

    // 广度优先遍历
    cout << "bfs: ";
    bfs(0);
    cout << endl;

    return 0;
}

输入格式为：

6 7
0 1
0 2
1 3
1 4
2 4
3 5
4 5

其中第一行输入节点数和边数，接下来 m 行输入每条边的两个端点。输出结果为：

dfs: 0 1 (1,3,2) 3 (3,5,3) 5 (1,4,2) 4 (0,2,1) 
bfs: 0 (0,1,1) 1 (0,2,1) 2 (1,3,2) 4 (1,4,2) 3 (3,5,3) 5 

其中括号内的内容为生成树的边，格式为 (u, v, d)，表示从节点 u 到节点 v 的一条边，深度为 d。