Medium · Graphs

Find Shortest Path with BFS

Given an unweighted, undirected graph as adjacency lists adj and two nodes src and dst, return the nodes of a shortest path from src to dst in order (src first, dst last), or null if dst cannot be reached.

Examples

Example 1

{
  "adj": [
    [1, 2],
    [0, 3],
    [0, 3, 6],
    [1, 2, 4],
    [3, 5],
    [4, 6],
    [2, 5]
  ],
  "pos": [
    [176, 44],
    [253, 81],
    [273, 165],
    [219, 232],
    [133, 232],
    [79, 165],
    [99, 81]
  ],
  "src": 0,
  "dst": 5
}

Output: [0, 2, 6, 5]

Example 2

{
  "adj": [
    [1, 2],
    [0, 4],
    [0, 3],
    [2, 4, 5],
    [1, 3, 6],
    [3, 6],
    [4, 5]
  ],
  "pos": [
    [176, 44],
    [253, 81],
    [273, 165],
    [219, 232],
    [133, 232],
    [79, 165],
    [99, 81]
  ],
  "src": 0,
  "dst": 6
}

Output: [0, 1, 4, 6]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.