cswork / libraryOpen practice workspace

Coding questions · MathWorks

Implement BFS shortest paths with reconstruction

This question evaluates understanding of graph traversal via breadth-first search, computation of shortest paths in unweighted graphs, and path reconstruction using parent arrays, assessing algorithmic reasoning and implementation skills in the Coding & Algorithms domain.

Given an unweighted graph with n vertices and m edges represented as an adjacency list, implement breadth-first search (BFS) from a source vertex s to return: (1) an array dist where dist[v] is the length of the shortest path from s to v (or −1 if unreachable); and (2) an array parent to reconstruct one shortest path. Handle disconnected graphs, analyze time and space complexity, and provide code in C, C++, Java, or JavaScript.

BFS Shortest Paths with Parent Reconstruction

Given an unweighted graph with n vertices (labeled 0 to n-1) represented as an adjacency list adj (where adj[u] is the list of vertices adjacent to u), and a source vertex s, run breadth-first search from s and return two arrays:

  1. dist — dist[v] is the number of edges on the shortest path from s to v, or -1 if v is unreachable from s.
  2. parent — parent[v] is the vertex immediately before v on one shortest path from s to v. Set parent[s] = -1, and parent[v] = -1 for any unreachable v.

Return the result as a list of two arrays: [dist, parent]. The graph may be disconnected. To make parent deterministic, explore each vertex's neighbors in the order they appear in adj[u], and record parent[v] only the first time v is discovered.

Example. With n = 6, adj = [[1,2],[0,3],[0,3,4],[1,2,5],[2,5],[3,4]], s = 0: dist = [0,1,1,2,2,3] and parent = [-1,0,0,1,2,3]. To reconstruct the shortest path to vertex 5: 5 ← 3 ← 1 ← 0, i.e. 0 -> 1 -> 3 -> 5.

Constraints

  • 1 <= n <= 10^5
  • 0 <= s < n
  • 0 <= m <= 2 * 10^5 (m = total number of directed entries across the adjacency list)
  • Each entry in adj[u] is a valid vertex index in [0, n-1]
  • The graph is unweighted and may be disconnected

Hints

  1. BFS visits vertices in non-decreasing order of distance from the source, so the first time you reach a vertex is along a shortest path.
  2. Use a single dist array initialized to -1 as both the 'visited' marker and the distance: dist[v] == -1 means v is unvisited/unreachable.
  3. When you pop u and look at a neighbor v that is still unvisited, set dist[v] = dist[u] + 1 and parent[v] = u, then enqueue v.
  4. Process adj[u] in order and only set parent[v] on first discovery so the reconstructed path is deterministic. parent[s] stays -1, and any vertex never reached keeps dist = parent = -1.