Free Graphs lessonsGraphs · Stage 2 · Breadth-first · Step 2

One search, every distance

Run the ripple search once and read off how far every place is from the start. About 14 minutes.

Don't stop at the target

In the last step we stopped being interested the moment we found the target. But the search was quietly working out the distance to every other place on its way. We can keep all of it.

Let the search run until the line is empty. Every place it touched now has the number of roads from the start written next to it. Places it never touched still say -1. That -1 is not a bug. It tells you those places are on a separate island that no road connects to the start.

Run to the end: the line emptying is the stopping point.

-1: means unreachable, not zero.

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

Distances from 0. Places 5 and 6 are on their own island.

queue: [0]

Start at 0, distance 0. Every other place begins at -1, not yet reached.

Move 1 of 5

The distances line up in rings

Look at the finished array of distances. There is exactly one place at distance 0, the start. Then all the places at distance 1, then all at distance 2, and so on, with no gaps. If a place sits at distance 4, some neighbour of it sits at distance 3.

That ring structure is useful on its own. Questions like "who is farthest away?" or "how many places are at each distance?" are just questions about this one array, so you can answer them with a single pass after the search.

Rings: distance 0, then 1, then 2, with no gaps.

Quick check

After the search ends, one place's distance is still -1. What does that mean?

ANo chain of roads connects it to the start
BIt is the farthest place from the start
CIt is the start itself

Show the answer

No chain of roads connects it to the start. Every reachable place was given a number, so a -1 can only be a place the search never touched.

Your problem

Distances from the start

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 an array of length n where entry i is the fewest roads from place start to place i, or -1 if place i cannot be reached.

Example

n = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 6]], start = 0 → [0, 1, 1, 2, 3, -1, -1]

1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000

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