Breadth-First Searchđź›’
Breadth-first search is a graph algorithm used to
- To check if there is a path between two vertices/nodes
- To get the shortest path between two nodes
- To do a traversal of a whole graph i.e. visiting each node in the given graph.
Time complexity
The time complexity of the breadth-first search algorithm is O(v+e). Where v is the number of vertices/nodes and e is for the number of edges.
Explanation
Let’s take an example, suppose we want to see if there exists a path between two nodes in a graph, and in the worst case the node “b” can be at the end of the graph, so we have to go through each node in the graph first, to reach that one. And the time complexity for that will O(n) where n is the number of vertices/node we have in a graph which we can also write as O(v).
While traversing through each node we have to check its “neighbor’s or you can say its edges” as well. So example if a node “c” has 3 edges/neighbors attached to it, we have to perform 3 operations on node “c”. And the time complexity for that will be again O(n) where n is the number of edges that a particular node has, which we can also write as O(e).
Combining the both we get the total time complexity of O(V+E)
- (V: because we are going to visit every node in the worst case)
- (E: Total number of edges a graph has because on each node we have to visit/check its edges as well.
The below coding example is checking if there is a path between node (1) and node (2), in a directed graph. And if there is it will print the path between those two nodes, and again that path will be the shortest path possible between these two nodes.
