-
寬度優先搜索
鎖定
- 中文名
- 寬度優先搜索算法
- 外文名
- BFS
- 別 名
- 廣度優先搜索
- 應用學科
- 計算機
- 適用領域
- 計算機
寬度優先搜索概述
BFS,其英文全稱是Breadth First Search。 BFS並不使用經驗法則算法。從算法的觀點,所有因為展開節點而得到的子節點都會被加進一個先進先出的隊列中。一般的實驗裏,其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為 open 的容器中(例如隊列或是鏈表),而被檢驗過的節點則被放置在被稱為 closed 的容器中。(open-closed表)
寬度優先搜索詳細解釋
已知圖G=(V,E)和一個源頂點s,寬度優先搜索以一種系統的方式探尋G的邊,從而“發現”s所能到達的所有頂點,並計算s到所有這些頂點的距離(最少邊數),該算法同時能生成一棵根為s且包括所有可達頂點的寬度優先樹。對從s可達的任意頂點v,寬度優先樹中從s到v的路徑對應於圖G中從s到v的最短路徑,即包含最小邊數的路徑。該算法對有向圖和無向圖同樣適用。
之所以稱之為寬度優先算法,是因為算法自始至終一直通過已找到和未找到頂點之間的邊界向外擴展,就是説,算法首先搜索和s距離為k的所有頂點,然後再去搜索和S距離為k+l的其他頂點。
為了保持搜索的軌跡,寬度優先搜索為每個頂點着色:白色、灰色或黑色。算法開始前所有頂點都是白色,隨着搜索的進行,各頂點會逐漸變成灰色,然後成為黑色。在搜索中第一次碰到一頂點時,我們説該頂點被發現,此時該頂點變為非白色頂點。因此,灰色和黑色頂點都已被發現,但是,寬度優先搜索算法對它們加以區分以保證搜索以寬度優先的方式執行。若(u,v)∈E且頂點u為黑色,那麼頂點v要麼是灰色,要麼是黑色,就是説,所有和黑色頂點鄰接的頂點都已被發現。灰色頂點可以與一些白色頂點相鄰接,它們代表着已找到和未找到頂點之間的邊界。
在寬度優先搜索過程中建立了一棵寬度優先樹,起始時只包含根節點,即源頂點s.在掃描已發現頂點u的鄰接表的過程中每發現一個白色頂點v,該頂點v及邊(u,v)就被添加到樹中。在寬度優先樹中,我們稱結點u 是結點v的先輩或父母結點。因為一個結點至多隻能被發現一次,因此它最多隻能有--個父母結點。相對根結點來説祖先和後裔關係的定義和通常一樣:如果u處於樹中從根s到結點v的路徑中,那麼u稱為v的祖先,v是u的後裔。
寬度優先搜索與深度優先搜索的對比
深度優先搜索用棧(stack)來實現,整個過程可以想象成一個倒立的樹形:
1、把根節點壓入棧中。
2、每次從棧中彈出一個元素,搜索所有在它下一級的元素,把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到,結束程序。
廣度優先搜索使用隊列(queue)來實現,整個過程也可以看做一個倒立的樹形:
1、把根節點放到隊列的末尾。
2、每次從隊列的頭部取出一個元素,查看這個元素所有的下一級元素,把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程序。
寬度優先搜索偽代碼實現
下面的寬度優先搜索過程BFS假定輸入圖G=(V,E)採用鄰接表表示,對於圖中的每個頂點還採用了幾種附加的數據結構,對每個頂點u∈V,其色彩存儲於變量color[u]中,結點u的父母存於變量π[u]中。如果u沒有父母(例如u=s或u還沒有被檢索到),則 π[u]=NIL,由算法算出的源點s和頂點u之間的距離存於變量d[u]中,算法中使用了一個先進先出隊列Q來存放灰色節點集合。其中head[Q]表示隊列Q的隊頭元素,Enqueue(Q,v)表示將元素v入隊, Dequeue(Q)表示對頭元素出隊;Adj[u]表示圖中和u相鄰的節點集合。
BFS(G,S)
foreachu∈V[G]-{s}
do
color[u]←White;
d[u]←∞;
π[u]←NIL;
end;
color[s]←Gray;
d[s]←0;
π[s]←NIL;
Q←{s}
while(Q≠φ)
do
u←head[Q];
for each v∈Adj[u]
do
if(color[v]=White)
then
color[v]←Gray;
d[v]←d[u]+1;
π[v]←u;
Enqueue(Q,v);
end;
Dequeue(Q);
color[u]←Black;
end;
end;
end;
圖1展示了用BFS在例圖上的搜索過程。黑色邊是由BFS產生的樹
[2]
枝。每個節點u內的值為d[u],圖中所示的隊列Q是第9-18行while循環中每次迭代起始時的隊列。隊列中每個結點下面是該結點與源結點的距離。
圖1 BFS在一個無向圖上的執行過程
過程BFS按如下方式執行,第1-4行置每個結點為白色,置d[u]為無窮大,每個結點的父母置為NIL,第5行置源結點S為灰色,即意味着過程開始時源結點已被發現。第6行初始化d[s]為0,第7行置源結點的父母結點為NIL,第8行初始化隊列0,使其僅含源結點s,以後Q隊列中僅包含灰色結點的集合。
程序的主循環在9-18行中,只要隊列Q中還有灰色結點,即那些已被發現但還沒有完全搜索其鄰接表的結點,循環將一直進行下去。第10行確定隊列頭的灰色結點為u。第11-16行的循環考察u的鄰接表中的每一個頂點v。如果v是白色結點,那麼該結點還沒有被發現過,算法通過執行第13-16行發現該結點。首先它被置為灰色,距離d[v]置為d[u]+1,而後u被記為該節點的父母,最後它被放在隊列Q的隊尾。當結點u的鄰接表中的所有結點都被檢索後,第17 -18行使u彈出隊列並置成黑色。
寬度優先搜索實際應用
BFS在求解最短路徑或者最短步數上有很多的應用。
應用最多的是在走迷宮上。
在一個n*n的矩陣裏走,從原點(0,0)開始走到終點(n-1,n-1),只能上下左右4個方向走,只能在給定的矩陣裏走,求最短步數。n*n是01矩陣,0代表該格子沒有障礙,為1表示有障礙物。
int mazeArr[maxn][maxn]; //表示的是01矩陣
int stepArr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向
int visit[maxn][maxn]; //表示該點是否被訪問過,防止回溯,回溯很耗時。
核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。
寬度優先搜索C++
structNode { intx; inty; intstep; Node(intx1,inty1,intstep1):x(x1),y(y1),step(step1){} }; intBFS() { Nodenode(0,0,0); queue<Node>q; while(!q.empty())q.pop(); q.push(node); while(!q.empty()) { node=q.front(); q.pop(); if(node.x==n-1&&node.y==n-1) { returnnode.step; } visit[node.x][node.y]=1; for(inti=0;i<4;i++) { intx=node.x+stepArr[i][0]; inty=node.y+stepArr[i][1]; if(x>=0&&y>=0&&x<n&&y<n&&visit[x][y]==0&&mazeArr[x][y]==0) { visit[x][y]=1; Nodenext(x,y,node.step+1); q.push(next); } } } return-1; }
寬度優先搜索Java
privatestaticintbfs(){ Nodenode=newNode(0,0,0); Queue<Node>queue=newLinkedList<Node>(); queue.add(node); while(!queue.isEmpty()){ NodenewNode=queue.poll(); visit[newNode.x][newNode.y]=1; for(inti=0;i<4;i++){ intx=newNode.x+stepArr[i][0]; inty=newNode.y+stepArr[i][1]; if(x==n-1&&y==n-1){ returnnewNode.step+1; } if(x>=0&&y>=0&&x<n&&y<n &&visit[x][y]==0&&mazeArr[x][y]==0){ Nodenext=newNode(x,y,newNode.step+1); queue.add(next); } } } return-1; } privatestaticclassNode{ privateintx; privateinty; privateintstep; publicNode(intx,inty,intstep){ super(); this.x=x; this.y=y; this.step=step; } }
寬度優先搜索優化
寬度優先搜索總結
在證明寬度優先搜索的各種性質之前,我們先做一些相對簡單的工作 ——分析算法在圖G=(V,E)之上的運行時間。在初始化後,再沒有任何結點又被置為白色。因此第12行的測試保證每個結點至多隻能進入隊列一次,因而至多隻能彈出隊列一次。入隊和出隊操作需要O(1)的時間,因此隊列操作所佔用的全部時間為O(V),因為只有當每個頂點將被彈出隊列時才會查找其鄰接表,因此每個頂點的鄰接表至多被掃描一次。因為所有鄰接表的長度和為Q(E),所以掃描所有鄰接表所花費時間至多為O(E)。初始化操作的開銷為O(V),因此過程BFS的全部運行時間為O(V+E),由此可見,寬度優先搜索的運行時間是圖的鄰接表大小的一個線性函數。
- 參考資料
-
- 1. 嚴蔚敏,吳偉民 著.數據結構(C語言版) :清華大學出版社,2012-05-01
- 2. 算法導論(Introduction to Algorithms Second Edition)中文版 機械工業出版社 2010
- 3. 九度1335闖迷宮 .九度[引用日期2013-12-31]