BFS: breadth-first search in Java

Problem

Six streets instead of four

The courier dispatcher wants a route from the depot to the hospital with the fewest streets. In this city every street means a traffic light, a turn and a stop, so the number of streets matters more than the metres.

A colleague wrote a search that takes the first free street and keeps going until it arrives. If it gets stuck, it goes back and tries the next one:

static List<String> anyRoute(Map<String, List<String>> graph,
        String at, String target, Set<String> seen) {
    if (at.equals(target)) return new ArrayList<>(List.of(at));
    seen.add(at);
    for (String next : graph.get(at)) {
        if (seen.contains(next)) continue;
        List<String> rest = anyRoute(graph, next, target, seen);
        if (rest != null) {
            rest.add(0, at);
            return rest;
        }
    }
    return null;
}

List<String> route = anyRoute(graph, "Depot", "Hospital", new HashSet<>());
System.out.println(String.join(" → ", route) + ": " + (route.size() - 1) + " streets");

Depot → Station → Square → Market → Park → Stadium → Hospital: 6 streets

There is a route, but it has 6 streets. Look at the map from the previous lesson: Depot → Station → Square → Cinema → Hospital is 4. The search did not make a mistake: it never asked for the shortest one, it took the first one it found.

The idea

A wave from the depot

Imagine a wave leaving the depot. First it reaches all stops one street away. Then from them all new stops two streets away. Then three. A stop the wave has reached is taken: the next waves do not touch it.

So a stop gets its distance at the moment the wave touches it for the first time, and that is the smallest one possible.

The order "nearer ones first" is kept by a queue: found stops join at the back, and the one being handled leaves from the front. This is BFS (breadth-first search).

dist keeps the distance of every found stop. It is also the set of seen stops: a stop with a dist does not enter the queue a second time.
prev keeps where every stop was found from. With it the route itself is rebuilt later.

See it

Layer by layer

record Search(Map<String, Integer> dist, Map<String, String> prev) {}

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

static List<String> pathTo(Map<String, String> prev,
                           String target) {
    List<String> path = new ArrayList<>();
    String at = target;
    while (at != null) {
        path.add(at);
        at = prev.get(at);
    }
    Collections.reverse(path);
    return path;
}

Step by step, in words

Start at Depot: dist = 0, and it is the only stop in the queue.
Depot leaves the queue. Its neighbours Station and Market are new: dist = 1, prev = Depot, and they join the back of the queue.
Station: Depot already has a dist and is skipped. Square gets dist = 2.
Market also sees Square, but Square is already in the queue with dist = 2. Every stop enters the queue only once. Park: dist = 2.
Layer 2 leaves the queue and opens layer 3: Cinema across the bridge and Stadium. The queue always holds at most two layers, the nearer one in front.
Cinema finds Hospital: dist = 4. When Stadium also reaches it, Hospital already has a dist: the first arrival is the shortest one.
Hospital has nothing new around it. The queue is empty: every stop has its distance from Depot.
pathTo walks back along prev: Hospital ← Cinema ← Square ← Station ← Depot. Reversed, that is the route: 4 streets.

The program runs BFS from the depot, prints the distance to every stop and the route to the hospital:

Search found = bfs(graph, "Depot");
for (String stop : stops) {
    System.out.println(stop + ": " + found.dist().get(stop));
}
List<String> path = pathTo(found.prev(), "Hospital");
System.out.println(String.join(" → ", path) + ": " + (path.size() - 1) + " streets");

Depot: 0
Station: 1
Market: 1
Square: 2
Park: 2
Cinema: 3
Hospital: 4
Stadium: 3
Depot → Station → Square → Cinema → Hospital: 4 streets

ArrayDeque is a queue: add puts at the back, poll takes from the front. How the queue works inside is in the lesson "Stack and queue".

Try it

Put the lines in order

This is the heart of BFS: one turn of the loop. Put the lines in order:

if (dist.containsKey(next)) continue;
dist.put(next, dist.get(stop) + 1);
prev.put(next, stop);
}
String stop = queue.poll();
for (String next : graph.get(stop)) {
queue.add(next);

Try it

Predict the output

The same BFS, but it starts from Cinema. What does the program print for Depot, Stadium and Park?

Search found = bfs(graph, "Cinema");
StringJoiner line = new StringJoiner(" ");
for (String stop : List.of("Depot", "Stadium", "Park")) {
    line.add(String.valueOf(found.dist().get(stop)));
}
System.out.println(line);

Answer

3 3 4

4 2 3

3 2 3

The idea

The route backwards

dist says how many streets there are, but not which ones. The route is in prev: Hospital was found from Cinema, Cinema from Square, Square from Station, Station from Depot. Depot has no prev, because everything started there.

That is why the route is read from the back: from the target along prev to the start, and reversed at the end.

static List<String> pathTo(Map<String, String> prev,
                           String target) {
    List<String> path = new ArrayList<>();
    String at = target;
    while (at != null) {
        path.add(at);
        at = prev.get(at);
    }
    Collections.reverse(path);
    return path;
}

String at = target;
while (at != null) {
    path.add(at);
    at = ;
}

More precisely, if you are curious

The routes in prev form a tree: every stop points to exactly one other, the one it was found from, and the root is the depot. This is called the BFS tree. Every branch from the root to a stop is the shortest route to it. That is why one BFS from the depot gives the shortest routes to all stops at once, not only to the hospital.

If a stop was never found (there is no route), it has no dist. Check that before you call pathTo: otherwise you get a "route" of one stop, the target itself.

The idea

Why the first arrival is the shortest

The queue holds at most two layers: d and d + 1, with the nearer one in front. A stop d + 1 streets away is found from a stop d streets away, and stops d + 2 away come only when the ones at d + 1 start to leave. So a stop gets its dist from the shortest route, and every later route to it is at least as long and is skipped.

It also matters when a stop is marked as seen: at the moment it enters the queue, not when it leaves. Otherwise Square, which is seen both from Station and from Market, would enter twice.

More precisely, if you are curious

The proof in one sentence: by induction on d, all stops at distance d leave the queue before all stops at distance d + 1, and each gets dist = d. This holds only if every edge costs 1. If the streets have different lengths, fewer streets does not mean fewer metres. Then the queue is replaced by a priority queue by the distance travelled, and that is Dijkstra (the Dijkstra lesson in this module).

The idea

What it costs

Every stop enters the queue at most once and leaves once. When it leaves, it looks at its streets. A two-way street is seen from both of its ends. In total: V departures and 2E looks, O(V + E).

That holds for an adjacency list. With a matrix "who are the neighbours" is the whole row, and BFS makes V looks per stop: O(V²). Run both on a grid city of n crossroads:

BFS with an adjacency list O(n)
BFS with a matrix O(n²)

Algorithm	n = 10	n = 1,000	n = 5,000	n = 100,000
BFS with an adjacency list	36	4,872	24,716	498,734
BFS with a matrix	110	1,001,000	25,005,000	≈ 10,002,000,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

Every stop that leaves the queue and every look at a neighbour is counted. At 1000 crossroads the list makes 4,872 operations, and the matrix 1,001,000. At 100,000 crossroads the list makes 498,734, about 5 per crossroad: one departure and up to 4 streets. The matrix at 5000 is already at 25,005,000.

Try it

Find the bug

A colleague decided that the distance of a new stop is "the next number". The program prints:

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.size());
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

Depot: 0
Station: 1
Market: 2
Square: 3
Park: 4
Cinema: 5
Hospital: 7
Stadium: 6
Depot → Station → Square → Cinema → Hospital: 4 streets

The route is right, 4 streets, and yet Hospital comes out at 7. Which line has the bug?

Pick the line with the bug.

More precisely

The queue in every language

ArrayDeque is a ring buffer: add and poll are O(1). LinkedList is a Queue too, but every element is a separate node, and it is slower. Do not use ArrayList with remove(0): it moves all remaining elements, O(n) for every take, and BFS becomes O(V²) even with an adjacency list.

Exercise

The layers of the city

Solve the task in your editor.

Layers and bridges. With BFS from the depot print the stops by layers (the stops of each layer in the order of stops) and the farthest stop. Then close both bridges: remove them from the adjacency list, run BFS again and print which stops can no longer be reached.

String[][] bridges = {
    {"Market", "Park"}, {"Square", "Cinema"},
};

Layer 0: Depot
Layer 1: Station, Market
Layer 2: Square, Park
Layer 3: Cinema, Stadium
Layer 4: Hospital
Farthest: Hospital (4 streets)
Without the bridges you cannot reach: Park, Cinema, Hospital, Stadium

More tasks

The nearest pharmacy. Some stops have a pharmacy. Run one BFS that starts from all pharmacies at once (all of them are in the queue with dist 0), and print for every stop how many streets away the nearest one is.
A maze of shelves. The warehouse is a grid of shelves (#) and aisles (.). Find the fewest steps from the entrance to the exit, where the neighbours of a cell are up, down, left and right.
All the shortest. Count how many different shortest routes there are from the depot to every stop.

Test

Check yourself

1. Why is the first route by which BFS reaches a stop the shortest one in streets?The queue handles all stops d streets away before it gets to those d + 1 awayBecause BFS tries all routes and keeps the shortestBecause the neighbours in the list are sorted by distance

2. A colleague replaced the queue with a stack: it takes the last stop added. What happens?The walk no longer goes in layers, and dist can come out bigger than the shortestNothing: the order does not matterThe program loops forever

3. The streets have lengths in metres. Does BFS give the shortest route in metres?No: BFS counts streets, every street is one step, however long it isYes, if the adjacency list also keeps the metresYes, always

4. How much work does BFS do on a city with V crossroads and E streets, kept as an adjacency list?O(V + E): every stop leaves once, every street is looked at twiceO(V · E)O(V²)

BFS: the fewest stops

Cookies