Breadth-first search 廣度優先搜尋法

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
            }
        }
    }
}

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

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

找出最短路徑的出口(JavaScript)

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

參考資料:

        (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

如有版權問題，請告知。