????????圖的廣度優(yōu)先遍歷和樹的廣度優(yōu)先遍歷類似，樹是層序遍歷，從根節(jié)點(diǎn)出發(fā)找到其所有的孩子結(jié)點(diǎn)。而圖的廣度優(yōu)先就是從一個(gè)結(jié)點(diǎn)開始，搜索所有的相鄰節(jié)點(diǎn)。而圖與樹不同點(diǎn)在于，樹不存在回路，所以搜索相鄰的結(jié)點(diǎn)不會(huì)搜到已經(jīng)訪問過的結(jié)點(diǎn)，而圖搜索相鄰頂點(diǎn)時(shí)可能會(huì)重復(fù)訪問。所以，圖需要對每個(gè)頂點(diǎn)進(jìn)行標(biāo)記。

????????那么具體如何實(shí)現(xiàn)對圖的廣度優(yōu)先遍歷呢？之前了解到，樹的層序遍歷需要一個(gè)輔助隊(duì)列，BFS也是采取類似的方法。這里我們主要用到兩個(gè)圖的基本操作，一個(gè)是尋找第一個(gè)相鄰節(jié)點(diǎn)FirstNeighbor，一個(gè)是尋找相鄰節(jié)點(diǎn)的下一個(gè)相鄰節(jié)點(diǎn)NextNeighbor。同時(shí)定義一個(gè)bool型的數(shù)組visited[]標(biāo)記每個(gè)頂點(diǎn)有沒有被訪問過。

算法如下：

void BFS(G,v){? ?//從頂點(diǎn)v出發(fā)遍歷圖G

????visit(v);

????visited(v)=true;

????Enqueue(Q,v);????????//v進(jìn)入隊(duì)列Q

????while(isempty(Q)){ //隊(duì)列非空

????????Dequeue(Q,v);? //隊(duì)頭出隊(duì)

????????for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor){ //遍歷與隊(duì)頭頂點(diǎn)相鄰的所有頂點(diǎn)

????????????if(!visited(w)){ //鄰接節(jié)點(diǎn)沒有被訪問過

????????????????visit(w);

????????????????visited(w)=true;

????????????????Enqueue(Q,w); //訪問并入隊(duì)

????????????????????????????????}

????????????????????}

????????}

}

????????總體來看，廣度優(yōu)先遍歷和層序遍歷從實(shí)現(xiàn)方式來看十分類似（因?yàn)闃淦鋵?shí)就是一個(gè)特殊的圖），只是要記住廣度優(yōu)先遍歷每次訪問完需要標(biāo)記，訪問時(shí)也要排除掉標(biāo)記的。但是圖的存儲(chǔ)方式不同遍歷的次序也是不同的，鄰接表的遍歷次序是唯一的。

????????并且此方法對于非連接圖的遍歷也存在弊端，不過只需在遍歷停止后，再遍歷一遍visited[]數(shù)組，如果存在數(shù)組值為false，在以該節(jié)點(diǎn)為起始節(jié)點(diǎn)進(jìn)行BFS遍歷，直到?jīng)]有沒訪問的節(jié)點(diǎn)即可。實(shí)現(xiàn)方法如下：

void BFSTraverse(G){

for(i=0;i<G.vexnum;i++)visited[i]=false; //初始化visited數(shù)組

InitQueue(Q);

for(i=0;i<G.vexnum;i++){

????????if(visited[i]==false){?

????????????BFS(G,i);

????????????????}

}

}

????????顯然對于無向圖，調(diào)用BFS的次數(shù)=連通分量數(shù)。BFS的空間復(fù)雜度，輔助隊(duì)列最大為O（|v|）。此算法的主要開銷來自于訪問頂點(diǎn)和找到相鄰的鄰接點(diǎn)，對于鄰接矩陣，尋找頂點(diǎn)鄰接點(diǎn)的時(shí)間復(fù)雜度為O(v)，共有v個(gè)頂點(diǎn)因而查找所有頂點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O（v^2）。對于鄰接表，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)只需O(E)的時(shí)間復(fù)雜度，總時(shí)間復(fù)雜度為O(V+E)。

????????因?yàn)槲覀冊谶M(jìn)行廣度優(yōu)先時(shí)避免了重復(fù)訪問，因此有的邊不需要經(jīng)過就能訪問到所有的點(diǎn)，那么我們把這些邊去掉就得到了廣度優(yōu)先生成樹。而由于鄰接表不唯一可能遍歷的序列不唯一，從而導(dǎo)致廣度優(yōu)先生成樹也不唯一。由此，我們可以想到，對于非連通圖的BFS可以得到廣度優(yōu)先森林。

????????在了解了廣度優(yōu)先搜索的原理后，下面我們開始學(xué)習(xí)其最重要的一個(gè)應(yīng)用——求最短路徑。最短路徑問題有幾個(gè)常見的場景：單源最短路徑，每對頂點(diǎn)間的最短路徑。BFS可以用來求無權(quán)圖的單元最短路徑。

????????我們只需在BFS算法的基礎(chǔ)上增加兩個(gè)數(shù)組，一個(gè)數(shù)組存放源節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離，一個(gè)數(shù)組存放該路徑的上一個(gè)頂點(diǎn)。實(shí)現(xiàn)方法如下：

void BFS_Min_Distance(G,u){

visited(u)=true;

for(i=0;i<G.vexnum;i++){d[i]=-1;

path[i]=-1;

}//初始化路徑長度和路徑前驅(qū)節(jié)點(diǎn)

d[u]=0;

EnQueue(Q,u);

while(isEmpty(Q)){

DeQueue(Q,u);//隊(duì)頭元素出隊(duì)

for(w=FirstNeigobor(G,u);w>=0;w=NextNeighbor(G,u,w)){//訪問鄰接節(jié)點(diǎn)

while(!visited[w]){

d[w]=d[u]+1;

path[w]=u;

visited[w]=true;

EnQueue(Q,w);}

????????}//if

????}//while

}

通過回溯path數(shù)組，我們可以找到最短路徑，多么精妙的算法。同時(shí)我們可以發(fā)現(xiàn)，通過廣度優(yōu)先生成樹的節(jié)點(diǎn)和根節(jié)點(diǎn)的距離就是最短路徑。