Breadth First Search in C++

0
9242

Breadth First Search is an implementation of graph theory for searching in a graph by exploration of all the nodes available at a certain depth before jumping to next level. Also known as BFS, it is essentially based to two operations: approaching the node close to the recently visited node and inspecting and visiting any node.

Starting from the root node, this method leads to the solution by visiting and inspecting each and every neighbor nodes. In this tutorial, we’re going to discuss a simple program for Breadth First Search in C++ along with its algorithm, pseudo code, and sample output.

Breadth First Search is generally used when the shortest path is to be determined from one node to another node. It uses a queue during the process of searching. Since it visits or inspects a sibling node before inspection child nodes, it is sometimes considered to be the finest technique for traversing a definite or finite graph.

You can read more about BFS here.

Algorithm of Breadth First Search:

During the course of traversing a graph, Breadth First Search utilizes the queue data structure, which helps to store all the generates. These generates should be unexplored nodes only. The type of the search totally relies on the order of placing of nodes on the queue structure for exploration and removal. The algorithm of BFS goes like this:

  1. Put the root node or starting node on queue (say q)
  2. Examine the queue, whether it is empty or not.
    -> If the queue is void, return the failure and stop the searching process.
    -> Else proceed ahead by placing the direct child nodes that has not been discovered yet.
  1. If the goal node (say g) is found as the first element of the queue, return it as success and stop.
  2. Otherwise, removal and expansion of the first element of the queue is required. Place these newly generated offspring at the end of queue at any order.
  3. Go back to the step 2 and repeat.

Pseudo code:

Consider an input graph ‘g’ and its root node ‘v’

  1. Create a queue q
  2. Place v onto ‘q’
  3. Mark the root node ‘v’
  4. while q is not empty:
  5. t ← q.dequeue()
  6. if r is the target or what you are searing: return r
  7. for all edges e in g.adjacentEdges(r) do
  8. o ← g.adjacentVertex(r,e)
  9. if o is not marked: mark o
  10. Place o onto q
  11. return null

Breadth First Search in C++ - Graph

Lets consider a graph above given above. Applying the algorithm, the Breadth First Search from node 1 is: 1, 2, 3, 4, 6, 7, 5. The program given below for Breadth First Search in C++ gives the same as output.

Source Code of Breadth First Search in C++:

This source code of Breadth First Search in C++ mainly utilizes structures, data class and user defined function features of the C++ programming language. struct node  is the major structure used in the source code. The main functions used in the program are as follows:

  • addEdge(1, 2)
  • addEdge(1, 3)
  • addEdge(2, 4)
  • addEdge(3, 4)
  • addEdge(3, 6)
  • addEdge(4 ,7)
  • addEdge(5, 6)
  • addEdge(5, 7)
  • clock()

Breadth First Search in C++ - Output Screen

Also see,
Depth First Search in C++
Dijkstra’s Algorithm Program
Gaussian Filter Generation in C++

The console output of Breadth First Search in C++ displays the starting vertex and the time taken to search. If you’ve any queries regarding BFS, its algorithm or source code, mention/discuss them in the comments section below.

You can find more C++ Tutorials here.

LEAVE A REPLY

Please enter your comment!
Please enter your name here