DSA · Lesson 11 of 17

Graphs: BFS & DFS

⏱ 15 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 5 practice problems

Model the problem as nodes and edges, then explore with breadth-first or depth-first search. This covers grids, islands, connectivity and shortest paths in unweighted graphs.

Modelling

A graph is a set of nodes connected by edges, which can be directed or undirected, weighted or unweighted. Interview graphs are often hidden: a grid (each cell is a node, neighbours are edges), word ladders (words that differ by one letter), states of a puzzle, course prerequisites.

Store a graph as an adjacency list: adj[u] = [v1, v2, …]. It uses O(V + E) memory, which is better than a V × V matrix for sparse graphs.

BFS or DFS?

	BFS (queue)	DFS (stack / recursion)
Order	ring by ring from the start	as deep as possible, then backtrack
Shortest path in unweighted graphs	✅ yes	❌ no
Memory	O(width)	O(depth)
Natural for	minimum steps, multi-source spreading (rotting oranges), level problems	connectivity, flood fill, cycle detection, topological order, backtracking

Both are O(V + E). On an m × n grid that is O(m·n).

The template you will reuse forever

Build the adjacency list (or use the grid directions).
Keep a visited set, and mark nodes when you enqueue them (not when you dequeue), so nothing is added twice.
Loop over every node if the graph may be disconnected, counting components as you go.

Multi-source BFS: push all sources at once (every rotten orange, every gate) and expand layer by layer; the layer number is the distance to the nearest source.

Code template

from collections import deque

def bfs(adj, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:              # mark when enqueuing
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def count_components(n, adj):
    seen, comps = set(), 0
    def dfs(u):
        stack = [u]; seen.add(u)
        while stack:
            x = stack.pop()
            for v in adj[x]:
                if v not in seen:
                    seen.add(v); stack.append(v)
    for u in range(n):
        if u not in seen:
            comps += 1; dfs(u)
    return comps

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))   # grid neighbours

Map<Integer, Integer> bfs(List<List<Integer>> adj, int start) {
    Map<Integer, Integer> dist = new HashMap<>(Map.of(start, 0));
    ArrayDeque<Integer> q = new ArrayDeque<>(List.of(start));
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u))
            if (!dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); q.add(v); }
    }
    return dist;
}

int countComponents(int n, List<List<Integer>> adj) {
    boolean[] seen = new boolean[n];
    int comps = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        comps++;
        Deque<Integer> stack = new ArrayDeque<>(List.of(s)); seen[s] = true;
        while (!stack.isEmpty()) for (int v : adj.get(stack.pop())) if (!seen[v]) { seen[v] = true; stack.push(v); }
    }
    return comps;
}

int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};   // grid neighbours

vector<int> bfs(const vector<vector<int>>& adj, int start) {
    vector<int> dist(adj.size(), -1);
    queue<int> q; q.push(start); dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    return dist;
}

int countComponents(int n, const vector<vector<int>>& adj) {
    vector<bool> seen(n, false);
    int comps = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        comps++;
        vector<int> st{s}; seen[s] = true;
        while (!st.empty()) { int u = st.back(); st.pop_back(); for (int v : adj[u]) if (!seen[v]) { seen[v] = true; st.push_back(v); } }
    }
    return comps;
}

int DR[] = {1, -1, 0, 0}, DC[] = {0, 0, 1, -1};   // grid neighbours

function bfs(adj, start) {
  const dist = new Map([[start, 0]]), q = [start];
  for (let h = 0; h < q.length; h++) {
    const u = q[h];
    for (const v of adj[u]) if (!dist.has(v)) { dist.set(v, dist.get(u) + 1); q.push(v); }
  }
  return dist;
}

function countComponents(n, adj) {
  const seen = new Array(n).fill(false);
  let comps = 0;
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    comps++;
    const stack = [s]; seen[s] = true;
    while (stack.length) for (const v of adj[stack.pop()]) if (!seen[v]) { seen[v] = true; stack.push(v); }
  }
  return comps;
}

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // grid neighbours

Practise this pattern (5 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
54	Flood Fill	Easy
55	Find if Path Exists in Graph	Easy
56	Number of Islands	Medium
57	Max Area of Island	Medium
58	Rotting Oranges	Medium

Common mistakes

Marking visited too late (on dequeue) in BFS, which adds duplicates and can blow up the queue.
Forgetting disconnected components: loop over every node.
Recursion depth on big grids (10⁶ cells): use an iterative stack or BFS.

Check yourself: why does BFS give shortest paths only in unweighted graphs?

BFS counts edges. With weights, a path with more edges can be cheaper, so you need Dijkstra (non-negative weights) or Bellman–Ford.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar