Lesson 34Intermediate55 minAssessment-backed

Breadth-First Search

Explore graphs by layers for shortest unweighted paths, nearest matches, and level-based processing.

What you will be able to do

Explain BFS layer order and why it gives shortest paths in unweighted graphs.

Implement BFS with a queue and visited set.

Use BFS for nearest resource, connection degree, grid distance, and dependency waves.

Track distance and parent information when the product needs a path.

Avoid queue and visited-set mistakes that cause repeated work.

Breadth-first search explores everything one step away before two steps away, then three. That layer guarantee is why BFS is the default for shortest paths when every edge has equal cost.

The Layer Invariant

When a node is first removed from the BFS queue, it has been reached using the fewest number of edges from the start. This is true only when every edge has equal weight or cost.

BFS explores graph by distance layers — BFS turns reachability into expanding rings of distance.

Scenario: Nearest Healthy Service

A platform graph connects services by call relationships. During an incident, you need the nearest healthy fallback service from a failing service. If each hop has equal operational cost, BFS finds the nearest reachable candidate first.

Need	BFS field	Why
Shortest hop count	distance map	First visit gives minimum edges.
Recover route	parent map	Backtrack from target to start.
Avoid repeats	visited set	Graphs can cycle.
Level processing	queue size	Each wave is one distance.

BFS queue frontier and visited set — Queue plus visited set is the operating system of BFS.

Same Pattern in Java, Python, and JavaScript

This BFS returns the shortest number of edges from start to target, or -1 when target is unreachable.

import java.util.*;

class BfsDistance {
    static int shortest(Map<String, List<String>> graph, String start, String target) {
        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int distance = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                String node = queue.poll();
                if (node.equals(target)) return distance;
                for (String next : graph.getOrDefault(node, List.of())) {
                    if (visited.add(next)) queue.offer(next);
                }
            }
            distance++;
        }
        return -1;
    }
}

Assessment trap

BFS is not automatically shortest when edges have different weights. Weighted shortest path requires a different cost model.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return shortest hop count between two graph nodes.
Given a grid of fresh and rotten oranges, return minutes until all fresh oranges rot.
Return one shortest unweighted path from start to target.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Nearest support escalation	DFS and return the first match found.	Use BFS when nearest by relationship hops matters.	First BFS match is shortest only for equal edge cost.
Word transformation	Try arbitrary replacements recursively.	Use BFS over valid one-letter transformations.	Visited prevents exponential revisits.
Incident blast radius waves	Process dependencies in random order.	Use BFS levels to show one-hop, two-hop, three-hop impact.	Level order improves explainability during incidents.

Solved modelInterview Question Solutions

Question 1: Shortest Path in Unweighted Graph

Return shortest hop count between two graph nodes. Use BFS because each queue layer is one more edge from the start. The first target visit is optimal.

import java.util.*;

class BfsDistance {
    static int shortest(Map<String, List<String>> graph, String start, String target) {
        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int distance = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                String node = queue.poll();
                if (node.equals(target)) return distance;
                for (String next : graph.getOrDefault(node, List.of())) {
                    if (visited.add(next)) queue.offer(next);
                }
            }
            distance++;
        }
        return -1;
    }
}

Question 2: Rotting Oranges

Given a grid of fresh and rotten oranges, return minutes until all fresh oranges rot. Use multi-source BFS: enqueue all initially rotten cells, then process minute by minute.

import java.util.*;
class Rotten { static int minutes(int[][] grid) { int fresh = 0, minutes = 0; Queue<int[]> q = new ArrayDeque<>(); for (int r=0;r<grid.length;r++) for (int c=0;c<grid[0].length;c++) { if (grid[r][c]==2) q.offer(new int[]{r,c}); if (grid[r][c]==1) fresh++; } int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}}; while (fresh>0 && !q.isEmpty()) { for (int size=q.size(); size>0; size--) { int[] cell=q.poll(); for (int[] d:dirs) { int r=cell[0]+d[0], c=cell[1]+d[1]; if (r>=0&&c>=0&&r<grid.length&&c<grid[0].length&&grid[r][c]==1) { grid[r][c]=2; fresh--; q.offer(new int[]{r,c}); } } } minutes++; } return fresh==0 ? minutes : -1; } }

Question 3: Reconstruct Shortest Path

Return one shortest unweighted path from start to target. BFS with a parent map records how each node was first reached; backtrack from target after discovery.

import java.util.*;
class BfsPath { static List<String> path(Map<String,List<String>> g, String s, String t) { Queue<String> q = new ArrayDeque<>(); Map<String,String> parent = new HashMap<>(); q.offer(s); parent.put(s, null); while(!q.isEmpty()) { String node=q.poll(); if (node.equals(t)) break; for(String next:g.getOrDefault(node,List.of())) if(!parent.containsKey(next)) { parent.put(next,node); q.offer(next); } } if(!parent.containsKey(t)) return List.of(); LinkedList<String> out = new LinkedList<>(); for(String cur=t; cur!=null; cur=parent.get(cur)) out.addFirst(cur); return out; } }

Solved modelWorked Interview Answer

Return the shortest number of edges between two nodes in an unweighted graph. BFS is correct because it visits nodes in increasing edge distance. The first time the target is reached, no shorter unweighted path remains undiscovered.

import java.util.*;

class BfsDistance {
    static int shortest(Map<String, List<String>> graph, String start, String target) {
        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int distance = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                String node = queue.poll();
                if (node.equals(target)) return distance;
                for (String next : graph.getOrDefault(node, List.of())) {
                    if (visited.add(next)) queue.offer(next);
                }
            }
            distance++;
        }
        return -1;
    }
}

Hands-on drillTry It Yourself

Practice task

Given a social graph, find the minimum number of introductions between two users. Trace the queue one level at a time.

Failure patternsCommon Mistakes to Avoid

Marking visited only after dequeue and enqueuing duplicates.
Using BFS for weighted shortest paths.
Forgetting distance tracking.
Using Array.shift repeatedly in JavaScript for huge queues.
Not handling unreachable targets.

Execution guardrailQuick-Start Checklist

Initialize queue with start.
Mark start visited.
Process level size when distance matters.
Mark neighbors visited before enqueue.
Return when target is first reached.
Return no-path value if queue empties.

Recall drillKnowledge Check

Question	Strong answer
Why does BFS give shortest unweighted path?	It visits nodes in increasing edge distance.
What memory does BFS use?	O(width/frontier) plus visited set.
When is BFS wrong for shortest path?	When edges have unequal weights.

VocabularyKey Terms

Term	Meaning
Queue	FIFO structure for frontier processing.
Frontier	Nodes discovered but not fully processed.
Level	All nodes at the same edge distance.
Visited set	Prevents repeats and cycles.

Next practiceFurther Reading

Practice shortest path in binary matrix, word ladder, and multi-source BFS.
Review queue implementation details.
Compare BFS with Dijkstra for weighted graphs.

Graph Modeling

Depth-First Search