Breadth-first search 廣度優先搜尋法

廣度優先搜尋法，是一種圖形(graph)搜索演算法。

從圖的某一節點(vertex, node)開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，由走訪過的節點繼續進行先廣後深 ...  關於   童玩.程式.老玩童   九連環  智慧拼盤  華容道  資料結構與演算法   疊代與遞廻  回溯法  深度優先搜尋法  廣度優先搜尋法  遊戲   超級運動員  Contact  廣度優先搜尋法 (Breadth-firstSearch) Breadth-firstsearch(BFS)isastrategy forsearchinginagraph.TheBFSbeginsatarootnodeandinspectsall theneighboringnodes.Thenforeachofthoseneighbornodesinturn,it inspectstheirneighbornodeswhichwereunvisited,andsoon.(參1) 廣度優先搜尋法，是一種圖形(graph)搜索演算法。

從圖的某一節點(vertex, node)開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，由走訪過的節點繼續進行先廣後深的搜尋。

以樹(tree)來說即把同一深度(level)的節點走訪完，再繼續向下一個深度搜尋，直到找到目的節點或遍尋全部節點。

廣度優先搜尋法屬於盲目搜索(uninformedsearch)是利用佇列(Queue)來處理，通常以迴圈的方式呈現。

(參2) 範例:廣度優先搜尋法找出下圖的所有節點順序:        假設起始點為A，且每一節點由左至右的順序來搜尋下個節點，則結果為:A,B,C,D,E,F,G 演算法    procedureBFS(vertexs) {    createaqueueQ    enqueuesontoQ    marksasvisited    whileQisnotempty{       dequeueavertexfromQintov       foreachwadjacenttov{          ifwunvisited {             markwasvisited              enqueuewontoQ                }       }    } } 範例:以廣度優先搜尋法找出最短路徑的出口           假設起始點在迷宮的中央，而出口在迷宮的四個角落，由於廣度優先搜尋法是將每個方格的下一步全部走完，所以當最先走到出口的路徑即為最短路徑。

找出最短路徑的出口(JavaScript)         迷宮說明:這個迷宮是經過設計的，繪製的起點同搜索時的起點(在中央)，每一條路徑是利用DFS產生，且將走過的位置放到佇列(queue)中，當遇到死路後不是用回溯(backtacking)方式來繪製下一條路，而是由佇列中取出，如此可得到較放射狀的迷宮，易於看出廣度優先搜尋法的感覺，請參考:迷宮+Queue繪製(JavaScript)。

參考資料:                (1)Breadth-firstsearchwiki:http://en.wikipedia.org/wiki/Breadth-first_search        (2)橫向優先搜尋(breadth-firstsearch):http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/bfs.html 如有版權問題，請告知。