🧩 Data Structures & Algorithms · Chapter 15

Graphs: BFS and DFS

BFS spreads like a ripple; DFS dives like a maze-runner. Same graph, same O(V + E) cost — but only one of them finds the fewest-stops route.

Study this lesson free in the app →

The basics

A graph is a set of nodes (vertices) joined by edges — cities and roads, people and friendships, web pages and links. BFS (breadth-first search) and DFS (depth-first search) are the two basic ways to visit every node you can reach from a starting point.

The problem it solves: "Can I get from here to there?", "What's the fewest number of hops?", "How many separate groups are there?", "Is there a cycle?" — almost every graph question starts with a systematic walk that never visits a node twice.

The mental model: drop a stone in a pond. The ripple reaches everything 1 step away, then 2 steps, then 3 — that's BFS, driven by a queue. Now explore a cave: follow one tunnel as deep as it goes, and only when it dead-ends, back up to the last fork — that's DFS, driven by a stack (or recursion).

Cost: both are O(V + E) time with an adjacency list, and O(V) extra space for the visited set plus the queue or stack.

Explained

Your metro map: which station is the fewest stops away? Your social network: who is a friend of a friend? Your course plan: in what order can you take classes with prerequisites?

Three different questions, one toolkit: walk the graph without visiting anything twice. The only real choice is whether you walk wide (BFS) or deep (DFS).

The ripple and the cave

A rumour (BFS). You tell your news to your 3 closest friends. Each tells their friends who haven't heard yet. Everyone who hears it on day 1 is one hop away, day 2 is two hops. Ask "how many days until Maria hears?" and the answer is exactly her distance in the friendship graph. Nobody hears it twice, because people who already know just say "old news" — that's the visited set.

A cave (DFS). You explore with a ball of string. Take the first tunnel and keep going. At a dead end, wind the string back to the last fork and try its next tunnel. Chalk an X at every junction you've passed so you never loop. You'll see the whole cave, but the order tells you nothing about which chamber is closest to the entrance.

Representing the graph

The graph used in the next two animations:

    A ─── B
    │     │
    C ─── D ─── F ─── G
    │           │
    E ──────────┘

adjacency list (neighbours in edge order):
A: B, C        E: C, F
B: A, D        F: D, E, G
C: A, D, E     G: F
D: B, C, F

Adjacency list — dict of lists. O(V + E) space; iterating a node's neighbours costs its degree. The default choice. Adjacency matrix — V × V grid of 0/1. O(V²) space, O(1) 'is there an edge?'. Only for small or very dense graphs.

With a list, BFS/DFS take each node out once (V) and scan each edge from both ends (2E) → O(V + E). With a matrix, scanning a row is V, so it becomes O(V²).

BFS from A: ripples

Queue starts [A]. Take A, add B and C. Take B, add D. Take C, add E (D is already seen). Take D, add F. Take E (nothing new). Take F, add G. Visit order: A B C D E F G. Distances: B, C = 1; D, E = 2; F = 3; G = 4.

DFS from A: dive, then backtrack

Recursive DFS taking neighbours in the listed order: A → B → D (B's first new neighbour) → C (D's first new neighbour) → E → F → G. Visit order: A B D C E F G. It reached C third, through a 3-edge path, although C is directly connected to A — DFS order says nothing about distance.

BFS distances, DFS two ways

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
         "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E", "G"],
         "G": ["F"]}

def bfs_dist(graph, start):
    dist = {start: 0}                  # doubles as the visited set
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1
                q.append(nb)
    return dist          # A0 B1 C1 D2 E2 F3 G4

def dfs(graph, node, seen=None):
    seen = set() if seen is None else seen
    seen.add(node)
    for nb in graph[node]:
        if nb not in seen:
            dfs(graph, nb, seen)
    return seen

def dfs_iter(graph, start):            # no recursion limit
    seen, stack, order = set(), [start], []
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node); order.append(node)
        for nb in reversed(graph[node]):  # reversed → same order as recursive
            if nb not in seen:
                stack.append(nb)
    return order         # A B D C E F G

def count_components(graph):
    seen, count = set(), 0
    for v in graph:
        if v not in seen:
            count += 1
            seen |= dfs(graph, v)
    return count

Which one, and what it costs

                     BFS                    DFS
──────────────────────────────────────────────────────────
structure            queue (deque)          stack / recursion
time                 O(V + E)               O(V + E)
extra space          O(V) — widest frontier O(V) — longest path
fewest-hops path     yes                    no
good for             levels, nearest X,     components, cycles,
                     shortest unweighted    topological sort,
                     path, 'within k hops'  mazes, backtracking

On grids (mazes, maps, game boards) each cell is a node with up to 4 neighbours: V = rows × cols, E ≈ 2V, so BFS is O(rows × cols).

At real scale: a social graph with 1 billion users and ~200 friends each has ~100 billion edges — full BFS is a distributed job. 'Friends within 2 hops' stays cheap only because you stop after level 2: 200 + 200² ≈ 40,000 nodes.

Gotchas

• No visited set — the first cycle (A → B → D → C → A) loops forever.
• Marking visited on dequeue in BFS — D is reachable from both B and C, so it gets queued twice; on dense graphs the queue explodes. Mark when you enqueue.
• list.pop(0) as a queue — O(n) per pop turns BFS into O(V²). Use collections.deque.
• BFS on weighted edges — it minimises edges, not kilometres or minutes. Use Dijkstra.
• Recursive DFS on a 100,000-node path — Python's ~1,000-frame limit. Use an explicit stack.
• Expecting one 'correct' DFS order — a stack pushing neighbours in order visits A C E F G D B; recursion visits A B D C E F G. Both are valid DFS orders.
• Forgetting disconnected parts — one BFS only reaches its own component; loop over all nodes.

Words to know

In two minutes

• A graph is nodes plus edges; store it as an adjacency list — O(V + E) space — unless it's tiny or very dense.
• BFS: queue, explores level by level from the start; the first time it reaches a node is via the fewest edges.
• DFS: stack or recursion, follows one path as deep as possible, then backtracks.
• Both visit each node once and look at each edge a constant number of times: O(V + E) time, O(V) extra space.
• Always keep a visited set, and in BFS mark a node visited when you enqueue it, not when you dequeue it.
• BFS → fewest hops, levels, nearest X. DFS → reachability, connected components, cycle detection, topological order, backtracking.
• BFS minimises edge count, not total weight — weighted shortest paths need Dijkstra (a heap).

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.