Java breadth-first search: shortest unweighted distances

Java 8+. Use a JDK that supports this release.

Mark a vertex when enqueuing it

A delivery graph contains cycles and repeated routes. Assign a distance before adding a discovered vertex to the queue. Otherwise two parents could enqueue the same vertex before either removes it for processing.

The input is a directed adjacency list with integer vertex IDs from zero through length minus one. The helper rejects invalid source and neighbour IDs. An unreachable vertex retains distance -1.

BFS answers minimum hop count. It does not answer the fastest route when edges carry different travel times. A weighted shortest-path algorithm needs a different relaxation and ordering policy.

Representation is part of the cost

An adjacency list lets the loop examine only outgoing edges of visited vertices. An adjacency matrix would require scanning a row across all possible vertices even when few routes exist.

Distance is enough for hop counts. Reconstructing a path needs a predecessor array recorded when each vertex is first discovered. If several shortest paths exist, neighbour order decides which predecessor is seen first.

Working program

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class DeliveryHops {
    static int[] distances(int[][] routes, int source) {
        if (source < 0 || source >= routes.length) throw new IllegalArgumentException("Invalid source");
        int[] distance = new int[routes.length];
        Arrays.fill(distance, -1);
        Deque<Integer> pending = new ArrayDeque<>();
        distance[source] = 0; pending.addLast(source);
        while (!pending.isEmpty()) {
            int depot = pending.removeFirst();
            for (int next : routes[depot]) {
                if (next < 0 || next >= routes.length) throw new IllegalArgumentException("Invalid route");
                if (distance[next] == -1) {
                    distance[next] = distance[depot] + 1;
                    pending.addLast(next);
                }
            }
        }
        return distance;
    }
    public static void main(String[] args) {
        int[][] routes = {{1, 2}, {3}, {3}, {0}, {}};
        System.out.println(Arrays.toString(distances(routes, 0)));
    }
}

Output

[0, 1, 1, 2, -1]

Cost and design choices

For V vertices and E adjacency entries, the distance-array setup plus traversal takes O(V + E) in the worst case. The queue and distance array require O(V) extra storage. Input adjacency storage is separate.

The helper validates neighbours as it encounters them. Unreachable invalid adjacency entries are not visited. A fully validated reusable graph should check every row once at construction.

Common Mistakes

• Do not mark visited only after dequeueing.
• Do not use DFS to claim minimum-hop distances.
• Do not apply unweighted BFS directly to unequal travel costs.

Connect the contracts

FIFO queue operations preserve the layer order used by this traversal.

Compare minimum-hop discovery with depth-first reachability; both can visit the same vertices while answering different questions.

Compare the Python boundary

Python graph BFS: mark a vertex when it enters the queue.

Continue with range and graph boundaries

Continue with Java bipartite matching: reroute an assignment with an augmenting path, Java Edmonds-Karp max flow: residual capacity and reverse edges, Java A* on a unit grid: an admissible Manhattan bound.