DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Breadth First Search (BFS)

What Is BFS on a Graph?

BFS explores a graph level by level — first all neighbours of the start vertex, then their unvisited neighbours, and so on. It uses a queue (FIFO) to process vertices in the order they are discovered.

Reference graph (undirected):

     0 ─── 1 ─── 3
     │     │
     2 ─── 4 ─── 5

BFS from vertex 0:

Level 0: [0]           Enqueue 0, mark visited
Level 1: [1, 2]        Process 0 → enqueue unvisited neighbours 1, 2
Level 2: [3, 4]        Process 1 → enqueue 3 (2 already visited? no)
                       Process 2 → enqueue 4
Level 3: [5]           Process 3 → no new
                       Process 4 → enqueue 5

BFS order: 0, 1, 2, 3, 4, 5

Distances from 0:
  d[0]=0, d[1]=1, d[2]=1, d[3]=2, d[4]=2, d[5]=3

The first time BFS reaches a vertex = shortest path (in edge count).

Why BFS Gives Shortest Paths

KEY PROPERTY: BFS processes all distance-d vertices BEFORE
              any distance-(d+1) vertex is dequeued.

Proof sketch:
  - Start: only vertex s at distance 0 is in the queue.
  - Processing s: enqueue all its neighbours at distance 1.
  - FIFO: all distance-1 vertices are dequeued before any
          distance-2 vertex (which is enqueued by distance-1 vertices).
  - By induction: distance-k vertices are fully processed before
                  any distance-(k+1) vertex is dequeued.
  - Therefore: first time vertex v is dequeued = shortest path to v.

If a vertex v is reachable via a shorter path,
that shorter path would have been discovered earlier (fewer levels)
and v would already be marked visited.
Any later rediscovery via a longer path is rejected.

This guarantee ONLY holds for unweighted graphs (all edges = cost 1).
For weighted graphs: use Dijkstra's algorithm.

Core BFS Implementation

Java

Try it out

import java.util.*;

public class GraphBFS {

    // BFS traversal — returns vertices in BFS order
    public static List<Integer> bfs(List<List<Integer>> adj, int start, int V) {
        List<Integer>  order   = new ArrayList<>();
        boolean[]      visited = new boolean[V];
        Queue<Integer> queue   = new ArrayDeque<>();

        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int u = queue.poll();     // Dequeue front vertex
            order.add(u);

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;     // Mark BEFORE enqueuing
                    queue.offer(v);
                }
            }
        }

        return order;
    }

    // BFS shortest path — returns distances from start
    public static int[] shortestPath(List<List<Integer>> adj, int start, int V) {
        int[]          dist    = new int[V];
        boolean[]      visited = new boolean[V];
        Queue<Integer> queue   = new ArrayDeque<>();

        Arrays.fill(dist, -1);     // -1 = unreachable
        dist[start]    = 0;
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v]    = dist[u] + 1;   // One more edge from u
                    queue.offer(v);
                }
            }
        }

        return dist;
    }

    // BFS shortest path with parent tracking — reconstruct actual path
    public static List<Integer> shortestPathRoute(
            List<List<Integer>> adj, int start, int end, int V) {
        int[]          parent  = new int[V];
        boolean[]      visited = new boolean[V];
        Queue<Integer> queue   = new ArrayDeque<>();

        Arrays.fill(parent, -1);
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u == end) break;

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v]  = u;
                    queue.offer(v);
                }
            }
        }

        // Reconstruct path from end to start via parent array
        if (!visited[end]) return Collections.emptyList();   // No path

        List<Integer> path = new ArrayList<>();
        for (int v = end; v != -1; v = parent[v]) {
            path.add(0, v);   // Prepend to get start→end order
        }
        return path;
    }

    public static void main(String[] args) {
        // Graph: 0─1─3, 0─2─4─5, 1─4
        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{0,2},{1,3},{1,4},{2,4},{4,5}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]);
        }

        System.out.println("BFS order from 0: " + bfs(adj, 0, V));
        // [0, 1, 2, 3, 4, 5]

        int[] dist = shortestPath(adj, 0, V);
        System.out.println("Distances from 0: " + Arrays.toString(dist));
        // [0, 1, 1, 2, 2, 3]

        List<Integer> path = shortestPathRoute(adj, 0, 5, V);
        System.out.println("Path 0→5: " + path);
        // [0, 2, 4, 5] or [0, 1, 4, 5]
    }
}

Output:
BFS order from 0: [0, 1, 2, 3, 4, 5]
Distances from 0: [0, 1, 1, 2, 2, 3]
Path 0→5: [0, 2, 4, 5]

Dry Run: BFS Shortest Path

Graph:
     0 ─── 1 ─── 3
     │     │
     2 ─── 4 ─── 5

BFS from 0:

Initial: queue=[0], visited={0}, dist=[0,-1,-1,-1,-1,-1]

Step 1: Dequeue 0
  Neighbours: 1 (unvisited → enqueue), 2 (unvisited → enqueue)
  queue=[1, 2], dist=[0,1,1,-1,-1,-1]

Step 2: Dequeue 1
  Neighbours: 0 (visited), 3 (unvisited → enqueue), 4 (unvisited → enqueue)
  queue=[2, 3, 4], dist=[0,1,1,2,2,-1]

Step 3: Dequeue 2
  Neighbours: 0 (visited), 4 (already in queue/visited → skip)
  queue=[3, 4], dist unchanged

Step 4: Dequeue 3
  Neighbours: 1 (visited) → nothing new
  queue=[4]

Step 5: Dequeue 4
  Neighbours: 1 (visited), 2 (visited), 5 (unvisited → enqueue)
  queue=[5], dist=[0,1,1,2,2,3]

Step 6: Dequeue 5
  Neighbours: 4 (visited) → nothing new
  queue=[]

Final distances: [0, 1, 1, 2, 2, 3]
All vertices visited — graph is connected ✓

Application 1: Connected Components

Run BFS from each unvisited vertex. Each BFS call discovers one complete connected component.

Disconnected graph:
  Component 1: 0─1─2
  Component 2: 3─4
  Component 3: 5 (isolated)

Outer loop:
  vertex 0: not visited → BFS → discovers {0,1,2} → component 1
  vertex 1: already visited → skip
  vertex 2: already visited → skip
  vertex 3: not visited → BFS → discovers {3,4} → component 2
  vertex 4: already visited → skip
  vertex 5: not visited → BFS → discovers {5} → component 3

Total components: 3

Java

Try it out

import java.util.*;

public class ConnectedComponents {

    public static int countComponents(List<List<Integer>> adj, int V) {
        boolean[] visited  = new boolean[V];
        int       count    = 0;

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                bfsComponent(adj, start, visited);  // Explore entire component
                count++;
            }
        }
        return count;
    }

    // BFS that labels all vertices in one component
    public static List<Integer> getComponents(List<List<Integer>> adj, int V) {
        int[]   component = new int[V];
        boolean[] visited = new boolean[V];
        Arrays.fill(component, -1);
        int compId = 0;

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                Queue<Integer> queue = new ArrayDeque<>();
                queue.offer(start);
                visited[start]   = true;
                component[start] = compId;

                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    for (int v : adj.get(u)) {
                        if (!visited[v]) {
                            visited[v]   = true;
                            component[v] = compId;
                            queue.offer(v);
                        }
                    }
                }
                compId++;
            }
        }
        return Arrays.asList(Arrays.stream(component).boxed().toArray(Integer[]::new));
    }

    private static void bfsComponent(List<List<Integer>> adj, int start, boolean[] visited) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) { visited[v] = true; queue.offer(v); }
            }
        }
    }

    public static void main(String[] args) {
        // Disconnected: 0-1-2, 3-4, 5
        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(1); adj.get(1).add(0);
        adj.get(1).add(2); adj.get(2).add(1);
        adj.get(3).add(4); adj.get(4).add(3);
        // 5 is isolated

        System.out.println("Components: " + countComponents(adj, V));   // 3
        System.out.println("Labels:     " + getComponents(adj, V));      // [0,0,0,1,1,2]
    }
}

Output:
Components: 3
Labels:     [0, 0, 0, 1, 1, 2]

Application 2: Multi-Source BFS

Start BFS with multiple sources simultaneously. Finds minimum distance from the nearest source to every vertex.

PROBLEM: "01 Matrix" — distance from each cell to nearest 0.

Matrix:        Distances to nearest 0:

0 0 0          0 0 0
0 1 0    →     0 1 0
1 1 1          1 2 1

ALGORITHM:
  Enqueue ALL zeros at distance 0.
  BFS from all zeros simultaneously.
  Each cell gets the distance from its nearest zero.

vs SINGLE-SOURCE BFS from each zero separately:
  Would be O(K × V) where K = number of zeros.
  Multi-source BFS: O(V + E) — same as single BFS.

Java

Try it out

import java.util.*;

public class MultiSourceBFS {

    // 01 Matrix: distance to nearest 0
    public static int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue  = new ArrayDeque<>();

        // Enqueue ALL zeros at distance 0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j]    = 0;
                    visited[i][j] = true;
                    queue.offer(new int[]{i, j});
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1];

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    dist[nr][nc]    = dist[r][c] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] result = updateMatrix(mat);
        for (int[] row : result) System.out.println(Arrays.toString(row));
        // [0, 0, 0]
        // [0, 1, 0]
        // [1, 2, 1]
    }
}

Output:
[0, 0, 0]
[0, 1, 0]
[1, 2, 1]

Application 3: 0-1 BFS

For graphs where edge weights are only 0 or 1, use a deque instead of a queue. Weight-0 edges go to the front; weight-1 edges go to the back. Achieves O(V + E) instead of O((V+E) log V) for Dijkstra's.

KEY IDEA:
  Weight-0 edge: neighbour at SAME distance → front of deque (process next)
  Weight-1 edge: neighbour at distance+1 → back of deque (process later)

GRAPH EXAMPLE:
  0 ──0── 1 ──1── 2
  │               │
  └──1── 3 ──0── ┘

From 0:
  0 is at dist 0
  1 (via weight-0 edge): dist = 0 → FRONT
  3 (via weight-1 edge): dist = 1 → BACK

Deque after processing 0: FRONT [1, 3] BACK
  Process 1 (dist=0):
    2 (weight-1): dist=1 → BACK

Deque: FRONT [3, 2] BACK
  Process 3 (dist=1):
    2 (weight-0): dist=1 → FRONT (better than current dist[2]=1? same, skip)

Final distances: [0, 0, 1, 1]

Java

Try it out

import java.util.*;

public class ZeroOneBFS {

    // 0-1 BFS: edge weights are 0 or 1 only
    public static int[] zeroOneBFS(List<List<int[]>> adj, int start, int V) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        Deque<Integer> deque = new ArrayDeque<>();
        deque.addFirst(start);

        while (!deque.isEmpty()) {
            int u = deque.pollFirst();

            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];

                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;

                    if (w == 0) deque.addFirst(v);   // Same level → FRONT
                    else        deque.addLast(v);    // Next level → BACK
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        // Graph with 0/1 weights: 0─0─1─1─2, 0─1─3─0─2
        int V = 4;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(new int[]{1, 0}); adj.get(1).add(new int[]{0, 0});
        adj.get(1).add(new int[]{2, 1}); adj.get(2).add(new int[]{1, 1});
        adj.get(0).add(new int[]{3, 1}); adj.get(3).add(new int[]{0, 1});
        adj.get(3).add(new int[]{2, 0}); adj.get(2).add(new int[]{3, 0});

        System.out.println(Arrays.toString(zeroOneBFS(adj, 0, V)));
        // [0, 0, 1, 1]
    }
}

Output:
[0, 0, 1, 1]

BFS Cycle Detection (Undirected)

In undirected BFS: if a neighbour of u is already visited
AND it is not u's direct parent → CYCLE exists.

     0 ─── 1
     │     │
     2 ─── 3    ← square has a cycle

BFS from 0:
  Process 0: enqueue 1, 2 (parent[1]=0, parent[2]=0)
  Process 1: enqueue 3 (parent[3]=1); 0 is visited — 0 is parent of 1 → OK
  Process 2: neighbour 3 is already visited (via 1) and 3 ≠ parent[2]=0 → CYCLE!

Java

Try it out

public static boolean hasCycleBFS(List<List<Integer>> adj, int V) {
    boolean[] visited = new boolean[V];

    for (int start = 0; start < V; start++) {
        if (visited[start]) continue;

        Queue<int[]> queue = new ArrayDeque<>();  // [vertex, parent]
        queue.offer(new int[]{start, -1});
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] curr   = queue.poll();
            int   u      = curr[0];
            int   parent = curr[1];

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(new int[]{v, u});
                } else if (v != parent) {
                    return true;   // Back edge → cycle
                }
            }
        }
    }
    return false;
}

BFS Summary: Key Patterns

PATTERN                  TECHNIQUE                       COMPLEXITY
────────────────────────────────────────────────────────────────────
Single-source BFS        Queue + visited array           O(V + E)
Shortest path distance   dist[v] = dist[u] + 1          O(V + E)
Reconstruct path         parent[] array + backtrack      O(V + E)
Connected components     Outer loop + BFS per component  O(V + E)
Multi-source BFS         Pre-enqueue all sources         O(V + E)
0-1 BFS                  Deque: 0-weight→front, 1→back   O(V + E)
Cycle detection          Track parent in BFS pair        O(V + E)
Bipartite check          Alternate colors in BFS         O(V + E)
Level-by-level           levelSize = queue.size()        O(V + E)

Complexity Summary

Operation	Time	Space	Notes
BFS traversal	O(V + E)	O(V)	visited array + queue
Shortest path	O(V + E)	O(V)	dist array + queue
Path reconstruction	O(V + E)	O(V)	parent array + queue
Connected components	O(V + E)	O(V)	Same BFS, outer loop
Multi-source BFS	O(V + E)	O(V)	All sources at distance 0
0-1 BFS	O(V + E)	O(V)	Deque instead of queue
Cycle detection	O(V + E)	O(V)	Track parent per vertex

V = vertices, E = edges. Assumes adjacency list representation.

Common Mistakes

Marking visited AFTER dequeuing instead of BEFORE enqueuing. If you mark a vertex visited when you dequeue it (instead of when you enqueue it), the same vertex can be enqueued multiple times — once from each neighbour that discovers it before it's dequeued. This causes O(E) redundant work in the worst case and incorrect distance calculations. Always mark visited immediately when enqueuing.

Forgetting the outer loop for disconnected graphs. BFS from vertex 0 only explores vertex 0's connected component. If the graph is disconnected, unvisited vertices are never reached. The outer loop for each unvisited vertex: start BFS is required to handle all components.

Using DFS instead of BFS for shortest path. DFS finds A path but not necessarily the shortest. BFS guarantees shortest path in unweighted graphs because it processes vertices level by level. Using DFS and hoping to find the minimum is incorrect — DFS may find a long path before the short one.

Using BFS for weighted shortest paths. BFS gives shortest path by edge count (unweighted). For weighted graphs, use Dijkstra's (positive weights) or Bellman-Ford (any weights). BFS on a weighted graph finds the path with fewest edges, not minimum total weight.

Multi-source BFS: running separate BFS for each source. Running K separate BFS calls each taking O(V + E) gives O(K × (V + E)) total — much worse than multi-source BFS O(V + E). Always use the single multi-source BFS by pre-loading all sources into the queue at distance 0.

Interview Questions

Q: Why does BFS guarantee shortest path but DFS does not?

BFS processes vertices level by level — all vertices at distance d are fully processed before any vertex at distance d+1 is dequeued. This is guaranteed by the FIFO property of the queue. The first time BFS reaches a vertex, it's via the shortest path (fewest edges). DFS follows one path as deep as possible, potentially finding a long path to a vertex before discovering a shorter one. DFS gives A path but not the SHORTEST path.

Q: What is the time complexity of BFS and why?

O(V + E) with adjacency list. Each vertex is enqueued and dequeued exactly once — O(V) total dequeue operations. Each edge is examined exactly once (from the source vertex's adjacency list when that vertex is dequeued) — O(E) total edge examinations. With adjacency matrix, BFS is O(V²) — each dequeue requires scanning V entries to find neighbours.

Q: How does multi-source BFS differ from running BFS from each source separately?

Multi-source BFS adds ALL sources to the queue at distance 0 before the main loop starts. This is equivalent to adding a virtual super-source connected to all real sources with weight-0 edges. The entire BFS runs once — O(V + E). Running separate BFS from each of K sources is O(K × (V + E)) — much slower. Multi-source BFS gives the minimum distance to the nearest source from every vertex in one pass.

Summary

BFS explores a graph level by level using a queue (FIFO). Vertices are marked visited when enqueued (not when dequeued) to prevent duplicate processing.

Three foundational results from BFS:

›Traversal order — all vertices reachable from source, in order of increasing distance
›Shortest path — dist[v] = dist[u] + 1 when v is first discovered; guaranteed to be minimum edge count
›Path reconstruction — track parent[v] = u during BFS, then backtrack from destination to source

Four key BFS patterns:

Pattern	Change from standard BFS
Connected components	Outer loop over all vertices; count BFS restarts
Multi-source BFS	Pre-load all sources at distance 0 before the loop
0-1 BFS	Replace queue with deque; weight-0 → front, weight-1 → back
Cycle detection	Track parent; visited neighbour ≠ parent → cycle

When BFS is the right tool:

›Shortest path in unweighted graphs — guaranteed minimum edges
›Level-by-level processing — all distance-k nodes before distance-(k+1)
›Multi-source minimum distance — nearest exit, rotten oranges, 01 matrix
›Connected component counting

In the next topic you will explore Graph DFS — depth-first traversal, cycle detection, topological sort, and strongly connected components.

Suggested Quiz

BFS uses a queue. Why does FIFO order guarantee shortest paths in an unweighted graph?

1/6

←

PreviousTypes of Graphs

NextDepth First Search (DFS)

→