The Breadth First Search algorithm is like the Depth First Search algorithm with the exception that it uses a queue rather than a stack. BFS is technically the opposite of DFS since the BFS algorithm explores the deepest nodes first before backtracking to explore the shallower nodes. An element can be enqueued or dequeued. The queue works on a first-in-first-out principle (FIFO), which means that the element that was enqueued first will be dequeued first. BFS works like this:

• Select the first node
• Explore all unvisited nodes and enqueue them
• Once all unvisited, adjacent nodes have been visited from the first node, dequeue the second node
• Move to the next enqueued node and repeat the process

Let’s take a look at the Breadth First Search Algorithm in action.

The first operation that the BFS algorithm does is that it selects vertex A as the starting point. Why vertex A? Because that’s the vertex that we’ve decided to start with. Vertex A is added to the discovery list and is set as the current node. The current node is represented with the arrow. It is marked as visited but it is not enqueued.

The vertices that are adjacent to it, B and G, are enqueued in alphabetical order. Vertex B is added to the discovery list, followed by vertex G. Both vertices are marked as visited.

Since there are no additional, undiscovered, adjacent nodes, this completes the discovery phase for vertex A. Since vertex B was enqueued first, it’s dequeued now and selected as the node from which the traversal continues.

The process repeats. All adjacent, unvisited vertices from the current node are enqueued. Vertex B has one undiscovered node: vertex C. Vertex C is enqueued, added to the discovery list, and marked as visited.

Since there are no additional, undiscovered, adjacent nodes, this completes the discovery phase for vertex B. Since vertex G was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

All adjacent, unvisited vertices from the vertex G are enqueued. Vertex G has two undiscovered nodes: vertices E and J. Both vertices are enqueued, added to the discovery list, and marked as visited.

Since there are no additional, undiscovered, adjacent nodes, this completes the discovery phase for vertex G. Since vertex C was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

There are no additional, undiscovered, adjacent nodes, so this completes the discovery phase for vertex C. Since vertex E was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

All adjacent, unvisited vertices from the vertex E are enqueued. Vertex E has one undiscovered node: vertex K. Vertex K is enqueued, added to the discovery list, and marked as visited.

There are no additional, undiscovered, adjacent nodes, so this completes the discovery phase for vertex E. Since vertex J was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

All adjacent, unvisited vertices from the vertex J are enqueued. Vertex J has two undiscovered nodes: vertices D and F. Both vertices are enqueued, added to the discovery list, and marked as visited.

Although the algorithm has discovered all the nodes in the graph, it cannot finish until the queue is empty. There are no additional, undiscovered, adjacent nodes from vertex J; this completes the discovery phase for vertex J. Since vertex K was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

There are no additional, undiscovered, adjacent nodes, so this completes the discovery phase for vertex K. Since vertex D was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

There are no additional, undiscovered, adjacent nodes, so this completes the discovery phase for vertex D. Since vertex F was enqueued next, it’s dequeued now and selected as the node from which the traversal continues.

There are no additional, undiscovered, adjacent nodes, so this completes the discovery phase for vertex F. Since the queue is empty, this completes the traversal process.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.