1. 簡介

BFS（Breadth First Search，廣度優(yōu)先搜索，又名寬度優(yōu)先搜索），與深度優(yōu)先算法在一個結(jié)點(diǎn)“死磕到底“的思維不同，廣度優(yōu)先算法關(guān)注的重點(diǎn)在于每一層的結(jié)點(diǎn)進(jìn)行的下一層的訪問。

2. BFS算法介紹

BFS算法和核心思路就是：從某個點(diǎn)一直把其鄰接點(diǎn)走完，然后任選一個鄰接點(diǎn)把與之鄰接的未被遍歷的點(diǎn)走完，如此反復(fù)走完所有結(jié)點(diǎn)。類似于樹的層序遍歷。

BFS的核心就是要把當(dāng)前在哪作為一個狀態(tài)存儲，并將這個狀態(tài)交給隊列進(jìn)行入隊操作，故而，

算法步驟（用隊列實(shí)現(xiàn)）

a) 訪問指定起始點(diǎn)。

b) 訪問當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的頂點(diǎn)，并將之放入隊列中。

c) 刪除隊列的隊首節(jié)點(diǎn)。訪問當(dāng)前隊列的隊首，前面的步驟。直到隊列為空。

d) 若若途中還有頂點(diǎn)未被訪問，則再選一個點(diǎn)作為起始頂點(diǎn)。重復(fù)前面的步驟。（針對非連通圖）。

3. 案例圖示

還是這一份例圖，我們直接以案例進(jìn)行講解，就本圖而言，其訪問順序可以是（不唯一）：1-2-3-4-5

首先從1開始，1結(jié)點(diǎn)處可以訪問2，3兩個結(jié)點(diǎn)，我們訪問并以此把兩個結(jié)點(diǎn)的訪問順序放入隊列，然后按照入隊順序（如2，3），之后我們出隊狀態(tài)2，依次訪問2結(jié)點(diǎn)的下兩個結(jié)點(diǎn)（4，5結(jié)點(diǎn)），并入隊4，5結(jié)點(diǎn)，再之后我們出隊3結(jié)點(diǎn)，并依次訪問后續(xù)，此時發(fā)現(xiàn)所有的結(jié)點(diǎn)已經(jīng)被訪問完畢了，可以結(jié)束搜索，最后我們得到次序：1-2-3-4-5

4. 相關(guān)代碼

BFS的模板代碼如下：

/**
 * 返回合適的檢索數(shù)據(jù)
 */
int BFS(Node root, Node target) 
{
    Queue<Node> queue;  //創(chuàng)建隊列
    int step = 0;       // 當(dāng)前隊列的步驟點(diǎn)
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) 
    {
        step = step + 1;
        //步數(shù)逐漸增加
        int size = queue.size();
        for (int i = 0; i < size; ++i) 
        {
            Node cur = the first node in queue;
            if cur is target
                return step - 1;
            for (Node next : the neighbors of cur) 
            {//這里常用一個二維方向數(shù)組實(shí)現(xiàn)
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          //出錯返回值
}

同樣提供一份BFS的圖論算法節(jié)選，代碼最核心還是取記憶BFS的模板并根據(jù)實(shí)際情況的靈活使用，故以下代碼僅提供參考

void BFSL(int pos,pGraph G,int visited[30])//從pos點(diǎn)開始進(jìn)行廣度優(yōu)先遍歷無向圖
{
    int queue[G->Vnum];//隊列輔助BFS遍歷
    int head=0,tail=0;//隊頭、隊尾指針
    Arcnode* p;
    queue[tail]=pos;
    visited[pos]=1;//標(biāo)記遍歷過
    tail++;
    while(head!=tail)
    {
        pos=queue[head];//出隊操作
        head++;
        printf("%d ",pos);
        p=G->vertice[pos].firstarc;
        while(p!=NULL)
        {
            if(visited[p->adjvex]==0)//判斷是否遍歷過
            {
                queue[tail]=p->adjvex;//入隊操作
                visited[p->adjvex]=1;//標(biāo)記遍歷過
                tail++;
            }
            p=p->next;
        }
    }
}

5.  應(yīng)用

BFS算法的實(shí)際應(yīng)用場景，最典型的有地圖搜索，迷宮尋路等，需要有“狀態(tài)”以及狀態(tài)改變場景的搜索算法，同時BFS由于不需要像DFS算法那樣回溯，故比DFS效率可能會更高一些?；贐FS算法的該進(jìn)算法，比如說R星尋路，DBFS(雙向廣搜)算法等這類改進(jìn)算法場景被應(yīng)用在實(shí)際游戲設(shè)計，GPS導(dǎo)航設(shè)計等場景中。