注意：本內(nèi)容主要是介紹用BFS實現(xiàn)圖的遍歷，所以需要對圖的結(jié)構(gòu)有所了解。
一、什么是BFS？
BFS（Breadth First Search，廣度優(yōu)先搜索，又名寬度優(yōu)先搜索），與深度優(yōu)先算法DFS往一個方向“死磕到底，不撞南墻不回頭”的思維方式不同，廣度優(yōu)先搜索算法關(guān)注的重點在于對每一層結(jié)點進行下一層的訪問。
二、BFS算法介紹
BFS算法和核心思路就是：從某個點一直把其鄰接點走完，然后任選一個鄰接點把與之鄰接的未被遍歷的點走完，如此反復(fù)走完所有結(jié)點。類似于樹的層序遍歷。
所以，BFS的核心就是要把當(dāng)前在哪作為一個狀態(tài)存儲，并將這個狀態(tài)交給隊列進行入隊操作
算法步驟（用隊列實現(xiàn)）
a) 訪問指定起始點。
b) 訪問當(dāng)前頂點的鄰接頂點有未被訪問的頂點，并將之放入隊列中。
c) 刪除隊列的隊首節(jié)點。訪問當(dāng)前隊列的隊首，前面的步驟。直到隊列為空。
d) 若途中還有頂點未被訪問，則再選一個點作為起始頂點。重復(fù)前面的步驟（針對非連通圖）。
三.、案例圖示
我們直接上案例進行說明，就本圖而言，其訪問順序可以是：1--2--3--4--5（并不唯一）
遍歷圖的具體步驟如下：
????????首先從1開始，1結(jié)點處連接著2，3兩個結(jié)點，所以我們先訪問2，3兩個結(jié)點。同時我們把兩個結(jié)點按照訪問順序入隊，比如，選擇2，3為入隊順序，所以之后我們先出隊狀態(tài)2，再來依次訪問結(jié)點2所連接的4，5兩個結(jié)點，同樣的，按照順序入隊4，5結(jié)點，然后操作完狀態(tài)2之后，我們再出隊狀態(tài)3，并依次訪問它的后續(xù)，但此時發(fā)現(xiàn)3的后續(xù)結(jié)點已經(jīng)訪問過了，并且檢查發(fā)現(xiàn)所有的結(jié)點都已經(jīng)被訪問完畢，說明遍歷結(jié)束了。最后我們得到圖的遍歷次序：1--2--3--4--5
四、相關(guān)代碼
具體實現(xiàn)遍歷圖的代碼示例：
void BFSL(int pos,pGraph G,int visited[30])//從pos點開始進行廣度優(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;
}
}
}?我們使用BFS解決問題的一般模板如下：
/**
?* 返回合適的檢索數(shù)據(jù)
?*/
int BFS(Node root, Node target)?
{
? ? Queue<Node> queue; ?//創(chuàng)建隊列
? ? int step = 0; ? ? ? // 當(dāng)前隊列的步驟點
? ? // 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ù)組實現(xiàn)
? ? ? ? ? ? ? ? add next to queue;
? ? ? ? ? ? }
? ? ? ? ? ? remove the first node from queue;
? ? ? ? }
? ? }
? ? return -1; ? ? ? ? ?//出錯返回值
}五、BFS的一些應(yīng)用場景
BFS算法的實際應(yīng)用場景：文章來源：http://www.zghlxwxcb.cn/news/detail-405537.html
最典型的有地圖搜索，迷宮尋路等這些需要有“狀態(tài)”以及狀態(tài)改變場景的搜索算法，同時BFS由于不需要像DFS算法那樣回溯，所以效率可能會比DFS更高一些。文章來源地址http://www.zghlxwxcb.cn/news/detail-405537.html
到了這里，關(guān)于廣度優(yōu)先搜索（BFS）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
