SUBJECT MATERIAL, EBOOKS, IMPORTANT QUESTION , ASSIGNMENT QUESTION, OLD QUESTION PAPER

Friday, 15 July 2022

Breadth First Search (BFS) Algorithm

What is BFS Algorithm (Breadth-First Search)? Breadth-first search (BFS) is an algorithm that is used to graph data or searching tree or t... thumbnail 1 summary

What is BFS Algorithm (Breadth-First Search)?

  • Breadth-first search (BFS) is an algorithm that is used to graph data or searching tree or traversing structures. 
  • The full form of BFS is the Breadth-first search.
  • The algorithm efficiently visits and marks all the key nodes in a graph in an accurate breadth wise fashion. 
  • This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent to the selected node. Remember, BFS accesses these nodes one by one.
  • Once the algorithm visits and marks the starting node, then it moves towards the nearest unvisited nodes and analyses them. 
  • Once visited, all nodes are marked. These iterations continue until all the nodes of the graph have been successfully visited and marked.

What is Graph traversals?

  • A graph traversal is a commonly used methodology for locating the vertex position in the graph. 
  • It is an advanced search algorithm that can analyze the graph with speed and precision along with marking the sequence of the visited vertices. 
  • This process enables you to quickly visit each node in a graph without being locked in an infinite loop.

Why do we need BFS Algorithm?

There are numerous reasons to utilize the BFS Algorithm to use as searching for your dataset. Some of the most vital aspects that make this algorithm your first choice are:

  • BFS is useful for analyzing the nodes in a graph and constructing the shortest path of traversing through these.
  • BFS can traverse through a graph in the smallest number of iterations.
  • The architecture of the BFS algorithm is simple and robust.
  • The result of the BFS algorithm holds a high level of accuracy in comparison to other algorithms.
  • BFS iterations are seamless, and there is no possibility of this algorithm getting caught up in an infinite loop problem.

The architecture of BFS algorithm

 

  • In the various levels of the data, you can mark any node as the starting or initial node to begin traversing. The BFS will visit the node and mark it as visited and places it in the queue.
  • Now the BFS will visit the nearest and un-visited nodes and marks them. These values are also added to the queue. The queue works on the FIFO model.
  • In a similar manner, the remaining nearest and un-visited nodes on the graph are analyzed marked and added to the queue. These items are deleted from the queue as receive and printed as the result.

 Algorithm of BFS:

  • Step 1: Place the root node inside the queue.
  • Step 2: If the queue is empty then stops and return failure.
  • Step 3: If the FRONT node of the queue is a goal node then stop and return success.
  • Step 4: Remove the FRONT node from the queue. Process it and find all its neighbours that are in ready state then place them inside the queue in any order.
  • Step 5: Go to Step 3.
  • Step 6: Exit.

Breadth-First Search – Example


  • Breadth-First Search algorithm follows a simple, level-based approach to solve a problem. Consider the below binary tree (which is a graph). Our aim is to traverse the graph by using the Breadth-First Search Algorithm.
  • BFS algorithm starts the operation from the first or starting node in a graph and traverses it thoroughly. Once it successfully traverses the initial node, then the next non-traversed vertex in the graph is visited and marked.

 Implementation:


 

Real life Applications Of Breadth-First Search Algorithm

Breadth-first Search is a simple graph traversal method that has a surprising range of applications. Here are a few interesting ways in which Bread-First Search is being used:

  • Crawlers in Search Engines: Breadth-First Search is one of the main algorithms used for indexing web pages. The algorithm starts traversing from the source page and follows all the links associated with the page. Here each web page will be considered as a node in a graph.
  • GPS Navigation systems: Breadth-First Search is one of the best algorithms used to find neighboring locations by using the GPS system.
  • Find the Shortest Path & Minimum Spanning Tree for an unweighted graph: When it comes to an unweighted graph, calculating the shortest path is quite simple since the idea behind shortest path is to choose a path with the least number of edges. Breadth-First Search can allow this by traversing a minimum number of nodes starting from the source node. Similarly, for a spanning tree, we can use either of the two, Breadth-First Search or Depth-first traversal methods to find a spanning tree.
  • Broadcasting: Networking makes use of what we call as packets for communication. These packets follow a traversal method to reach various networking nodes. One of the most commonly used traversal methods is Breadth-First Search. It is being used as an algorithm that is used to communicate broadcasted packets across all the nodes in a network.
  • Peer to Peer Networking: Breadth-First Search can be used as a traversal method to find all the neighboring nodes in a Peer to Peer Network. For example, BitTorrent uses Breadth-First Search for peer to peer communication.
  • Un-weighted Graphs: BFS algorithm can easily create the shortest path and a minimum spanning tree to visit all the vertices of the graph in the shortest time possible with high accuracy.
  • In Garbage Collection: Breadth First Search is used in copying garbage collection using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred over Depth First Search because of better locality of reference: 
  • Cycle detection in undirected graph: In undirected graphs, either Breadth First Search or Depth First Search can be used to detect cycle. We can use BFS to detect cycle in a directed graph also,
  • Ford–Fulkerson algorithm In Ford-Fulkerson algorithm, we can either use Breadth First or Depth First Traversal to find the maximum flow. Breadth First Traversal is preferred as it reduces worst case time complexity to O(VE2). 
  • To test if a graph is Bipartite We can either use Breadth First or Depth First Traversal. 
  • Path Finding We can either use Breadth First or Depth First Traversal to find if there is a path between two vertices. 
  • Finding all nodes within one connected component: We can either use Breadth First or Depth First Traversal to find all nodes reachable from a given node. 

Advantages of Breadth-first search:

  • One of the simplest search strategies.
  • Complete. If there is a solution, BFS is guaranteed to find it.
  • If there are multiple solutions, then a minimal solution will be found
  • The algorithm is optimal (i.e., admissible) if all operators have the same cost. Otherwise, breadth-first search finds a solution with the shortest path length.
  • Finds the path of minimal length to the goal.

Disadvantages of Breadth-first search are:

  • The breadth-first search algorithm cannot be effectively used unless the search space is quite small.
  • Memory Constraints As it stores all the nodes of the present level to go for the next level.
  • If a solution is far away then it consumes time. 

Performance Measurement:

  • Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of nodes traversed in BFS until the shallowest Node. Where the d= depth of shallowest solution and b is a node at every state. T (b) = 1+b2+b3+.......+ bd= O (bd)
  • Space Complexity: Space complexity of BFS algorithm is given by the Memory size of frontier which is O(bd).
  • Completeness: BFS is complete, which means if the shallowest goal node is at some finite depth, then BFS will find a solution.
  • Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the node.