Here, We will discuss about Breadth First Search (BFS), their algorithms and also explain advantages, disadvantages, time complexity and their applications.
Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
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
There are two such algorithm for traversing the graphs are:
- Breadth First Search (BFS)
- Depth First Search (DFS)
What is Breadth First Search(BFS)?
Breadth First Search (BFS) is a traversing algorithm for exploring a tree or graph. It works similar to level-order traversal of the trees. BFS works level by level.
BFS is better choice if the solution closer to the top of the tree.
This algorithm is a generalization of the breadth-first traversal algorithm for binary trees. It uses a queue.
Breadth First Search(BFS) Algorithm
BFS start traversing from a selected node(source or starting node) and traverse the graph layer-wise thus exploring the neighbour nodes (nodes which are directly connected to source node).
It continues this process until all levels of the graph are completed. Queue data structure is using for storing the vertices of a level.
To traverse the graph breadthwise as follow:
- First move horizontally and visit all the nodes of the current layer.
- Move to the next layer
Advantages of Breadth First Search
- BFS will find the shortest path between the starting point and any other reachable node.
Disadvantages of Breadth First Search
- A BFS on a binary tree generally requires more memory than a DFS.
Time Complexity of Breadth First Search
Time Complexity of Breadth First Search (BFS) is O(V+E) where V is the number of nodes and E is the number of edges.
If we use adjacency list for representing graphs, then Time complexity is O(V2) for adjacency matrix representation.
Applications of Breadth First Search(BFS)
- Finding all connected components in a graph
- Finding all nodes within one connected component
- Find the shortest path between two nodes
- Testing a graph for bipartiteness.
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 [email protected]. See your articles on the main page and help other coders.😎