λDSA Learning Hubpart of DSA Atlas

Graphs: BFS & DFS

Intermediate~4h · 8 lessons12 practice problems

Vertices, edges, adjacency lists — and the two traversals (BFS, DFS) that solve connected components, shortest unweighted paths, cycle detection, and topological sort.

0 of 8 lessons checked off

Introduction

What it is

  • A graph is a set of vertices connected by edges — the general structure of relationships. Directed or undirected, weighted or unweighted, cyclic or acyclic: four switches that classify every graph problem.
  • Trees are graphs with n − 1 edges and no cycles; linked lists are path graphs. Graphs are the superset where anything may connect to anything.

Why it matters

  • Most real systems are graphs: social networks, road maps, dependency builds, currency exchanges, state machines. Interviewers use graphs to test modelling — recognising that a word ladder or a grid of islands IS a graph is half the problem.
  • Two traversals carry the entire topic: BFS (by distance, via queue) and DFS (by depth, via stack/recursion). Nearly every classic — components, cycles, topological sort, bipartite check — is one of them plus bookkeeping.

How it works

  • Store adjacency lists: {node: [neighbours]} — O(V + E) space, instant neighbour iteration. (Adjacency matrices cost O(V²) and pay off only for dense graphs or O(1) edge tests.)
  • BFS: queue + mark-visited-on-enqueue → visits in distance order → shortest paths in unweighted graphs.
  • DFS: recursion (or explicit stack) → dives deep, backtracks → components, cycle detection, ordering.
  • Grids are graphs in disguise: cells are vertices, the 4 directions are edges. No adjacency structure needed — generate neighbours on the fly.

Where it's used

  • Package managers topologically sort dependency graphs; GPS runs shortest-path over road graphs; recommendation engines walk user-item graphs; compilers order build targets.

In interviews

  • Number of islands, clone graph, course schedule (cycle/toposort), rotting oranges (multi-source BFS), word ladder (implicit graph BFS), pacific-atlantic (multi-source DFS).
Analogy: A city map: intersections are vertices, streets are edges. BFS is the ripple of a stone dropped at your house — reaching everything 1 block away, then 2. DFS is a determined explorer with a ball of string, walking every street to its end before backtracking.

Interactive diagram

The queue enforces distance order: all 1-edge nodes, then 2, then 3. First arrival = shortest path.

ABCDEF
BFS from A

Breadth-first search explores in rings: all distance-1 nodes, then distance-2, and so on. A queue (FIFO) enforces that order.

queue
[A]

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Graph terminology and modelling

    Directed/undirected, weighted, cyclic; spotting implicit graphs.

    20 min
  2. Adjacency lists vs matrices

    O(V+E) vs O(V²); building from edge lists.

    20 min
  3. Breadth-first search

    Queue, visited-on-enqueue, distance layers, multi-source.

    30 min
  4. Depth-first search

    Recursive and iterative; pre/post times; backtracking.

    30 min
  5. Connected components & flood fill

    Loop over vertices, traverse from each unvisited one.

    20 min
  6. Cycle detection

    Undirected: parent tracking. Directed: the three-colour scheme.

    25 min
  7. Bipartite checking

    2-colouring by BFS; odd cycles are the only obstacle.

    15 min
  8. Topological sorting

    Kahn's indegree queue and DFS post-order; DAGs only.

    30 min

Operations

Breadth-first search

A queue explores by distance layers. Mark visited when ENQUEUING — the invariant that keeps every vertex in the queue at most once.

ABCDEF
BFS from A

Breadth-first search explores in rings: all distance-1 nodes, then distance-2, and so on. A queue (FIFO) enforces that order.

queue
[A]
from collections import dequedef bfs_distances(graph: dict[str, list[str]], start: str) -> dict[str, int]:    """Fewest-edge distance to every reachable node. O(V + E)."""    dist = {start: 0}    queue = deque([start])    while queue:        node = queue.popleft()        for neighbour in graph[node]:            if neighbour not in dist:      # visited check = distance recorded                dist[neighbour] = dist[node] + 1                queue.append(neighbour)    return dist
Time: O(V + E)Space: O(V)

Edge cases

  • Disconnected vertices simply never appear in dist — that's the reachability answer too.
  • Multi-source BFS: seed the queue with ALL sources at distance 0 (rotting oranges).
  • Path reconstruction: store parent[neighbour] = node and walk back.

Common mistakes

  • Marking visited at dequeue time — a vertex can be enqueued many times; on dense graphs that's exponential blowup.
  • Using list.pop(0) as the queue: O(V²).

Depth-first search

Dive along one path to exhaustion, backtrack, repeat. Recursion IS the stack; the iterative version makes it explicit.

ABCDEF
DFS from A

Depth-first search dives down one path as far as possible before backtracking. A stack (or recursion) remembers where to resume.

stack
[A]
def dfs_recursive(graph: dict[str, list[str]], start: str) -> list[str]:    """Visit order from start. O(V + E)."""    visited: set[str] = set()    order: list[str] = []    def visit(node: str) -> None:        visited.add(node)        order.append(node)        for neighbour in graph[node]:            if neighbour not in visited:                visit(neighbour)    visit(start)    return orderdef count_components(graph: dict[str, list[str]]) -> int:    """Connected components in an undirected graph."""    visited: set[str] = set()    components = 0    for node in graph:                    # restart DFS at every unseen node        if node not in visited:            components += 1            stack = [node]            while stack:                current = stack.pop()                if current in visited:                    continue                visited.add(current)                stack.extend(n for n in graph[current] if n not in visited)    return components
Time: O(V + E)Space: O(V)

Edge cases

  • Recursion depth can hit V (path graphs) — Python's limit says convert big-graph DFS to the explicit stack.
  • The components loop over ALL vertices is what catches disconnected pieces.
  • Iterative DFS may push a node twice; the visited check at pop time handles it.

Common mistakes

  • Forgetting the outer loop and reporting only the start's component.
  • 10⁵-node recursive DFS in Python — RecursionError in production, mention the iterative rewrite.

Cycle detection in a directed graph (three colours)

WHITE unvisited, GRAY in the current recursion path, BLACK finished. Meeting a GRAY node means the path loops back into itself — a cycle.

Cycle detection in a directed graph (three colours)
def has_cycle_directed(graph: dict[str, list[str]]) -> bool:    """Three-colour DFS. O(V + E)."""    WHITE, GRAY, BLACK = 0, 1, 2    colour = {node: WHITE for node in graph}    def dfs(node: str) -> bool:        colour[node] = GRAY                  # entered the current path        for neighbour in graph[node]:            if colour[neighbour] == GRAY:    # back edge → cycle                return True            if colour[neighbour] == WHITE and dfs(neighbour):                return True        colour[node] = BLACK                 # fully explored, safe forever        return False    return any(colour[n] == WHITE and dfs(n) for n in graph)
Time: O(V + E)Space: O(V)

Edge cases

  • A BLACK neighbour is NOT a cycle — it's a finished branch reached again (diamond shapes).
  • Self-loops: immediately GRAY → cycle.
  • Undirected graphs use a different test (an edge back to any visited non-parent) — don't mix them.

Common mistakes

  • Using a single visited set for directed cycles — flags diamonds as cycles (false positives).
  • Never resetting to BLACK, which makes everything look like a cycle.

Topological sort (Kahn's algorithm)

Repeatedly remove vertices with zero remaining prerequisites. If everything gets removed, that removal order IS a valid schedule; leftovers mean a cycle.

Topological sort (Kahn's algorithm)
from collections import dequedef topological_order(graph: dict[str, list[str]]) -> list[str] | None:    """Kahn's algorithm. Returns None if the graph has a cycle. O(V + E)."""    indegree = {node: 0 for node in graph}    for node in graph:        for neighbour in graph[node]:            indegree[neighbour] += 1    queue = deque(node for node, d in indegree.items() if d == 0)    order: list[str] = []    while queue:        node = queue.popleft()        order.append(node)        for neighbour in graph[node]:            indegree[neighbour] -= 1          # 'remove' the edge            if indegree[neighbour] == 0:      # prerequisites satisfied                queue.append(neighbour)    return order if len(order) == len(graph) else None
Time: O(V + E)Space: O(V)

Edge cases

  • len(order) < V ⇔ a cycle exists — Kahn's doubles as cycle detection (Course Schedule).
  • Multiple valid orders exist; a heap instead of a queue gives the lexicographically smallest.
  • Only DAGs (directed acyclic) can be topologically sorted — undirected graphs make no sense here.

Common mistakes

  • Building indegrees from the wrong edge direction — prerequisites arrows must point prerequisite → dependent.
  • Forgetting the final length check and returning a partial order on cyclic input.

Complexity analysis

OperationBestAverageWorstSpace
BFS / DFS traversalO(V + E)O(V + E)O(V + E)O(V)
Connected componentsO(V + E)O(V + E)O(V + E)O(V)
Cycle detectionO(V + E)O(V + E)O(V + E)O(V)
Topological sortO(V + E)O(V + E)O(V + E)O(V)
Adjacency matrix traversalO(V²)O(V²)O(V²)O(V²)

O(V + E) is the universal graph-traversal price: touch each vertex once and each edge once (twice undirected). The matrix row shows why sparse graphs use lists.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Number of Islands — grid BFS, the shape of half of all graph interviews
from collections import dequedef num_islands(grid: list[list[str]]) -> int:    """Count 4-connected regions of '1's. O(rows·cols) time and space."""    if not grid or not grid[0]:        return 0    rows, cols = len(grid), len(grid[0])    visited: set[tuple[int, int]] = set()    islands = 0    def bfs(sr: int, sc: int) -> None:        queue = deque([(sr, sc)])        visited.add((sr, sc))        while queue:            r, c = queue.popleft()            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):                nr, nc = r + dr, c + dc

What interviewers expect you to know

What interviewers expect you to know

  • BFS = queue = shortest unweighted paths; DFS = stack/recursion = components, cycles, orderings. Choosing correctly is the first grading point.
  • Visited-on-enqueue for BFS; three colours for directed cycles; parent-tracking for undirected cycles.
  • O(V + E) for everything on this page, and adjacency lists as the default representation.
  • Grid = implicit graph; word-ladder-style puzzles = implicit graph over states.

Modelling questions to rehearse

  • "Cells/islands/regions" → grid graph, flood fill components.
  • "Prerequisites/build order/compile" → directed graph, toposort (Kahn's), cycle = impossible.
  • "Minimum steps/moves from X to Y" → BFS over states, even when states are words or lock combinations.
  • "Can the network be split / are these two connected?" → components (or union-find, next topic).

How to talk through a graph problem

  • Declare the graph first: 'vertices are __, edges are __, directed? weighted?' — before any algorithm talk.
  • State the traversal invariant: BFS 'queue holds the frontier in distance order'; DFS 'gray nodes are my current path'.

Common mistakes

Forgetting visited entirely

Any cycle loops the traversal forever. Every graph walk carries a visited set — no exceptions, even 'obviously acyclic' inputs.

Visited at dequeue instead of enqueue

BFS-correctness AND performance bug: nodes enter the queue multiple times, distances come out wrong, dense graphs explode.

One visited-set scheme for both directions

Directed cycle detection needs the GRAY/on-path distinction; undirected needs parent exclusion. Swapping them yields false cycles on diamonds or misses real ones.

Only traversing from one start

Components, bipartite checks, and cycle detection need the outer loop over all vertices — disconnected pieces exist.

Deep recursion on big graphs

10⁵-vertex path graph = RecursionError. Know the iterative DFS conversion cold.

Wrong edge direction in toposort

[course, prerequisite] pairs must become prerequisite → course edges. Reversed arrows produce reversed (wrong) schedules.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Medium (11)

Hard (1)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. Fewest moves to solve a sliding puzzle / shortest word-ladder chain — which traversal and why?
  2. Code output2. BFS from A on: A–B, A–C, B–D, C–D, D–E (neighbours in alphabetical order). What's the visit order?
  3. Concept3. In three-colour DFS, meeting a BLACK neighbour means…
  4. Scenario4. Course Schedule: 4 courses, prerequisites [[1,0],[2,1],[3,2],[1,3]]. What does Kahn's algorithm report?
  5. Complexity5. BFS on a graph with V vertices and E edges, adjacency-list representation, costs…
  6. Scenario6. Rotting oranges: all rotten oranges spread simultaneously each minute. What's the right technique?
0 of 6 answered

Frequently asked questions

How do I know a problem is secretly a graph problem?

Look for entities with pairwise relationships and a reachability/ordering/grouping question: grids of cells, words one letter apart, courses with prerequisites, accounts sharing emails. Say 'vertices are X, edges are Y' — if that sentence lands, it's a graph.

Adjacency list or matrix in interviews?

List (dict of lists) 95% of the time: O(V+E) space and neighbour iteration match traversal costs. A matrix earns its O(V²) only for dense graphs or repeated O(1) 'does edge (u,v) exist?' checks.

DFS or BFS when both work (e.g. counting components)?

Truly interchangeable for reachability — pick the one you write fastest and say why it doesn't matter here. The forced choices: shortest unweighted path → BFS; anything needing path-order/finish-order (cycles, toposort-by-DFS) → DFS.

Summary & cheat sheet

Key takeaways

  • Declare vertices, edges, directedness, and weights before choosing any algorithm.
  • BFS = queue = distance layers = shortest unweighted paths; mark visited on enqueue.
  • DFS = depth + backtracking = components, cycles (3 colours), orderings.
  • Toposort: peel zero-indegree vertices; leftovers = cycle.
  • Grids and word ladders are graphs without adjacency lists — generate neighbours on the fly.
  • Everything here is O(V + E).

Formulas & cheat sheet

  • Undirected: Σ degree = 2E · Directed: Σ indegree = Σ outdegree = E
  • Tree = connected + exactly V − 1 edges
  • Bipartite ⇔ no odd cycle ⇔ 2-colourable by BFS

Interview checklist

  • I can write BFS-with-distances and iterative DFS from memory.
  • I can detect cycles in BOTH directed and undirected graphs.
  • I can implement Kahn's toposort and use it as cycle detection.
  • I can flood-fill a grid without building an adjacency list.