Breadth First Search (BFS)

Breadth-first search (BFS) algorithm is a graph search algorithm. Starting from a given vertex, it first explores all adjacent vertices of that vertex. Next, explores the adjacent vertices of these adjacent vertices in sequence. In this way, it explores level by level until the result is found, or all vertices are explored.

Algorithm

The BFS algorithm requires two data structures. One is called visited, which is used to record whether the vertex has been explored, and the other is a queue. When a vertex is explored, it will enqueue the adjacent vertices to the queue one by one. Then, each time, the first enqueued vertex will be taken from the queue to explore.

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

Time and Space Complexity

BFS dequeues vertices from the queue, and each vertex is only enqueued once at most, and this time complexity is O(V). Then, it scans all the adjacent vertices of each vertex once, and the time complexity of this is O(E). So, the total time complexity of BFS is O(V + E).

BFS needs a data structure to record whether a vertex has been explored, so the space complexity is O(V). BFS also needs a queue, and each vertex is only enqueued once. In the worst case, all vertices are enqueued except the vertex currently being explored, so the space complexity is O(V). Therefore, the total space complexity of BFS is O(V).

Example

The following example shows, at each step, what happens inside the queue and the visited.

Reference

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