输出深度优先生成树

深度优先生成树（Depth First Search Tree）可以通过深度优先搜索算法来生成。在搜索过程中，我们不断扩展当前节点的子节点，并将它们加入到搜索队列中，然后继续搜索队列中的下一个节点，直到队列为空为止。

在生成深度优先生成树时，我们可以在搜索过程中记录每个节点的父节点，这样就可以通过父节点指针来构建出生成树。下面是一个伪代码实现：

dfs_tree(node):
    visited[node] = True
    for child in node.children:
        if not visited[child]:
            parent[child] = node
            dfs_tree(child)

其中，visited数组用于记录节点是否已经被访问过，parent数组用于记录每个节点的父节点。我们从根节点开始调用dfs_tree函数，递归地遍历整个图，并记录每个节点的父节点，最终得到一棵深度优先生成树。

生成树的构建可以在搜索过程中进行，也可以在搜索结束后进行。如果在搜索过程中进行构建，则需要注意避免重复添加边的情况。如果在搜索结束后进行构建，则需要遍历整个图来查找每个节点的父节点，这种方法效率较低。

相关问题

用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` 数组来存储。在遍历时，每当访问到一个未访问过的节点时，就将该节点的父节点设置为当前节点，并递归访问该节点的邻居节点。

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

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

下面是用C++实现输出深度优先生成树和广度优先生成树的代码：

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

const int N = 100; // 图的最大节点数

int n, m; // n表示节点数，m表示边数
vector<int> g[N]; // 存储图
bool visited[N]; // 标记节点是否被访问过

// 深度优先生成树
void dfs(int u, int parent) {
    cout << u << " "; // 输出当前节点
    for (int v : g[u]) {
        if (v != parent) { // 避免重复访问父节点
            dfs(v, u); // 递归访问子节点
        }
    }
}

// 广度优先生成树
void bfs(int root) {
    queue<int> q;
    q.push(root); // 将根节点入队
    visited[root] = true; // 标记根节点已被访问过
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " "; // 输出当前节点
        for (int v : g[u]) {
            if (!visited[v]) { // 如果节点未被访问过
                visited[v] = true; // 标记节点已被访问过
                q.push(v); // 将节点入队
            }
        }
    }
}

int main() {
    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);
    }

    // 输出深度优先生成树
    cout << "Depth First Search Tree: ";
    dfs(1, 0); // 从节点1开始遍历

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

    // 输出广度优先生成树
    cout << "\nBreadth First Search Tree: ";
    bfs(1); // 从节点1开始遍历

    return 0;
}

输入格式为：

节点数 边数
u1 v1
u2 v2
...

例如，以下是一个包含6个节点和5条边的图：

6 5
1 2
1 3
2 4
2 5
3 6

输出为：

Depth First Search Tree: 1 2 4 5 3 6 
Breadth First Search Tree: 1 2 3 4 5 6 

其中，深度优先生成树的根节点为1，广度优先生成树的根节点也为1。