BFS & DFS Explained: Graph Traversal, Levels & Cycle Detection

A rumour starts with one student in a college. Version one: she tells her friends, they tell their friends — the rumour spreads in rings, everyone at distance 1, then distance 2, outward like a stone dropped in water. Version two: she tells ONE friend, who tells ONE friend — the rumour drives down a single deep chain before ever coming back to try another branch.

Same friend network, same starting point, two exploration personalities. In code they are BFS (breadth-first — the ripple) and DFS (depth-first — the dive), and the delightful secret of this lesson is that they are the same algorithm with one word changed.

One algorithm, two containers

Every graph traversal is the same loop: keep a collection of "discovered but not yet explored" vertices; repeatedly take one out, visit it, and add its unvisited neighbours. The only decision is which one to take out next — and that decision is a data structure:

• Take the oldest discovery (a queue, FIFO) → explore in rings, nearest first → BFS.
• Take the newest discovery (a stack, LIFO) → chase the freshest lead as deep as it goes → DFS.

Choose the container and you have chosen the exploration order — the stack/queue pairing from the Data Structures course, now running the whole show.

BFS: the queue and its guarantee

from collections import deque

def bfs_distances(adj, src):
    dist = {src: 0}                # doubles as the visited set
    q = deque([src])
    while q:
        u = q.popleft()            # serve the OLDEST discovery
        for v in adj[u]:
            if v not in dist:      # first discovery only
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

adj = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
       "D": ["B", "C", "E"], "E": ["D"]}
print(bfs_distances(adj, "A"))

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}

BFS carries a superpower disguised as a habit: in an unweighted graph, the FIRST time BFS reaches a vertex, it arrived by a shortest path. Why: the queue serves strictly non-decreasing distances — every distance-k vertex is served before any distance-(k+1) vertex — so nothing at distance k+1 can sneak in front. First arrival = minimal edge count. Every "minimum steps" problem you will ever meet is this guarantee, cashed in.

Cost: O(V + E) with an adjacency list — each vertex enqueued once, each edge examined from both ends once.

Dry run: BFS with the queue visible

serve A: discover B (d=1), C (d=1)      q = [B, C]
serve B: A seen; discover D (d=2)       q = [C, D]
serve C: A seen; D seen -> add NOTHING  q = [D]
serve D: B, C seen; discover E (d=3)    q = [E]
serve E: D seen                         q = []  done

The instructive moment is "serve C": D is already in dist — discovered by B — so C does NOT re-add it. D's distance stays 2, via its first discoverer. First discovery wins, and first discovery is shortest.

DFS: the stack and what it's for

def dfs(adj, src, visited=None):
    if visited is None:
        visited = set()
    visited.add(src)
    for v in adj[src]:
        if v not in visited:
            dfs(adj, v, visited)    # dive before trying siblings
    return visited

Recursive DFS rides the call stack — elegant, with Python's ~1000-frame limit as the fine print (big graphs want the explicit stack version). DFS makes no distance promises. So what is it FOR? Two things BFS can't give: the recursion carries the current path (ancestors = the frames on the stack — exactly what cycle detection and topological sort need), and it exhausts everything reachable with minimal ceremony — components, existence checks, flood fills. The tree traversals of lesson 6 were DFS all along.

The visited set (and WHEN to mark)

Trees have no cycles, so tree code needs no visited set. Graphs have cycles — skip the set and A → B → A → B never terminates. That's the obvious half. The subtle half: mark on DISCOVERY (enqueue), not on serving (pop).

Why does it matter? Mark-on-pop lets a vertex with five discoverers enter the queue five times before its first serving. Output stays correct; the queue bloats and dense graphs crawl. In the BFS code above, membership in dist is assigned at discovery — copy that pattern.

Grids are graphs: number of islands

The most-reported traversal question never says "graph". A grid of 1s (land) and 0s (water): count the islands (4-directionally connected land). See the hidden graph: cells are vertices; up/down/left/right adjacency is the edge rule, computed on the fly.

And what IS an island, graph-speak? A connected component. Count components the classic way: scan all cells; every time you meet UNVISITED land, that's a new island — flood-fill it (DFS) so it's never counted again:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0

    def sink(r, c):                    # DFS flood-fill
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return
        grid[r][c] = -1                # mark visited (in the grid itself)
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:        # unvisited land: a NEW island
                count += 1
                sink(r, c)             # consume the whole island
    return count

print(num_islands([[1, 1, 0, 0],
                   [1, 0, 0, 1],
                   [0, 0, 1, 1]]))

2

Check it by eye: the three 1s at top-left form one island; (1,3) connects down to (2,3) and left to (2,2) — one more. Two. Islands = number of flood-fills started, and every cell is touched O(1) times: O(rows × cols). The same grid-as-graph move powers maze problems, rotten oranges (BFS — it needs time levels), and literally Photoshop's paint bucket.

Ordering dependencies: topological sort

New problem shape: courses with prerequisites — in what order can you study them? Model: directed graph, edge u → v meaning "u before v". A valid order exists iff there is no directed cycle (A needs B needs A = deadlock, no order can exist).

What would common sense do? Take any course with no pending prerequisites. Cross it off everywhere. Repeat. That IS the algorithm — Kahn's algorithm — with in-degrees doing the bookkeeping:

from collections import deque

def topo_order(n, edges):              # edges: (before, after)
    adj = {i: [] for i in range(n)}
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)   # no prerequisites
    order = []
    while q:
        u = q.popleft()
        order.append(u)                # "take the course"
        for v in adj[u]:
            indeg[v] -= 1              # u done: v loses one prerequisite
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None = a cycle exists

print(topo_order(4, [(0, 1), (1, 2), (1, 3), (2, 3)]))

[0, 1, 2, 3]

And the elegant part: if a cycle exists, its members' in-degrees never reach 0 — they starve the queue, the loop ends early, and len(order) < n reports the deadlock. Starvation IS the cycle detector. Build systems, package managers, spreadsheet recalculation — all this algorithm.

What if...?

What if the graph is disconnected? One BFS/DFS sees only its component. Loop over all vertices, traversing from each unvisited one — islands did exactly this, and "how many components?" is the count of restarts.

What if edges have weights? BFS's guarantee dies — fewest edges no longer means smallest total (a 2-hop 1+1 route beats a 1-hop 10). That exact failure is where Dijkstra (next lesson) begins.

What if the grid is huge and recursion crashes? A 500×500 grid can nest 2,50,000 frames deep — RecursionError. Convert the flood-fill to an explicit stack (same logic, heap-sized limit) or BFS. Say the limit exists before it bites.

What if I need the minimum steps between two STATES, not places? Word ladder, knight moves, lock combinations: states are vertices, legal moves are edges — an implicit graph nobody hands you. "Minimum moves" + uniform cost = BFS on the state graph, generated on the fly. Seeing the hidden graph is the actual skill being tested.

Common mistakes

• No visited set on a cyclic graph — infinite loop; marking on pop instead of enqueue — bloated queues.
• Using DFS for "minimum steps" — it finds A path, not the shortest.
• Recursion-depth crashes on big grids — explicit stack or BFS.
• Forgetting disconnected graphs — traverse from every unvisited vertex.
• Treating diagonals as adjacent (or not) against the problem's definition — read the adjacency rule.
• Running Kahn's without checking len(order) == n — silently accepting deadlocked input.

How do I choose — BFS or DFS?

Quick revision

One thing to remember

BFS and DFS are one algorithm with the container swapped: queue → ripples and shortest paths; stack → dives, cycles and order.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three staples: BFS with the queue traced, number of islands, and course-schedule deadlock detection via Kahn's.

Q1BFS/DFSeasy

BFS uses a queue and DFS uses a stack because:

Asked in

aQueues are faster than stacksbBFS explores nearest-first (FIFO serves discovery order); DFS commits to one path deepest-first (LIFO serves the most recent discovery)cIt is convention with no reasondDFS cannot be written any other way

Q2BFSeasy

In an UNWEIGHTED graph, the first time BFS reaches a node, the path taken is:

Asked in

aA shortest path — BFS explores in strictly increasing distance from the sourcebA random pathcThe longest pathdAlphabetical order

Q3BFS/DFSmedium

Forgetting the visited set in BFS/DFS on a graph with cycles causes:

Asked in

aSlightly slower runsbInfinite loops (or exponential blowup) — the traversal keeps re-entering nodes around the cyclecWrong node order but correct terminationdNothing; graphs handle it automatically

Q4BFS/DFSmedium

Number of Islands (grid of 1=land, 0=water) is solved by:

Asked in

aCounting all the 1sbScanning the grid; each UNVISITED land cell starts one flood-fill (BFS or DFS) that marks its whole island — count the startscSorting the grid rowsdDynamic programming over rows

Q5Topological sortmedium

Course prerequisites form a directed graph. A valid study order exists if and only if:

Asked in

aThe graph is connectedbThe graph has NO directed cycle — topological order exists exactly for DAGscEvery course has at most one prerequisitedThe graph has fewer edges than nodes

Q6BFS/DFShard

You need the MINIMUM number of moves for a knight to reach a target square on a chessboard. BFS, not DFS, because:

Asked in

aDFS cannot move like a knightbEach move costs the same (1), so it's an unweighted shortest-path problem — BFS's speciality; DFS would find A path, possibly absurdly longcBFS uses less memorydDFS would revisit squares

Hands-on tasks:

FAQ

Ripples and dives mastered. Next: what happens to "shortest" when roads get lengths — Lesson 10: Shortest Paths & MST →