LESSON 332 OF 344 · GRAPHS

BFS Min Distance to Every Vertex in JavaScript

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

Guided

Ctrl + Enter to check

JAVASCRIPT · GRAPHS

Bfs Min Distance To Every Vertex in JavaScript, explained

Problem overview

The method bfsMinDistance receives the number of vertices n (labeled 0 to n - 1) and a list of edges, where each edge is a pair [u, v]. All edges have the same length, so a distance is simply a number of edges. The method returns an array dist of length n in which dist[i] is the minimum number of edges on a route from vertex 0 to vertex i, or -1 when vertex i cannot 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 at distance 0 from itself, vertices 1 and 2 are one edge away, and vertices 3 (through 1) and 4 (through 2) are two edges away.

Approach: breadth-first search, level by level

Breadth-first search (BFS) explores a graph in rings around the start. First comes the start itself, then everything one edge away, then everything two edges away, and so on. Since no ring is processed before the previous one is finished, the first time BFS reaches a vertex is along a route with the fewest possible edges. That is why BFS is the tool for shortest paths when every edge counts the same.

The ordering comes from a queue, a first-in, first-out list. Discovered vertices wait in the queue in the order they were found, and the vertex that has waited longest is processed next. Vertices of ring k are always queued before those of ring k + 1, because ring k + 1 vertices are only found while processing ring k.

The distance array also serves as the "visited" record. It starts as all -1, and a vertex whose entry is still -1 has not been reached. The moment a vertex is reached, its entry is set, so it can never be queued twice. Depth-first search would not give these distances, since it follows one long route before trying others and may reach a vertex the long way first.

Step by step

Build the adjacency list. Array.from({length: n}, () => []) creates one separate empty array per vertex, so graph[i] will hold the neighbors of vertex i.
Fill it from the edges. For each edge, push edge[1] onto graph[edge[0]]. This lesson records each edge in the direction it is listed, from edge[0] to edge[1]. Building the list takes O(m) time for m edges.
Create the queue as an array holding only the start vertex, [0]. Items are added at the back with push and removed from the front with shift.
Create the distance array. new Array(n).fill(-1) marks every vertex as unreached, and minDist[0] = 0 says the start is zero edges from itself. new Array(n) alone only reserves empty slots, so fill is needed.
Loop while the queue is not empty. Each vertex enters the queue at most once, so the loop runs at most n times.
Take the front vertex with queue.shift(). Taking from the back instead would turn the search into a depth-first one and break the distances.
Look at each neighbor in graph[node]. Across the whole run, every edge is looked at once.
Handle a new vertex. If minDist[adjNode] === -1, set it to minDist[node] + 1 and push adjNode onto the queue. This is the first and therefore shortest arrival, and the check stops any later arrival from overwriting it.
Return minDist. Vertices that were never reached keep their -1.

On the example: the queue starts as [0]. Processing 0 reaches 1 and 2 (distance 1), giving the queue [1, 2]. Processing 1 reaches 3 (distance 2). Processing 2 reaches 4 (distance 2). Processing 3 and 4 finds no new vertices, the queue empties, and the result is [0, 1, 1, 2, 2].

The solution in JavaScript

class Solution {
    bfsMinDistance(n, edges) {
        const graph = Array.from({length: n}, () => []);
        for (const edge of edges) {
            graph[edge[0]].push(edge[1]);
        }
        const queue = [0];
        const minDist = new Array(n).fill(-1);
        minDist[0] = 0;
        while (queue.length > 0) {
            const node = queue.shift();
            for (const adjNode of graph[node]) {
                if (minDist[adjNode] === -1) {
                    minDist[adjNode] = minDist[node] + 1;
                    queue.push(adjNode);
                }
            }
        }
        return minDist;
    }
}

JavaScript details worth knowing:

Edge direction. The loop stores only edge[0] to edge[1]. If an edge must be walkable both ways, add a second line, graph[edge[1]].push(edge[0]);. With the lesson's example, where each edge is listed from the vertex nearer to 0, the one-way list gives the right answer. For n = 3 and edges = [[1, 0], [1, 2]], the one-way list returns [0, -1, -1], while storing both directions would return [0, 1, 2].
An array as a queue. push adds to the end and shift removes from the start, which makes an array behave as a queue. shift has to move the remaining elements down, so it can be slow on arrays with a very large number of items. With at most 1,000 vertices that does not matter. For bigger graphs, keep an index to the front, such as let head = 0, read queue[head++], and never remove anything.
Strict equality. minDist[adjNode] === -1 compares without type conversion, which is the safe default. Here all the values are numbers, so == would behave the same, but === is the habit to keep.
const arrays can change. const queue and const minDist only forbid assigning a new array to those names. Pushing, shifting and writing elements are allowed.
Array.from versus fill for nested arrays. new Array(n).fill([]) would give every vertex the same neighbor list. The factory function in Array.from avoids that.

Complexity

Let n be the number of vertices and m the number of edges.

Time: O(n + m). Building the list is O(m). Each vertex is queued and removed at most once, and the neighbors of each vertex are scanned once, so the search looks at every edge at most once. Counting shift as constant time is accurate for the sizes in this lesson.

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

Edge cases and common mistakes

Unreachable vertices. A vertex with no route from 0 keeps -1. For n = 4 and edges = [[0, 1]] the answer is [0, 1, -1, -1].
The start vertex. It must be set to 0 before the loop. If it were left at -1, a route that returns to 0 would set it to a positive number.
Marking when taking from the queue. If the distance were set when a vertex is removed from the queue instead of when it is added, the same vertex could be queued many times by different neighbors.
Using pop instead of shift. pop takes from the back and makes the search depth-first. The distances then depend on the order of the edges, not on the shortest route.
Updating a distance twice. The === -1 test is what keeps the first, shortest value. Without it, a later and longer route would overwrite a correct distance.
Shared inner arrays. Building the adjacency list with fill([]) would make every vertex appear to have every edge.

Testing

n = 5, edges = [[0, 1], [0, 2], [1, 3], [2, 4]] gives [0, 1, 1, 2, 2].
n = 4, edges = [[0, 1]] gives [0, 1, -1, -1].
n = 4, edges = [[0, 1], [1, 2], [2, 3], [0, 3]] gives [0, 1, 2, 1], because the shortcut from 0 to 3 wins.

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free