（原創）BFS廣度優先演算法，看完這篇就夠了
BFS演算法
上一篇文章講解了DFS深度優先遍歷的演算法，我們說 DFS 顧名思義DEEPTH FIRET，以深度為第一標準來查詢，以不撞南牆不回頭的態度來發掘每一個點，這個演算法思想get到了其實蠻簡單。那麼 BFS 和DFS有什麼相同點和不同點呢？
我覺得有一種比喻對於 DFS 和 BFS 從方法論的角度解釋很到位，DFS 就像是小明要在家裡找到鑰匙，因為對位置的不確定，所以一間一間的來找，深度遍歷能確保小明走過所有的屋子。而 BFS 像是近視的小明的眼鏡掉在了地上，小明肯定是先摸索離手比較近的位置，然後手慢慢向遠方延伸，直至摸到眼鏡，像是以小明為中心搜尋圈不斷擴大的過程。所以如果說 DFS 從遍歷的層次結構上類似樹的先序遍歷，那麼BFS演算法按照裡外順序逐漸增加深度的做法，就像極了樸素的層次遍歷，例如：
把左圖拉平，按照層序把結點排列下來，各節點的連線關係並沒有變，圖結構沒有發生變化，但是這時，我們從A出發，按層序遍歷可以得到順序是 A B F C I G E D H
結合上一篇文章的 DFS ，我們可以發現這兩種演算法的區別在每一個點上都能得以體現，比如 A 點，DFS 鼓勵結點向著一個方向衝，BFS 則會在一個點上按照頂點下標次序遍歷完所有沒有訪問過的結點，比如A點遍歷完，馬上開始掃描，如果 B F這兩個點沒有被寵幸過，那麼一定要翻完 B、F 這兩個點的牌子之後，才會繼續訪問第二層，即把A點相連的結點全部遍歷完成才行，當然到了第二層 發現 B、F 早就被A安排過了，就不再進入這兩個點的迴圈，後面的一樣，這裡就不再贅述。
我們回憶一下DFS演算法，DFS沿著一個方向走最後是要走回頭路的，因為它遲早會遍歷到一個所有分支都被訪問過的結點，那麼要走回頭路意味著我們實現 DFS 時應該選擇後進先出的棧結構，而現在的 BFS 演算法是每經過一個點就會遍歷所有沒訪問過的點，同時，一個點如果已經訪問完，那麼它就沒有利用價值了，所以應該使用佇列先進先出的特點
這裡是圖形演示：
下面我們來看程式碼實現：
這是鄰接矩陣實現 BFS 演算法，結構定義見上一篇文章
void BFS(MGraph *G)
{
int i,j;
Queue Q;
InitQueue(&Q);
for(i = 0; i < G.numVertexes;i++)
{
visited[i] = FALSE;
}
for(i = 0;i < G.numVertexes;i++)
{
if(!visited[i])
{
visited[i] = TRUE;
printf("%c",&G.vexs[i]);
EnQueue(&Q,i);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&i);
for(j = 0;j < G.numVertexes;j++)
{
while(G.arc[i][j] == 1 && !visited[j])
{
visited[j] = TRUE;
printf("%c",G.vexs[j]);
EnQueue(&Q,j);
}
}
}
}
}
}
這是鄰接表實現的程式碼：
void BFS(GraphAdjList GL)
{
int i;
Queue Q;
EdgeNode *p;
InitQueue (&Q);
for(i = 0;i < GL->shuliang;i++)
{
visited[i] = FALSE;
}
for(i = 0;i < GL->shuliang;i++)
{
if(!visited[i])
{
visited[i] = TURE;
printf("%c",GL->adjlist[i].data);
EnQueue(&Q,i);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&i);
p = GL->adjlist[i].firstedge;
while(p)
{
if(!visited[p -> adjvex])
{
visited[p -> adjvex] = TRUE;
printf("%c",GL->adjlist[p -> adjvex].data);
EnQueue(&Q,p->adjvex);
}
p = p -> next;
}
}
}
}
}
個人感覺程式碼蠻好懂，這一塊感覺需要多多思考，廣度優先和深度優先小到日常生活，大到資料模型，有著廣泛的作用，而這篇文章中的兩種方法，因為都要遍歷整張圖，所以其演算法時間複雜度相同，所以對於全圖遍歷並沒有什麼明確選擇的優勢，而如果目的在於儘快地找到目的點，那麼深度優先更佔優勢；而如果是不斷擴大遍歷範圍，尋找相對最優解則是廣度優先看起來更划算。演算法就到這裡，經驗和思路只能靠大家自己在實踐中多多總結，得到自己使用的一套方法。