图的广度优先搜索

广度优先搜索（Breadth-First Search, BFS）简单来说就是利用队列结构，将邻接点依次加入队列中，将一个顶点的邻接点都遍历完成后再遍历邻接点的邻接点。

基本思想

广度优先搜索类似于树的层次遍历。

首先访问图中某一个指定的出发点 vᵢ。
然后依次访问 vᵢ 的所有邻接点 vᵢ₁, vᵢ₂, …, vᵢₜ。
再依次以 vᵢ₁, vᵢ₂, …, vᵢₜ 为顶点，访问各顶点未被访问的邻接点，依此类推，直到图中所有顶点均被访问为止。
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

算法实现

邻接矩阵形式

void BFS(int i) {  // 图用邻接矩阵表示
    int i, j;
    SETNULL(Q);
    ENQUEUE(Q, i);                     // 当前访问结点入队
    while (!EMPTY(Q)) {
        i = DEQUEUE(Q);                // 让当前结点出队
        for (j = 0; j < n; j++) {      // 访问这一行所有结点
            if ((g.arcs[i][j] == 1) && (!visited[j])) {
                // 如果当前结点有边且下一结点未被访问
                visited[j] = TRUE;
                ENQUEUE(Q, j);
            }
        }
    }
}

邻接表形式

void BFSL(int i) {  // 图用邻接表表示
    int i;
    edgenode *p;
    SETNULL(Q);
    ENQUEUE(Q, i);
    visited[i] = TRUE;
    while (!EMPTY(Q)) {
        i = DEQUEUE(Q);
        p = g[i].link;
        while (p != NULL) {            // 访问 p 的整个链
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = TRUE;
                ENQUEUE(Q, p->adjvex);
            }
            p = p->next;
        }
    }
}