Breadth First Search (BFS)

廣度優先搜尋（BFS）演算法是一種圖形搜尋演算法。從給定的一個點開始，它會先探索該點所有的相鄰點。再來，依序探索這些相鄰點的相鄰點。這樣子一層一層地探索下去，直到找到結果，或是探索完所有的點。

演算法

BFS 演算法需要兩個資料結構。一個叫 visited，用來記錄點是否已經探索過，而另外一個是 queue。當探索到某個點時，它會將相鄰點一一加入到 queue 裡。然後，每一次都會從 queue 中取出最先加入的點來探索。

Algorithm BFS(v) {
    queue := Queue();
    queue.enqueue(v);
    visited[v] := true;
    while queue.isNotEmpty {
        u := queue.dequeue();
        for all edges (u, w) {
            if !visited[w] {
                queue.add(w);
                visited[w] := true;
            }
        }
    }
}

時間與空間複雜度

BFS 會從 queue 中取出點，而每個點最多只會被加入到 queue 一次，此時間複雜度是 O(V)。然後，它會掃描每個點的所有相鄰點一次，此時間複雜度是 O(E)。所以，BFS 的總時間複雜度是 O(V + E)。

BFS 需要一個資料結構來記錄點是否已經探索過，所以空間是雜度是 O(V)。BFS 還需要一個 queue，而每個點只會被加入一次。在最壞的情況下，除了目前正在探索的點外，所有的點都在 queue，所以空間複雜度是 O(V)。所以，BFS 的總空間複雜度是 O(V)。

範例

下面的範例顯示，在每一個步驟時，queue 和 visited 內部的變化。

參考

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Breadth-first search, Wikipedia.