Summary: In this tutorial, we will learn what is Breadth First Search Algorithm and how to use the BFS algorithm to traverse graphs or trees in C++ and Java.

Introduction to Breadth First Search Algorithm

Breadth-first search is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Wikipedia

In breadth-first search, the neighbour nodes are traversed first before the child nodes.

For example consider the following GIF visualizing the BFS tree traversal:

bfs algorithm
GIF from Holczer Balazs Advanced Algorithms Course

Yellow color: Node added to the queue for the next visit. Red color: Node marked visited and removed from the queue.

As you can notice, the breadth-first search algorithm is visiting all the nodes in the current depth before moving to the next depth level.

The technique used in BFS is the opposite of DFS, which instead explores all the nodes in a branch until the leaf node and backtrack to visit other nodes.

How to implement the BFS algorithm in Program?

BFS uses queue to traverse nodes or vertex of a graph or tree.

BFS first pushes all neighbor nodes of the current depth into the queue and then visits them by following the FIFO (First In First Out) pattern.

While visiting a node BFS add their unvisited neighbors too to the queue.

Since the queue follows the FIFO pattern, the vertex of the highest level of depth is visited and popped first.

Queue process the deepest nodes which was later added to it, hence implementing breadth first search traversal.

Here is the algorithm for breadth-first search traversal:

  1. Select the root of the graph.
  2. Insert the root vertex into the queue.
  3. Pop a vertex from the queue, mark it as visited, and output its value.
  4. Visit its unvisited neighbor vertex, push them to the queue, and mark visited.
  5. Repeat step 3 until the queue is empty.
  6. When the queue is empty, end the program.

Breadth First Search using Adjacency Matrix

The adjacency matrix is a 2D array that maps the connections between each vertex.

if adjancyM[2][3] = 1, means vertex 2 and 3 are connected otherwise not.

Here is an example of adjacency matrix which we will use in our programs.

bfs adjacency matrix
Adjacency Matrix

Here is the implementation of breadth first search using adjacency matrix.

C++

Java

Output

bfs c++

Breadth First Search using Adjacency List

Each node or vertex holds the list of its neighbor’s nodes known as the Adjacency List.

In the following, program instead of adjacency matrix we used adjacency list to create connection between different vertices i.e. implementing graph.

C++

Java

Note: Here the use of pointers is necessary otherwise changes in the visited value of vertex will not occur because of copy creation causing an infinite literation.

Output

breadth first search in c++

Breadth-first traversal is also known as level order traversal.

In this tutorial, we learned what is breadth first search algorithm and how to implement BFS algorithm to traverse a graph or tree using adjacency list and matrix.

Leave a Reply