What is Breadth First Search

The Breadth First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores all of the neighbor nodes at the present present depth before moving on to the nodes at the next depth level.

Algorithm

For implementing BFS we will need a queue. Here are the steps for the BFS:

• Put a root (source) vertex to the queue
• Repeat following steps until the queue is empty
  • Take the next vertex from the queue and mark it as visited
  • Put into the queue all not visited vertices that are adjacent to the current vertex

Here is an implementation of BFS algorithm

    public void Bfs(Graph graph, int root)
    {
        var queue = new Queue<int>();

        // add the root vertex to the queue
        queue.Enqueue(root);

        // the root as visited
        _visited[root] = true;

        while (queue.Count != 0)
        {
            // remove next vertex from the queue
            int node = queue.Dequeue();

            // go thru each adjacent vertex
            foreach (int adjacent in graph.Adjacents(node))
            {
                // Visit not visited vertex
                if (_visited[adjacent] == false)
                {
                    _visited[adjacent] = true;
                    queue.Enqueue(adjacent);
                }
            }
        }
    }

 

BFS example

Let's see how the Breadth First Search algorithm works with an example. We use an undirected graph with 4 vertices.

 

 

The adjacency-lists for the graph will be:

0: 1, 3
1: 0, 3
2: 3
3: 0, 1, 2

and the _visited array is empty.

We start from vertex 0

• put 0 into the queue
• mark vertex 0 as visited: _visited[0] = true
• dequeue 0 and process adjacent vertices (1, 3)
• vertices 1 and 3 were not visited before so we put them into the queue and mark as visited
• after processing 0 adjacent vertices (1 and 3) will be marked as visited (green color)

 

 

Process vertex 1:

• dequeue 1 from the queue
• process adjacent vertices (0, 3)
• 0 and 3 were marked as visited during processing vertex 1, so we skip both

 

 

Process vertex 3:

• dequeue 3 from the queue
• process adjacent vertices (0, 1, 2)
• 0 and 1 were marked as visited during processing vertex 1, so we skip both
• the vertex 2 was not visited before, we put it into the queue and mark as visited

 

 

Process vertex 2:

• dequeue 2 from the queue
• process adjacent vertices 3
• 3 was marked as visited during processing vertex 1, so we skip it

The key difference Breadth First Search from the Depth First Search it finishes process all vertices on one level then goes to the next one.

Time complexity

The time complexity for BFSis O(V + E) where V is the number of vertices and E is the number of edges