Breadth First Search or BFS in C++ using Queue

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) in C++.

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 C++ using Adjacency Matrix

The adjacency matrix is a 2D matrix 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 represent that there is an edge between two vertexes and “0” represent ‘No Edge’.

bfs adjacency matrix
Adjacency Matrix

Output

bfs c++

Breadth First Search C++ 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.

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++ using adjacency matrix and list. This breadth first traversal technique is also known as level order traversal. If you have any problem then comment below.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.

Leave a Reply

Close Menu
shares