Breadth First Search

Let us first talk about the topic which says ‘Breadth First Search’ a methodology of traversing. Here breadth means we will be traversing the graph or tree along the width of it. Traversing means we will be accessing all the nodes along the path at least once. Search here is again means related to traversing.During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them.

Breadth first Search

 

So we are now familiar with the topic so we shall be moving on to basic introduction.BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

Its just like moving along the same line and traversing all nodes after the child node has been reached.

As the name BFS suggests, you are required to traverse the graph breadthwise as follows:

  1. First move horizontally and visit all the nodes of the current layer
  2. Move to the next layer.

 

 Breadth First Search

The distance between the nodes in layer 1 is comparitively lesser than the distance between the nodes in layer 2. Therefore, you need to traverse first layer before traversing another layer.

 

You might get confused here about the difference between child nodes and parent node. Consider the figure the node ‘a’ is parent node to ‘b’ & ‘c’ similarly ‘d’, ‘e’, ‘f’ ,’g’ are parent to the nodes below them. Parent nodes aare also called as root node and the child node are reffered to as siblings.

Traversing child nodes

A graph can contain cycles, which may bring you to the same node again while traversing the graph. To avoid processing of same node again, use a boolean array which marks the node after it is processed. While visiting the nodes in the layer of a graph, store them in a manner such that you can traverse the corresponding child nodes in a similar order.


You can also make this process easy, by using a queue to store the node and mark it as ‘visited’ until all its neighbours (vertices that are directly connected to it) are marked. The queue follows the First In First Out (FIFO) queuing method, and therefore, the neigbors of the node will be visited in the order in which they were inserted in the node i.e. the node that was inserted first will be visited first, and so on.

Now we can look at some of the applications of the bfs(breadth first search)

  • Shortest Path and Minimum Spanning Tree for unweighted graph.
  • Peer to Peer Networks.
  • Crawlers in Search Engines
  • Social Networking Websites
  • etc
  • Note:All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme

 

A Blogger, a coder and IT Student

Leave a reply:

Your email address will not be published.