Breadth First Search (BFS) is the traversing algorithm used for graphs and trees. From the name “Breadth first search” itself we get an idea that the traversal of nodes should follow breadth pattern instead of going deep.

Let’s discuss breadth first search (BFS) algorithm.

Breadth First Search Algorithm

bfs algorithm
Screenshots from Holczer Balazs Advanced Algorithms Course

Note: Yellow color: Node added to queue.

Red color: Node marked visited and removed from queue.

  1. To perform BFS first choose the root of the graph.
  2. Insert the root in the queue.
  3. Mark the root visited and print out the root value.
  4. Pop the root node/vertex and visit its child or neighbor.
  5. Check if they are visited. If not then push them into the queue.
  6. Do the same for all the vertex connected to the root (Vertex connected to the one node can be also called as child or neighbor)
  7. Now the queue contains the child/neighbor of the root. Repeat the process from step 4 for each and every vertex in the queue until all the vertex are visited

Note: By this algorithm, it is assumed that if the queue is empty then all the vertex are visited.

Breadth First Search in C++|Java using Adjacency Matrix

The adjacency matrix is a 2D array in which the index of the matrix is equivalent to nodes.

In our case S=0, A=1, B=2, C=3 and D=4.

“1” in the matrix entry represent that there is an edge between two vertexes and “0” represent ‘No Edge’.

bfs adjacency matrix
Adjacency Matrix

C++

Java

Output

bfs c++

Breadth First Search in C++|Java using Adjacency List

Each Vertex class contains a list which stores the vertex connected to the current Vertex object/class.

Here adjacency and neighbor means same.

C++

Java

Note: Here the use of pointers is necessary other wise changes in the visited value of vertex will not occur because of copy creation. Hence it will cause infinite loop.

Output

breadth first search in c++

These are the two ways to implement breadth first search in c++ and java using the adjacency matrix and list. This breadth-first traversal technique is also known as level order traversal. If you have any doubt then comment below.

Leave a Reply

Close Menu