教甄◆電腦科專業題庫下載題庫

Breadth-first search (BFS) is a strategy for searching in a graph.The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. (參1)

廣度優先搜尋法，是一種圖形(graph)搜索演算法。從圖的某一節點(vertex, node)開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，由走訪過的節點繼續進行先廣後深的搜尋。以樹(tree)來說即把同一深度(level)的節點走訪完，再繼續向下一個深度搜尋，直到找到目的節點或遍尋全部節點。

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

範例: 廣度優先搜尋法找出下圖的所有節點順序:

        假設起始點為 A，且每一節點由左至右的順序來搜尋下個節點，則結果為: A, B, C, D, E, F, G

演算法     procedure BFS(vertex s) {     create a queue Q     enqueue s onto Q     mark s as visited     while Q is not empty {         dequeue a vertex from Q into v         for each w adjacent to v {             if w unvisited  {                 mark w as visited                 enqueue w onto Q                     }         }     } }

範例: 以廣度優先搜尋法找出最短路徑的出口    

        假設起始點在迷宮的中央，而出口在迷宮的四個角落，由於廣度優先搜尋法是將每個方格的下一步全部走完，所以當最先走到出口的路徑即為最短路徑。

        
        (1) Breadth-first search wiki: http://en.wikipedia.org/wiki/Breadth-first_search
        (2) 橫向優先搜尋 (breadth-first search): http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/bfs.html

資料來源：