DSA Factory
Free Graphs lessonsGraphs · Stage 2 · Breadth-first · Step 1

Spread out like a ripple

Find the fewest roads between two places by exploring everything one hop away, then two hops, then three. About 15 minutes.

Why depth-first is the wrong tool

Depth-first search charges down one trail as far as it can. It will happily find a route to the target, but it can easily find a long winding one while a short route sat right next to the start.

When the question is the fewest roads, you want the opposite habit: don't go deep, go wide. Look at every neighbour of the start first. Then every neighbour of those. The first ring that contains the target tells you the answer.

Depth-first: finds a route, not necessarily the shortest.
Rings: the first ring holding the target is the answer.

A waiting line keeps the rings in order

How does the search remember whose neighbours to visit next? With a queue, just like a line at a ticket counter. New places join at the back, and the next place to explore is taken from the front.

That keeps the rings in order. The start goes in first. Its neighbours join behind it. By the time we reach the places two hops away, every place one hop away has already had its turn. Write down the hop count for each place as it joins the line, and a place's count is just its parent's count plus one.

Back in, front out: that is what keeps the rings in order.
Mark on joining: so no place waits in the line twice.
In code
dist = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
    node = queue.popleft()
    for nxt in adj[node]:
        if dist[nxt] == -1:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)
return dist[target]
Fewest roads from 0 to 5. The numbers on the dots are hop counts.
0012345
queue
[0]

Start at 0 with a hop count of 0. The line holds just 0.

Move 1 of 4
Quick check

A place has just been added to the line with a hop count of 3. A neighbour of it not yet seen joins the line. What is that neighbour's hop count?

  1. A4, one more than the place it was reached from
  2. B3, the same as its neighbour
  3. C1, because it is one road away from something
Show the answer

4, one more than the place it was reached from. Each ring is one hop beyond the one before it.

Your problem

Fewest roads

There are n places, numbered 0 to n − 1, joined by two-way roads. edges[i] = [a, b] means a road between place a and place b. Return the fewest roads you must travel to get from place start to place target, or -1 if you cannot get there.

Example
n = 6, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [2, 5], [4, 5]], start = 0, target = 5 → 2

1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000 · no road joins a place to itself

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve