Python中图怎么通过广度优先遍历生成pre数组

在 Python 中，可以使用邻接表或邻接矩阵来表示图。这里以邻接表为例，介绍如何通过广度优先遍历生成 pre 数组。

首先，我们需要定义一个邻接表，表示节点之间的关系。假设邻接表为 `graph`，其中 `graph[i]` 表示节点 i 的所有邻居节点。例如，`graph[0] = [1, 2]` 表示节点 0 的邻居节点为 1 和 2。

接下来，我们可以使用 Python 中的 `deque` 来实现队列。我们还需要定义一个布尔型数组 `visited`，用来记录每个节点是否已经被遍历过，以防止重复遍历。

代码如下：

from collections import deque

def bfs(graph, start):
    n = len(graph)
    visited = [False] * n
    pre = [-1] * n

    queue = deque([start])
    visited[start] = True

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                pre[neighbor] = vertex
                queue.append(neighbor)

    return pre

在上面的代码中，我们首先初始化了 `visited` 和 `pre` 数组，`visited` 数组用于记录每个节点是否已经被遍历过，`pre` 数组用于记录每个节点的前一个节点。然后创建一个队列，将起始节点加入队列中。接着进行 BFS 遍历，对于每个节点，遍历其所有邻居节点，如果该邻居节点尚未被访问，则将其标记为已访问，并将其加入到队列中。同时，在 `pre` 数组中记录该邻居节点的前一个节点。最后返回 `pre` 数组即可。

例如，假设邻接表为 `[[], [2], [1, 3, 4], [2, 4], [2, 3]]`，表示节点 0 没有邻居节点，节点 1 的邻居节点为 2，节点 2 的邻居节点为 1、3、4，以此类推。如果起始节点为 1，那么调用 `bfs(graph, 1)` 会返回 `[-1, -1, 1, 2, 2]`，表示节点 2 的前一个节点是 1，节点 3 的前一个节点是 2，节点 4 的前一个节点是 2，节点 1 没有前一个节点，节点 0 没有被遍历到。