c++设计算法求无向图的深度优先生成树

以下是C++代码实现，假设无向图为G，顶点数为n，边数为m，使用邻接表存储：

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

const int N = 100010;

vector<int> G[N];    // 图的邻接表存储
bool visited[N];     // 标记顶点是否被访问过
int pre[N];          // 记录DFS生成树中每个顶点的前驱节点

void dfs(int u) {
    visited[u] = true;   // 标记u为已访问
    for (auto v : G[u]) {
        if (!visited[v]) {   // 如果v未被访问过，则(u, v)是树边
            pre[v] = u;      // 记录v的前驱节点为u
            dfs(v);          // 继续以v为起点进行深度优先遍历
        }
    }
}

void dfs_tree(int n) {
    for (int i = 1; i <= n; i++) {
        visited[i] = false;   // 初始化所有顶点为未访问过
        pre[i] = -1;           // 初始化所有顶点的前驱节点为-1
    }
    for (int u = 1; u <= n; u++) {
        if (!visited[u]) {     // 如果u未被访问过，则以u为起点进行深度优先遍历
            dfs(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读入无向图
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs_tree(n);   // 计算无向图的深度优先生成树

    // 输出DFS生成树
    cout << "DFS Tree:" << endl;
    for (int i = 1; i <= n; i++) {
        if (pre[i] != -1) {
            cout << pre[i] << " " << i << endl;
        }
    }

    return 0;
}

算法思路：从某个未被访问过的顶点 $u$ 开始进行深度优先遍历，每次遍历到一条未被访问过的边 $(u,v)$ 时，将 $(u,v)$ 加入到生成树中，并标记 $v$ 为已访问。在深度优先遍历的过程中，记录每个顶点的前驱节点，最终输出所有生成树边即可。