Breadth first search

#1

my doubt is about to understand the recursion properly
in BFS

#2

Hello @tusharkhandelwal315,

Let’s understand it with and example:
image

BFS of graph is same as that of tree:

  1. Make an array named discovered to mark the nodes as visited to avoid multiply copies of same nodes being puhsed to queue.

  2. Let the source node be 1.

  3. Push the source node to queue and pass the queue to the recursive function.

  4. The front of that queue will be the current node. i.e. initially the source node and pop that node out of the queue

  5. One by one push all it’s all neighbouring node into the queue (that share a direct edge with the current node) and Pass the updated queue to the recursive function.

  6. The base case will be when there are no more nodes in the queue i.e. when there is no more node left to traverse.

So, you must relate it to the iterative approach.

  1. At each recursive call, we are just poping the front element of the queue and pushing all it’s neighbours to the queue.
    This is exactly what we do in each iteration in the iterative approach.

  2. This will be repeated until the queue goes empty.
    The same termination condition is used in the iterative approach.

Refer to this links for code:https://www.techiedelight.com/breadth-first-search/

Hope, this would help.
Give a like if you are satisfied.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.