广度优先搜索（BFS）

基本思想

广度优先搜索（BFS）类似于二叉树的层序遍历算法

基本思想是：

首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，...，wi，然后依次访问w1，w2，...，wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直到图中所有顶点都被访问过为止。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。

伪代码

bool visited[MAX_VERTEC_NUM]; // 访问标记数组
void BFSTraverse(Graph G) // 对图G进行广度优先遍历
{
    for(int i=0i<G.vexnum;i++)
        visited[i] = false; // 访问标记数组初始化
    InitQueue(Q); // 初始化辅助队列
    for(int i=0;i<G.vexnum;i++) // 从0号顶点开始遍历
        if(!visited[i]) // 对每个连通分量调用一次BFS
            BFS(G,i) // vi未被访问过，从vi开始BFS
}

void BFS(Graph G,int v) // 从顶点v出发，广度优先遍历图G
{
    visit(v); // 访问初始顶点v
    visited[v] = TRUE; // 对v做已访问标记
    Enqueue(Q,v); // 顶点v入队列
    while(!isEmpty(Q))
    {
        DeQueue(Q,v); // 顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) // 检测v所有邻接点
            if(!visited[w]) // w为v的尚未访问的邻接顶点
            {
                visit(w); // 访问顶点w
                visited[w] = TRUE; // 对w做已访问标记
                EnQueue(Q,w); // 顶点w入队列
            }
    }
}
           

BFS算法求解单源最短路径问题

void BFS_MIN_Distance(Graph G,int u)
{
    // d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;i++)
        d[i] = ∞; // 初始化路径长度
    visited[u] = TRUE;d[u] = 0;
    EnQueue(Q,u);
    while(!IsEmpty(Q)) // BFS算法主过程
    {
        DeQueue(Q,u); // 队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if(!visited[w]) // w为u的尚未访问的邻接顶点
                visited[w] = TRUE; // 设已访问标记
                d[w] = d[u]+1; // 路径长度加1
                EnQueue(Q,w); // 顶点w入队
    }
}