FOR FREE MATERIALS
Implement BFS Algorithm and use it to check whether a graph is connected or not
Back to ProgrammingDescription
Introduction:
Connected Graph: An undirected graph is connected if it has at least one vertex and there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. An undirected graph G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints.
BFS Algorithm: Breadth-first search (BFS) is an algorithm that is used to graph data or search tree or traversing structures.
The algorithm efficiently visits and marks all the key nodes in a graph in an accurate breadthwise 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.
As the name suggests, we move in breadth of the graph, i.e., we move horizontally first and visit all the nodes of the current layer and then we move to the next layer.
Rules of BFS Algorithm
● A queue (FIFO-First in First Out) data structure is used by BFS.
● You mark any node in the graph as root and start traversing the data from it.
● BFS traverses all the nodes in the graph and keeps dropping them as completed.
● BFS visits an adjacent unvisited node, marks it as done, and inserts it into a queue.
● Removes the previous vertex from the queue in case no adjacent vertex is found.
● BFS algorithm iterates until all the vertices in the graph are successfully traversed and marked as completed.
● There are no loops caused by BFS during the traversing of data from any node.
Example BFS Algorithm
Algorithm
Algorithm
Input: A graph in adjacency matrix format
Output: Check if it is connected or not using BFS Algorithm
Step 1: Take any vertex as a starting node into queue
Step 2:Take all adjacent vertices of the selected vertex
Step 3: Check if they are visited or not, if not then insert them into queue
Step 4: Mark the vertex visited and delete from queue
Step 5:if the queue is not empty then take the 1st element as next vertex
Step 6:Repeat steps from 2 to 5 while the queue is not empty
Step 7: Check all the vertices is visited or not
if not then print the graph is not connected
else print result
Code
Applications of BFS Algorithm
Let's take a look at some of the real-life applications where a BFS algorithm implementation can be highly effective.
● 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.
● P2P Networks: BFS can be implemented to locate all the nearest or neighboring nodes in a peer to peer network. This will find the required data faster.
● Web Crawlers: Search engines or web crawlers can easily build multiple levels of indexes by employing BFS. BFS implementation starts from the source, which is the web page, and then it visits all the links from that source.
● Navigation Systems: BFS can help find all the neighboring locations from the main or source location.
● Network Broadcasting: A broadcasted packet is guided by the BFS algorithm to find and reach all the nodes it has the address for.
Advantages:
● Breadth first search will never get trapped exploring the useless path forever.
● If there is a solution, BFS will definitely find it out.
● If there is more than one solution then BFS can find the minimal one that requires less number of steps.
● 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.
Disadvantages:
● The main drawback of Breadth first search is its memory requirement. Since each level of the tree must be saved in order to generate the next level, and the amount of memory is proportional to the number of nodes stored, the space complexity of BFS is O(bd). As a result, BFS is severely space-bound in practice so will exhaust the memory available on typical computers in a matter of minutes.
● If the solution is farther away from the root, breadth first search will consume a lot of time.
