BFS算法伪代码

下面是 BFS 算法的伪代码：

BFS(G, s):
    for each vertex u in G:
        color[u] = WHITE     // 所有点初始状态为白色
        d[u] = INFINITY      // 所有点到起点距离初始为无穷大
        p[u] = NULL          // 所有点的前驱节点初始为 NULL
    color[s] = GRAY          // 起点 s 置灰
    d[s] = 0                 // 起点到自身距离为 0
    p[s] = NULL              // 起点前驱节点为 NULL
    Q.enqueue(s)             // 将起点加入队列 Q
    while Q is not empty:    // 只要队列不为空
        u = Q.dequeue()      // 取出队首元素 u
        for each v in G.adj[u]:  // 遍历 u 的邻接点 v
            if color[v] == WHITE:  // 若 v 为白色，说明还未被访问
                color[v] = GRAY   // 将 v 置灰
                d[v] = d[u] + 1  // 更新到起点的距离
                p[v] = u         // 标记 v 的前驱节点为 u
                Q.enqueue(v)     // 将 v 加入队列 Q
        color[u] = BLACK     // 将 u 置黑

其中，`G` 是一张图，`s` 是起点，`color[u]` 表示顶点 `u` 的颜色，`d[u]` 表示顶点 `u` 到起点的距离，`p[u]` 表示顶点 `u` 的前驱节点。`Q.enqueue(u)` 表示将顶点 `u` 加入队列 `Q` 中，`Q.dequeue()` 表示从队列 `Q` 中取出队首元素。