Find Path Between Two Nodes

Given an undirected graph as an adjacency list, and two nodes **src** and **dst**, determine whether a path exists between them. Return the path as an array of vertices if it exists, otherwise return an empty array.

Examples

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

Output: [0,1,2,3]

Direct path through the chain.

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

Output: []

No path — two disconnected components.

Constraints

• 1 <= vertices <= 1000
• src != dst

Complexity Analysis

Time

O(V + E)

Space

O(V)

visited set and parent map for path reconstruction.

Test Cases

#1 — Connected path

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

Expected: [0,1,2,3]

#2 — Disconnected

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

Expected: []

#3 — Direct edge

Input: graph=[[1],[0]] src=0 dst=1

Expected: [0,1]

Interactive graph explorer available!

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