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

下面是用Python实现的图的广度优先遍历生成pre数组的代码：

from collections import deque

# 无向图的邻接表表示
adj = [[] for _ in range(N)]

# 生成pre数组的BFS遍历函数
def bfs(start):
    # 初始化pre数组，将所有顶点的前一个顶点置为-1
    pre = [-1] * N
    pre[start] = start

    # 队列q存储待遍历的顶点
    q = deque([start])

    # BFS遍历，直到队列为空
    while q:
        u = q.popleft()
        for v in adj[u]:
            if pre[v] == -1:
                pre[v] = u
                q.append(v)

    return pre

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

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

pre = bfs(1)

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