Prerequisites: Graphs, BFS.
Problem: Given an undirected and unweighted graph, the task is to find the length of the shortest path between two specified nodes, x and y. If no path exists, return -1.
Solution Approach: We can use BFS to solve the problem. If the node x is in same connected component as node y, then the minimum distance can be found, if not then the answer would be -1. Breadth-First Search (BFS) efficiently explores the graph in a level-by-level manner starting from node x. The inherent nature of BFS makes it suitable for finding the shortest path in an unweighted graph, ensuring that the first occurrence node y is reached using the minimum number of edges.
Key Points:
- Level-by-Level Exploration:
- BFS traverses the graph level by level, starting from the source node (x) and moving outward.
- At each level, all vertices at the same distance from the source are explored before moving to the next level.
- Shortest Path Guarantee:
- In an unweighted graph, BFS guarantees that the first occurrence of a target node (y) is reached with the minimum number of edges.
- As BFS explores the graph level by level, the first time y is encountered, it will be through the shortest possible path.
In case y is not reachable from node x, the distance array shall still have initial infinite value at the end of bfs traversal indicating there is no path between them.
Time complexity: The time complexity is O(N + M), where N is the number of nodes, and M is the number of edges. Each node and edge is processed once during the BFS traversal.
Space complexity: O(N) as the space complexity of BFS is O(N), as we need to put atmost all the nodes in the queue during BFS traversal.