Breadth-First Search

Breadth-first search explores an unweighted graph in layers of increasing edge distance from a source.

static int[] distances(List<List<Integer>> graph, int source) {
    int[] distance = new int[graph.size()];
    Arrays.fill(distance, -1);
    Queue<Integer> frontier = new ArrayDeque<>();
    distance[source] = 0;
    frontier.add(source);

    while (!frontier.isEmpty()) {
        int vertex = frontier.remove();
        for (int neighbor : graph.get(vertex)) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[vertex] + 1;
                frontier.add(neighbor);
            }
        }
    }
    return distance;
}

Correctness

The queue contains discovered vertices in nondecreasing distance. When a vertex at distance d discovers a new neighbor, it creates a path of length d + 1. Any shorter path would have discovered that neighbor from an earlier layer, so the first assigned distance is minimal.

Each reachable vertex enters the queue once and each outgoing edge is inspected once: Θ(V + E) time over the represented graph and Θ(V) auxiliary space. Store a predecessor alongside distance to reconstruct shortest paths.

Note

BFS minimizes the number of edges. It does not solve arbitrary weighted shortest paths; use Dijkstra only when weights are non-negative.