c++实现无向图的深度优先生成树

实现无向图的深度优先生成树主要分为以下几个步骤：

1. 定义图的结构体，包含顶点数和边的数组（每个边包含起点和终点的编号）。

struct Graph {
    int V; // 顶点数
    vector<pair<int,int>> edges; // 边的数组
};

2. 定义一个DFS函数，用于遍历图并生成深度优先生成树。该函数需要传入当前节点编号、父节点编号、当前生成树的深度、以及一个visited数组用于记录已经遍历过的节点。

void DFS(int v, int parent, int depth, vector<bool>& visited, vector<vector<int>>& adj_list, vector<int>& parent_list, vector<int>& depth_list) {
    visited[v] = true;
    parent_list[v] = parent;
    depth_list[v] = depth;
    for (auto u : adj_list[v]) {
        if (!visited[u]) {
            DFS(u, v, depth + 1, visited, adj_list, parent_list, depth_list);
        }
    }
}

3. 定义一个函数来生成深度优先生成树。该函数需要传入一个图结构体，以及一个起点编号。首先，需要初始化visited、parent_list和depth_list数组。然后，从起点开始调用DFS函数进行遍历，最终返回生成树的parent_list和depth_list数组。

pair<vector<int>, vector<int>> DFS_tree(Graph& g, int start) {
    vector<bool> visited(g.V, false);
    vector<vector<int>> adj_list(g.V);
    vector<int> parent_list(g.V, -1);
    vector<int> depth_list(g.V, 0);

    // 构造邻接表
    for (auto edge : g.edges) {
        int u = edge.first, v = edge.second;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    // 生成深度优先生成树
    DFS(start, -1, 0, visited, adj_list, parent_list, depth_list);

    return make_pair(parent_list, depth_list);
}

以上就是实现无向图的深度优先生成树的步骤。