Skip to main content
Code ScholarsCodeScholars

Graphs and Network Algorithms · Graph Traversal

Breadth-First Search

Breadth-first search explores level by level using a queue and naturally finds shortest paths in unweighted graphs.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

Students learn BFS as the graph version of systematic outward exploration.

Guided Lesson Notes

Understanding Breadth-First Search

Breadth-First Search focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Breadth-first search explores level by level using a queue and naturally finds shortest paths in unweighted graphs.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Breadth-First Search when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Breadth-First Search

ABCDE

Key Ideas

  • Queue-driven traversal
  • Distance by layers
  • Parent pointers for path reconstruction

Practice Prompts

  • Trace BFS levels from a start vertex.
  • Recover the shortest unweighted path using parent links.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Breadth-First Search

Trace a small input, focusing on queue-driven traversal.

  1. 1Write a small input where Breadth-First Search is clearly useful.
  2. 2Label the part of the input related to Queue-driven traversal.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Adjacency-list traversalO(V + E)DFS and BFS visit vertices and inspect edges.
Adjacency matrix storageO(V^2)A matrix reserves space for every possible pair.
Weighted optimizationVariesMST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Breadth-First Search interview problem: Number of Islands

Interview medium

Problem

Given a grid of 0s and 1s, count how many connected islands of 1s exist using four-direction adjacency.

Input

The first line contains n and m. The next n lines contain m values, each 0 or 1.

Output

Print the island count.

Sample Input

4 5
1 1 0 0 0
1 0 0 1 1
0 0 0 0 0
1 0 1 1 0

Sample Output

4

Why the sample works

There are four separate groups of land cells.

Approach

  1. 1Scan every cell in the grid.
  2. 2When an unseen land cell is found, start a DFS or BFS and mark its entire island.
  3. 3Increase the island count once per new traversal.
  4. 4Water cells and already visited land cells are skipped.

O(nm) time and O(nm) extra space in the worst case.

Java Solution

import java.util.*;

public class Main {
  static int n;
  static int m;
  static int[][] grid;
  static boolean[][] seen;
  static int[] dr = {1, -1, 0, 0};
  static int[] dc = {0, 0, 1, -1};

  static void dfs(int r, int c) {
    seen[r][c] = true;
    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d];
      int nc = c + dc[d];
      if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
      if (grid[nr][nc] == 1 && !seen[nr][nc]) {
        dfs(nr, nc);
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    grid = new int[n][m];
    seen = new boolean[n][m];

    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) {
        grid[r][c] = sc.nextInt();
      }
    }

    int islands = 0;
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) {
        if (grid[r][c] == 1 && !seen[r][c]) {
          islands++;
          dfs(r, c);
        }
      }
    }

    System.out.println(islands);
  }
}

Python Solution

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
seen = [[False] * m for _ in range(n)]

def dfs(r, c):
    seen[r][c] = True
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < m:
            if grid[nr][nc] == 1 and not seen[nr][nc]:
                dfs(nr, nc)

islands = 0
for r in range(n):
    for c in range(m):
        if grid[r][c] == 1 and not seen[r][c]:
            islands += 1
            dfs(r, c)

print(islands)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Breadth-First Search: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler