Breadth First Search (Shortest Reach)

Compute shortest distances from a start node in an undirected graph with uniform edge weight using BFS.

Language Selection

Choose your preferred programming language

Showing: Python

Breadth First Search (Shortest Reach)

This is the canonical “BFS shortest path in an unweighted graph” interview problem, popularized by HackerRank as “Breadth First Search: Shortest Reach”.

Problem Statement

You are given multiple queries. For each query, you are given an undirected graph with:

Nodes labeled from 1 to n
m undirected edges
A starting node s
Each edge has a uniform weight of 6

For each query, compute the shortest distance from s to every other node.

If a node is unreachable from s, its distance is -1.
Output distances in increasing node label order, excluding the start node s.

Example 1

Input (single query shown conceptually):

n = 4, edges = (1–2), (1–3)
s = 1

Shortest distances from 1:

to 2: 6 (1 edge)
to 3: 6 (1 edge)
to 4: -1 (unreachable)

Output:

6 6 -1

Example 2 (Disconnected graph)

n = 3, m = 0 (no edges)
s = 2

Distances:

to 1: -1
to 3: -1

Output:

-1 -1

Example 3 (Single node)

n = 1, s = 1

There are no other nodes to output.

Output:

(Empty line)

Intuition — what insight unlocks the solution?

Because all edges have the same weight (6), the “shortest total weight path” is the same as the path with the fewest edges.

BFS explores the graph level by level:

Level 0: start node
Level 1: nodes 1 edge away
Level 2: nodes 2 edges away

So the first time BFS reaches a node, it has found the minimum number of edges from the start. Multiply that edge-count by 6 (or add 6 per step) to get the required distance.

This is the standard pattern: Single-source shortest path in an unweighted graph → BFS + queue.

Approach

Brute Force (what not to do)

Run a BFS separately for every destination node t

For each node, do BFS from s until you find t.
Time: O(V + E) per node → O(V·(V+E)) overall.

Dijkstra’s algorithm

Correct, but unnecessary overhead because all edges have equal weight.
Time: typically O((V+E) log V) with a heap.

Optimal Approach (BFS once)

For each query:

Build an adjacency list for the undirected graph.
Create a distance array dist[1..n] initialized to -1.
Set dist[s] = 0 and push s into a queue.
While the queue is not empty:
- Pop node u.
- For each neighbor v of u:
  - If dist[v] == -1 (unvisited):
    - Set dist[v] = dist[u] + 6
    - Push v
Output dist[i] for all nodes i != s in increasing order.

Why this works

BFS guarantees that nodes are visited in non-decreasing number of edges from s.
Because each edge contributes the same cost (6), the first time you visit a node is the cheapest path.

Solution

Below are reference implementations for the core function “compute distances from s”. (Input parsing differs across platforms; the algorithm is the same.)

Python:

from collections import deque
from typing import List, Tuple


def bfs_shortest_reach(n: int, edges: List[Tuple[int, int]], s: int) -> List[int]:
    """Returns distances from s to all nodes 1..n (1-indexed), excluding s in output order."""
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    dist = [-1] * (n + 1)
    dist[s] = 0

    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:  # not visited
                dist[v] = dist[u] + 6
                q.append(v)

    # Output excludes s
    return [dist[i] for i in range(1, n + 1) if i != s]

Java:

import java.util.*;

public class Solution {
    public static List<Integer> bfsShortestReach(int n, int[][] edges, int s) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        dist[s] = 0;

        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(s);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 6;
                    q.add(v);
                }
            }
        }

        List<Integer> out = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i == s) continue;
            out.add(dist[i]);
        }
        return out;
    }
}

Go:

package main

import "container/list"

type Edge struct{ U, V int }

func bfsShortestReach(n int, edges []Edge, s int) []int {
	adj := make([][]int, n+1)
	for _, e := range edges {
		adj[e.U] = append(adj[e.U], e.V)
		adj[e.V] = append(adj[e.V], e.U)
	}

	dist := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = -1
	}
	dist[s] = 0

	q := list.New()
	q.PushBack(s)

	for q.Len() > 0 {
		front := q.Front()
		u := front.Value.(int)
		q.Remove(front)

		for _, v := range adj[u] {
			if dist[v] == -1 {
				dist[v] = dist[u] + 6
				q.PushBack(v)
			}
		}
	}

	out := make([]int, 0, n-1)
	for i := 1; i <= n; i++ {
		if i == s {
			continue
		}
		out = append(out, dist[i])
	}
	return out
}

JavaScript:

function bfsShortestReach(n, edges, s) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }

  const dist = new Array(n + 1).fill(-1);
  dist[s] = 0;

  // Simple queue with head index for O(1) amortized pops
  const queue = [s];
  let head = 0;

  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 6;
        queue.push(v);
      }
    }
  }

  const out = [];
  for (let i = 1; i <= n; i++) {
    if (i === s) continue;
    out.push(dist[i]);
  }
  return out;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public static List<int> BfsShortestReach(int n, List<(int u, int v)> edges, int s) {
        var adj = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) adj[i] = new List<int>();

        foreach (var (u, v) in edges) {
            adj[u].Add(v);
            adj[v].Add(u);
        }

        var dist = new int[n + 1];
        Array.Fill(dist, -1);
        dist[s] = 0;

        var q = new Queue<int>();
        q.Enqueue(s);

        while (q.Count > 0) {
            int u = q.Dequeue();
            foreach (int v in adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 6;
                    q.Enqueue(v);
                }
            }
        }

        var output = new List<int>(n - 1);
        for (int i = 1; i <= n; i++) {
            if (i == s) continue;
            output.Add(dist[i]);
        }
        return output;
    }
}

Complexity Analysis

Let V = n (vertices) and E = m (edges).

Time: O(V + E)
- Building the adjacency list processes each edge twice (undirected): O(E)
- BFS visits each vertex at most once and scans each adjacency list once: total neighbor scans sum to O(E)
- Therefore overall O(V + E).
Space: O(V + E)
- Adjacency list stores all edges: O(V + E)
- Distance array and queue store up to V nodes: O(V)
- Total O(V + E).

Common Mistakes

Using DFS and expecting shortest paths
- DFS does not guarantee the first time you reach a node is the shortest path.
Forgetting the edge weight is 6
- Distances must increase by +6 per edge, not +1.
Marking visited too late
- Marking when dequeued (instead of when enqueued) can cause the same node to be enqueued many times.
Printing the start node’s distance
- Output must exclude node s.
Indexing bugs (1-based labels)
- Nodes are labeled 1..n; be careful if your language uses 0-based arrays.
Not resetting state per query
- Each query needs a fresh adjacency list, queue, and distance array.

Return the actual shortest path (store parent[v] = u when first visiting)
Multi-source BFS (start from multiple sources simultaneously)
Grid shortest path (walls/obstacles, 4-direction movement)
Bidirectional BFS (shortest path between two endpoints)
LeetCode staples:
- 102 — Binary Tree Level Order Traversal
- 994 — Rotting Oranges

Language Selection

Breadth First Search (Shortest Reach)

Problem Statement

Example 1

Example 2 (Disconnected graph)

Example 3 (Single node)

Intuition — what insight unlocks the solution?

Approach

Brute Force (what not to do)

Optimal Approach (BFS once)

Why this works

Solution

Complexity Analysis

Common Mistakes

Related / Follow-up Problems

Share this