Start learning free

LESSON 336 OF 348 · GRAPHS

BFS Min Distance to Every Vertex in TypeScript: Breadth-First Search

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

    TYPESCRIPT · GRAPHS

    Bfs Min Distance To Every Vertex in TypeScript, explained

    Problem overview

    The method bfsMinDistance receives n, the number of vertices labeled 0 to n - 1, and a list of edges, where each edge is a pair [u, v]. It returns an array dist of length n. Entry dist[i] is the minimum number of edges on a path 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 at distance 0 from itself. Vertices 1 and 2 are one edge away. Vertex 3 is reached through 1 and vertex 4 through 2, two edges each.

    Approach: explore in rings around the source

    Because every edge counts as 1, the distance to a vertex is simply the number of steps in the shortest walk. Breadth-first search (BFS) finds those walks naturally. It visits vertex 0 first, then everything one edge away, then everything two edges away, and so on, ring by ring. The first time BFS reaches a vertex is therefore along a shortest path, so that is the distance to record, and it never needs updating.

    The ring-by-ring order comes from a queue, which hands out items first in, first out. Vertices are enqueued as they are discovered, and they are processed in the order they were discovered, so all vertices at distance d are processed before any at distance d + 1. A depth-first search, which uses a stack or recursion, would dive deep along one branch and could reach a vertex by a long route first, so it doesn't give shortest distances.

    The distance array doubles as the visited marker. It starts filled with -1, meaning "not reached yet". Vertices that BFS never reaches keep that -1, which is exactly what the problem wants for unreachable vertices.

    Step by step

    1. Create the adjacency list. graph holds one empty number[] per vertex, built with Array.from so that each vertex gets its own array. Looking up a vertex's neighbours then takes constant time.
    2. Fill it from edges. For each edge, push edge[1] onto graph[edge[0]].
    3. Create the queue as a number[] that starts with vertex 0. An array works as a queue: push adds at the back and shift removes from the front.
    4. Create minDist with n entries, all -1, and set minDist[0] to 0. The source is zero edges from itself.
    5. Loop while the queue is not empty. Each vertex is enqueued at most once, so the loop runs at most n times.
    6. Take the front vertex with shift() into node. The result type is number | undefined, because shift returns undefined on an empty array, so the code adds ! to tell the compiler that the loop condition guarantees a value.
    7. Loop over the neighbours of node with adjNode as the variable.
    8. Handle a new vertex. If minDist[adjNode] is still -1, set it to minDist[node] + 1 and push adjNode onto the queue.
    9. Return minDist.

    The solution in TypeScript

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

    The details worth knowing:

    • Fresh arrays per slot. Array.from({length: n}, () => []) runs the function once per index. new Array(n).fill([]) would store a single array in every slot, so a push to one vertex's list would appear in all of them.
    • new Array(n).fill(-1). new Array(n) only reserves n empty slots; fill gives each a value. The result is [-1, -1, ...].
    • The ! is a compile-time promise. The non-null assertion changes nothing in the compiled JavaScript and checks nothing at run time. Here the promise is true, since queue.length > 0 was just tested.
    • === against -1. The strict comparison is the idiomatic way to test for the sentinel.
    • The graph is read in the listed direction. The loop that builds graph pushes only edge[1] onto the list of edge[0], so a move from a vertex is possible only along an edge whose first number is that vertex. For the edge lists in this lesson, which name the nearer vertex first, that gives the right distances. For input where an edge may be written in either order, also push edge[0] onto graph[edge[1]]. On n = 3 and edges = [[1,0],[1,2]], the code as written returns [0, -1, -1], while two-way edges would give [0, 1, 2].
    • shift and performance. Removing from the front of an array has to move the remaining items in principle. Engines optimise this well for the sizes in this lesson (up to 1,000 vertices), but for very large queues an index that walks along the array does the job without removing anything.

    Complexity

    Let V be the number of vertices and E the number of edges.

    Time: O(V + E). Building the list takes O(V + E). Each vertex enters the queue at most once, thanks to the -1 check, and each vertex's neighbour list is scanned once, so every edge is looked at once.

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

    Edge cases and common mistakes

    • Unreachable vertices. With n = 4 and edges = [[0,1],[2,3]], the answer is [0, 1, -1, -1]: the search never leaves the component of vertex 0.
    • Cycles. A triangle [[0,1],[1,2],[2,0]] gives [0, 1, 2]. The reverse edge back to 0 is ignored because minDist[0] is already 0, not -1.
    • Shortcuts. With n = 4 and edges = [[0,1],[1,2],[2,3],[0,3]], vertex 3 is at distance 1 through the direct edge, even though the long route is listed earlier. The result is [0, 1, 2, 1].
    • Using the back of the queue. Replacing shift() with pop() turns the queue into a stack and breaks the ring-by-ring order, so distances can come out too large.
    • Marking a vertex when it is dequeued instead of when it is enqueued. The same vertex could be added several times before it gets processed, and the work grows.
    • Forgetting to set the source. If minDist[0] stayed -1, the search would treat vertex 0 as unvisited and could enqueue it 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],[2,0]] gives [0, 1, 2].
    • n = 4, edges = [[0,1],[1,2],[2,3],[0,3]] gives [0, 1, 2, 1].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free