廣度優先搜尋（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入隊
    }
}