图的广度优先遍历生成pre数组

广度优先遍历（BFS）可以用来生成一张无向图的pre数组，pre数组记录了每个顶点在BFS遍历时的前一个顶点。

以下是一种基于队列的BFS遍历算法，可以在遍历过程中生成pre数组：

// 无向图的邻接表表示
vector<int> adj[N];

// 生成pre数组的BFS遍历函数
void bfs(int start, int pre[]) {
    // 初始化pre数组，将所有顶点的前一个顶点置为-1
    memset(pre, -1, sizeof(pre));

    // 队列q存储待遍历的顶点
    queue<int> q;
    q.push(start);
    pre[start] = start;

    // BFS遍历，直到队列为空
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (pre[v] == -1) {
                pre[v] = u;
                q.push(v);
            }
        }
    }
}

在上面的代码中，我们使用了一个队列q来存储待遍历的顶点。初始时，将起始顶点start加入队列，并将其pre值设为start。然后，每次从队列中取出一个顶点u，并遍历其所有邻接点v。如果v的pre值尚未被赋值（即为-1），则将其pre值设为u，并将v加入队列。这样，当队列为空时，所有顶点的pre值都已经被计算出来了。

使用该函数可以生成pre数组，例如：

int pre[N];
bfs(1, pre);

这将生成以1为起点的BFS遍历，并将其结果存储在pre数组中。