数据结构图广度优先的生成树

生成树是一种无向图的树形表示方式，它包含了原图的所有节点，但是只有足够连接这些节点的边。广度优先搜索可以生成无向图的生成树。

生成树算法的基本思想是从一个起点开始，依次添加节点和边直到覆盖所有的节点。具体步骤如下：

1. 选定一个起点作为根节点，并将其标记为已访问。
2. 将根节点入队。
3. 重复以下步骤，直到队列为空：
- 从队列中取出一个节点。
- 枚举该节点的所有邻居节点，如果邻居节点未被访问过，则将其标记为已访问，并将该节点和邻居节点之间的边加入生成树中。
- 将邻居节点入队。

在生成树过程中，我们需要用一个数组记录每个节点的父节点，以便后续构造生成树。具体实现可以使用队列来辅助实现广度优先搜索，也可以使用递归实现深度优先搜索。

下面是一个示例代码（使用邻接表表示图）：

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

using namespace std;

const int MAXN = 100;  // 最大节点数

vector<int> adj[MAXN];   // 邻接表表示图
int father[MAXN];        // 记录节点的父节点
bool visited[MAXN];      // 记录节点是否已访问

void bfs(int root) {
    queue<int> q;
    q.push(root);
    visited[root] = true;
    father[root] = -1;   // 根节点没有父节点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                father[v] = u;  // 记录父节点
                q.push(v);
            }
        }
    }
}

int main() {
    int n, m;   // n 个节点，m 条边
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);   // 从节点 1 开始生成树
    for (int i = 1; i <= n; i++) {
        cout << "father of " << i << " is " << father[i] << endl;
    }
    return 0;
}

注：以上代码仅供参考，实际应用中需要根据具体需求进行修改。