Implement BFS to Find Shortest Path in Graph

Scenario

Social network needs to compute the shortest friend-distance between two users in an undirected graph containing millions of nodes.

Question

Implement an iterative BFS that returns the minimum number of hops between a source and target user. Extend the function to also return one of the actual shortest paths.

Hints

Use a queue, visited set, and early exit when target is found.

BFS Shortest Hops and Path in Graph

Given an undirected, unweighted graph with n nodes labeled 0..n-1 and a list of edges edges where each edge is [u, v], implement an iterative BFS that returns the minimum number of hops (edges) between source and target and one corresponding shortest path. Return a dictionary: {"distance": d, "path": p}. If target is unreachable, return {"distance": -1, "path": []}. The path must start at source and end at target. If source == target, return {"distance": 0, "path": [source]}.

Constraints

• 1 <= n <= 200000
• 0 <= len(edges) <= 400000
• 0 <= u, v < n for every edge [u, v]
• 0 <= source, target < n
• Graph is undirected and may be disconnected
• Implement iterative BFS using a queue (no recursion)
• Return one shortest path; if none exists, return distance -1 and empty path

Examples

Example 1

Input: n = 6, edges = [[0,1],[1,2],[2,3],[0,4],[4,5]], source = 0, target = 3
Output: {"distance": 3, "path": [0,1,2,3]}

Explanation: The unique shortest path from 0 to 3 is 0->1->2->3 with 3 hops.

Example 2

Input: n = 4, edges = [[0,1],[2,3]], source = 0, target = 3
Output: {"distance": -1, "path": []}

Explanation: Nodes 0 and 3 are in different components; no path exists.

Hints

1. Use a queue and a visited structure to explore nodes level by level.
2. Track each node's predecessor to reconstruct the path once the target is found.
3. You can stop the BFS as soon as the target is discovered; distance is path length minus one.

Approach

Breadth-first search (BFS) explores the graph layer by layer, guaranteeing that the first time we discover the target we have found a shortest path in an unweighted graph. We maintain a predecessor array to reconstruct the path by backtracking from the target to the source. We also keep a visited array to avoid revisiting nodes. We exit early as soon as the target is discovered to minimize work.

• Time complexity: O(n + m), where n is the number of nodes and m is the number of edges
• Space complexity: O(n + m) for adjacency list, visited, and parent arrays