CodeX
Published in

CodeX

Breadth First Search Algorithm

A concept that is important to grasp in learning Breadth First Search (BFS) is graph traversal. First, if unfamiliar, a graph is a non-linear data structure consisting of a finite set of vertices (aka nodes) and edges (visually represented as lines) that connect the vertices of the graph.

Graph traversal is the process of visiting every vertex and edge once in a defined order. Both the once-only visiting of the vertices and edges as well as the order in which they are visited is important and depends upon the algorithm implemented to solve your question/problem. On this same vein, it is important to keep track of which vertices have been visited, commonly accomplished by marking them.

BFS is the most common approach to traverse a graph and the primary use is for finding the shortest path through a graph. BFS is a traversing algorithm, in which you begin traversing from a selected node (often referred to as the starting or source node) and proceed through the graph by layer — visiting all the nodes neighboring the source node prior to moving to the next level of nodes. In other words, the nodes of the graph are explored horizontally, with all nodes of the current layer visited and then moving to the next layer.

Functionality

BFS works by incorporating a queue. First the source node is added to the queue, followed by this node’s unvisited neighboring nodes. Once the source node no longer has any unvisited neighbors it is removed from the queue. The next in the queue from the first layer is used in place of the source node, and all the unvisited neighboring nodes to this are placed in the queue. Once there are no longer any unvisited neighbors to this node, it is removed from the queue and the process continues with the next node in the queue until there are no more unvisited nodes.

This queue data structure is incorporated in order to track which node to visit next, and indicates the shortest path through the graph from source node to finish. BFS follows three rules —

  • Rule 1: Visit the adjacent unvisited vertex, mark as visited, display, and insert in queue.
  • Rule 2: If no adjacent vertex, remove the first vertex from the queue.
  • Rule 3: Repeat Rule 1 and Rule 2 until queue is empty.

Visual Example

Step 1

We start by initializing the queue for our graph.

Step 2

Next, the source node is selected, in this case this is 0.

Step 3

Our BFS algorithm begins traversal by visiting the neighboring nodes (those with one edge of separation). In our example graph, we first visit node 1, and place that node in the queue.

Step 4

Following, neighboring and unvisited node 2 is visited and placed in the queue after node 1.

Step 5

As you may have predicted, the next step is to visit the source node’s last unvisited neighbor- node 3 and place that within the queue following node 2.

Step 6

As the source node (node 0 in this example) no longer has any unvisited neighboring nodes, the next node in the queue (node 1) is dequeued and used in place of the source node for this next step in the traversal. Node 4 is the only unvisited neighbor node to node 1 and so is visited and placed in the queue. Although all of the nodes in this graph have now been visited, in order for the BFS algorithm to resolve it needs to dequeue all nodes from the queue to confirm that there are no other unvisited nodes within the graph.

Conclusion

The BFS algorithm is the first choice for most needing to quickly search through a graph structure. One situation in which this algorithm is beneficial is if you need to analyze the nodes in a graph and find the shortest path for traversing from one node to another. BFS has a simple but robust architecture that allows for graph traversal in the fewest number of iterations. When compared to other algorithms, BFS has a high level accuracy and has no possibility of getting caught up in a infinite loop.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Denali Balser

Denali Balser

Full-stack software engineer experienced in Ruby on Rails, React, Redux, and JavaScript based programming.