Shortest Path in Unweighted Graph

Given an unweighted undirected graph as an adjacency list, and a source vertex, return an array where `dist[i]` is the **shortest distance** (number of edges) from the source to vertex i. Unreachable vertices should have distance **-1**.

Examples

Input: graph = [[1,2],[0,3],[0,3],[1,2]], src = 0

Output: [0,1,1,2]

0 is the source; 1 and 2 are one edge away; 3 is two edges away.

Input: graph = [[1],[0],[3],[2]], src = 0

Output: [0,1,-1,-1]

Vertices 2 and 3 are in a disconnected component.

Constraints

• 1 <= vertices <= 2000

Complexity Analysis

Time

O(V + E)

standard BFS.

Space

O(V)

distance array and queue.

Test Cases

#1 — Connected graph

Input: graph=[[1,2],[0,3],[0,3],[1,2]] src=0

Expected: [0,1,1,2]

#2 — Disconnected component

Input: graph=[[1],[0],[3],[2]] src=0

Expected: [0,1,-1,-1]

#3 — Single isolated vertex

Input: graph=[[]] src=0

Expected: [0]

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.