Start learning free

LESSON 332 OF 344 · GRAPHS

BFS Min Distance to Every Vertex in Java: Queue and Distance Array

Practice BFS, O(V+E) Read the full explanation

Given an unweighted undirected graph with n vertices (labeled 0 to n-1) and a list of edges where edges[i] = [u, v], find the minimum distance (number of edges) from vertex 0 to every other vertex using BFS.

Return an array dist of length n where dist[i] is the minimum distance from vertex 0 to vertex i. Use -1 if a vertex is unreachable.

Example

Input: n = 5, edges = [[0,1],[0,2],[1,3],[2,4]]
Output: [0, 1, 1, 2, 2]
Explanation:
- 0 → 0: distance 0
- 0 → 1: distance 1
- 0 → 2: distance 1
- 0 → 1 → 3: distance 2
- 0 → 2 → 4: distance 2

Constraints

  • 2 <= n <= 1000
  • 1 <= edges.length <= 5000
  • 0 <= u, v < n
  • No self-loops or duplicate edges.
STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · GRAPHS

    Bfs Min Distance To Every Vertex in Java, explained

    Problem overview

    The method bfsMinDistance receives the number of vertices n and an int[][] of edges, where each edge is a pair [u, v]. Vertices are labeled 0 to n - 1 and every edge has the same cost: one step. The method returns an array dist of length n in which dist[i] is the smallest number of edges needed to get from vertex 0 to vertex i, or -1 if vertex i can't be reached.

    For n = 5 and edges = [[0,1],[0,2],[1,3],[2,4]] the answer is [0, 1, 1, 2, 2]. Vertex 0 is zero steps from itself, vertices 1 and 2 are one step away, and vertices 3 and 4 are two steps away, through 1 and 2.

    Approach: breadth-first search

    Breadth-first search (BFS) explores a graph in layers. It first handles the start vertex, then everything one edge away, then everything two edges away, and so on. Since all edges cost the same, the first time BFS reaches a vertex is along a shortest path, and no later route can be shorter. That is why the distance can be written down at that moment and never changed.

    The layer order comes from a queue: first in, first out. Vertices discovered earlier are processed earlier, so closer vertices always come before farther ones. Taking vertices from the wrong end would make the search depth-first and break the distances.

    The distance array also serves as the visited record. It starts filled with -1, meaning "not reached yet". A neighbor whose entry is still -1 is new: give it the current distance plus one and queue it. A neighbor whose entry is not -1 has already been reached, at an equal or smaller distance, so it is skipped. A vertex that is never reached keeps -1, which is exactly what the problem wants for unreachable vertices.

    Step by step

    1. Build the adjacency list: a List<List<Integer>> with one empty ArrayList per vertex, so graph.get(i) holds the vertices that vertex i leads to.
    2. Fill it from edges. For each int[] edge, add edge[1] to the list of edge[0]. The lesson's code follows each edge from its first vertex to its second.
    3. Create the queue as an ArrayDeque declared as a Deque<Integer>, and add vertex 0. add puts a vertex at the back and poll takes one from the front.
    4. Create minDist as an int[] of size n. A new int array starts with zeros, which would wrongly claim every vertex is at distance 0, so fill it with -1 using Arrays.fill. Then set minDist[0] to 0.
    5. Loop while the queue is not empty. Each vertex enters the queue at most once, so the loop ends.
    6. Take the front vertex into int node with poll.
    7. Loop over its neighbors, adjNode, in graph.get(node).
    8. Handle new vertices. If minDist[adjNode] == -1, set it to minDist[node] + 1 and add adjNode to the queue.
    9. Return minDist.

    The solution in Java

    class Solution {
    public int[] bfsMinDistance(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        int[] minDist = new int[n];
        Arrays.fill(minDist, -1);
        minDist[0] = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int adjNode : graph.get(node)) {
                if (minDist[adjNode] == -1) {
                    minDist[adjNode] = minDist[node] + 1;
                    queue.add(adjNode);
                }
            }
        }
        return minDist;
    }
}

    Walking through the example: the queue starts as [0]. Processing 0 sets minDist[1] and minDist[2] to 1 and queues both. Processing 1 reaches 3 and sets it to 2, and processing 2 reaches 4 and sets it to 2. Processing 3 and 4 finds no new vertices, the queue empties, and the result is [0, 1, 1, 2, 2].

    Java details worth a closer look:

    • Deque or Queue. ArrayDeque is the usual choice for a queue in Java. It is faster than LinkedList for this job, and it doesn't allow null elements. Declaring the variable as Deque<Integer> works because add and poll are available on it.
    • poll returns an Integer. Assigning it to an int unboxes it automatically. Since the loop only runs while the queue is non-empty, poll never returns null here.
    • Arrays.fill sets every slot of the array to the given value in one call. Without it, a loop would be needed.
    • Edge direction. The code reads the pairs as edge[0] to edge[1] only. That matches the example, where every edge points away from vertex 0. If edges should work in both directions, add graph.get(edge[1]).add(edge[0]) as well. Without it, a vertex that is only listed as the first endpoint of an edge toward vertex 0 would stay at -1.

    Complexity

    Let m be the number of edges.

    Time: O(n + m). Building the lists is O(n + m). Each vertex is queued at most once because only a -1 entry gets queued. Each vertex's neighbor list is scanned once, so every edge is examined once.

    Space: O(n + m). The adjacency list stores every edge, and the queue and the distance array each hold at most n entries.

    Edge cases and common mistakes

    • Unreachable vertices. With n = 4 and edges = [[0,1],[2,3]], vertices 2 and 3 are never queued, so the result is [0, 1, -1, -1].
    • Forgetting the -1 fill. An unfilled int[] holds zeros, so unreached vertices would look like they sit at distance 0, and the test minDist[adjNode] == -1 would never fire.
    • Setting the source distance. Leaving minDist[0] at -1 would let a neighbor send the search back to vertex 0 and overwrite its distance.
    • Using a stack instead of a queue. Taking the newest vertex first gives some path, not necessarily the shortest one.
    • Setting the distance when the vertex is taken from the queue instead of when it is discovered. The same vertex can then be queued several times before it is first processed.
    • Cycles. A cycle can't cause an endless loop, because a vertex that already has a distance is never queued again.

    Testing

    • n = 5, edges = [[0,1],[0,2],[1,3],[2,4]] gives [0, 1, 1, 2, 2].
    • n = 4, edges = [[0,1],[2,3]] gives [0, 1, -1, -1].
    • n = 3, edges = [[0,1],[1,2],[0,2]] gives [0, 1, 1].
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free