Graph Traversal: BFS and DFS Explained (Shortest Paths, Cycles, Topological Sort)

In plain words — and an analogy

Imagine you drop a stone into a still pond. The ripples expand outward in perfect concentric rings — every point one metre away gets wet before any point two metres away. That is breadth-first search (BFS): it soaks the graph level by level, finishing all vertices at distance 1 from the start before touching any at distance 2. Now imagine exploring a maze by picking one corridor and walking it until you hit a dead end, then backing up and trying the next branch. That is depth-first search (DFS): commit to one path, go as deep as possible, then backtrack. These two mental images predict almost everything about what each algorithm is good for.

You have a graph in memory; now you need to explore it — visit vertices, find paths, detect structure. There are two fundamental ways, and remarkably, nearly every graph algorithm in existence is one of them (or a weighted refinement of one). The astonishing part: they're the *same* algorithm with one component swapped — replace the queue with a stack and BFS becomes DFS.

The one discipline both require: visited tracking

Unlike trees, graphs have cycles, so a traversal can loop forever revisiting the same vertices. The non-negotiable fix: a visited set (a boolean array or hash set). Mark a vertex visited the moment you enqueue/discover it, and never process it twice. This single rule is what keeps traversal O(V + E) instead of infinite — every vertex is processed once, and every edge examined once.

    (A)
   /   \
 (B)   (C)
  |   /   \
 (D)-(E)  (F)

Edges (undirected, unweighted):
A-B, A-C, B-D, C-D, C-E, C-F

Breadth-first search: rings of distance

BFS uses a queue. Start at a source, then repeatedly take the oldest-discovered vertex and add its unvisited neighbors to the back. Because the queue is FIFO, BFS finishes all vertices at distance 1 before any at distance 2, all of distance 2 before distance 3 — it expands outward in concentric rings.

BFS(graph, source):
  visited = {source}
  queue   = deque([source])
  dist    = {source: 0}
  parent  = {source: None}

  while queue is not empty:
    u = queue.popleft()           // dequeue oldest
    for each neighbor v of u:
      if v not in visited:
        visited.add(v)            // mark WHEN ENQUEUED
        dist[v]   = dist[u] + 1
        parent[v] = u
        queue.append(v)

  return dist, parent

Worked example: BFS on the sample graph

Start from A. Watch the queue evolve and the distance table fill in step by step:

Step | Dequeue | Queue after      | Distances set
-----|---------|------------------|-------------------------------
  0  |  start  | [A]              | A=0
  1  |    A    | [B, C]           | B=1, C=1
  2  |    B    | [C, D]           | D=2  (A-B-D)
  3  |    C    | [D, E, F]        | E=2, F=2  (A-C-E, A-C-F)
  4  |    D    | [E, F]           | (D already seen from both B and C)
  5  |    E    | [F]              |
  6  |    F    | []               |

Visitation order: A, B, C, D, E, F
Shortest distances from A:
  A=0  B=1  C=1  D=2  E=2  F=2

The killer property: on an unweighted graph, BFS finds the shortest path (fewest edges) from the source to every reachable vertex. The ring-by-ring order guarantees the first time you reach a vertex is via a minimum-length path — you couldn't have reached it sooner by definition of the rings. Reconstruct the actual path by following parent pointers backward from the target. This is why maze-solving, word ladders, 'six degrees' problems, and network-hop counting are all BFS.

Depth-first search: plunge and backtrack

DFS uses a stack — usually the implicit call stack via recursion. From a vertex, walk to an unvisited neighbor, then *its* unvisited neighbor, going as deep as possible; when stuck, backtrack to the last vertex with an unexplored neighbor. Recursive DFS is strikingly short: mark the vertex visited, then recurse into each unvisited neighbor. That's it.

DFS(graph, u, visited):
  visited.add(u)
  for each neighbor v of u:
    if v not in visited:
      DFS(graph, v, visited)

// Call site:
visited = set()
for each vertex u in graph:
  if u not in visited:
    DFS(graph, u, visited)   // handles disconnected components

Worked example: DFS on the sample graph

Call stack (grows right = deeper)       | Action
----------------------------------------|----------------------------
DFS(A)                                  | visit A
  DFS(B)        [A on stack]            | visit B
    DFS(D)      [A, B on stack]         | visit D
      DFS(C)    [A, B, D on stack]      | visit C
        DFS(E)  [A,B,D,C on stack]      | visit E  (backtrack E)
        DFS(F)  [A,B,D,C on stack]      | visit F  (backtrack F)
      (backtrack C)
    (backtrack D)
  (backtrack B)
(backtrack A)

Visitation order: A, B, D, C, E, F
(Compare to BFS order: A, B, C, D, E, F — noticeably different!)

DFS doesn't find shortest paths (it commits to one deep branch before exploring nearer options), but its structure — the order it enters and leaves vertices — reveals graph properties BFS doesn't surface: whether a cycle exists, a valid ordering of dependencies, and the connected/strongly-connected components. Two flagship applications:

• Cycle detection. In a directed graph, track three states — unvisited, *in the current recursion stack*, and finished. If DFS ever reaches a vertex that's currently in the recursion stack, you've found a back edge → a cycle. (In an undirected graph, a cycle is any edge to an already-visited vertex that isn't the parent you came from.)
• Topological sort. On a DAG, run DFS and record each vertex when it *finishes* (all its descendants done); the reverse of that finish order is a valid topological order — every task appears before everything that depends on it. This is how build systems, schedulers, and dependency resolvers compute a legal execution order. If cycle detection fires, no valid order exists.

result = []                 // will hold topo order (reversed)
visited = set()

DFS_topo(u):
  visited.add(u)
  for each neighbor v of u:
    if v not in visited:
      DFS_topo(v)
  result.append(u)            // push AFTER all descendants finish

for each vertex u in graph:
  if u not in visited:
    DFS_topo(u)

result.reverse()              // now a valid topological order

BFS vs DFS at a glance

Both are O(V + E) — the theoretical floor, since you must at least look at every vertex and edge — and both need O(V) space in the worst case. The choice is never about speed; it's about *what you're looking for*. Need the nearest/shortest? BFS. Need to explore structure, detect cycles, or order dependencies? DFS.

Under the hood: why BFS is correct for shortest paths

Proof by induction on distance d: the base case (the source at distance 0) is trivially correct. For the inductive step, assume every vertex at distance d has been correctly labeled with dist = d before any vertex at distance d+1 is processed. When BFS dequeues a vertex u at distance d, it examines u's neighbors. Any unvisited neighbor v must be at distance d+1 (it cannot be at distance ≤ d because it's unvisited, and it cannot be at distance d+2 without a path through d+1 vertices). So BFS correctly labels v with d+1 before any vertex at d+2 is processed. The ring order is what makes the induction hold.

Worked example: shortest path in a grid

Find the fewest steps from top-left to bottom-right of a grid with some blocked cells, moving up/down/left/right. Model it as an implicit graph: each open cell is a vertex, edges join open orthogonal neighbors.

S . . X
. X . .
. . X .
X . . E

S = start (0,0)   E = end (3,3)
X = blocked cell

BFS expansion (each ring is one step):
Ring 0: (0,0)
Ring 1: (0,1), (1,0)
Ring 2: (0,2), (2,0), (1,2)  -- note (1,1) is blocked
Ring 3: (1,3), (2,1), (2,2) -- skipping (0,3) blocked, (3,0) blocked
Ring 4: (3,1), (3,2)  -- note (2,2) already visited
Ring 5: (3,3)  <-- destination reached at distance 5

Run BFS from the start, computing neighbor cells on the fly (no explicit graph needed). The first time BFS dequeues the destination, its recorded distance is the answer — guaranteed minimal by the ring property. On an R×C grid this is O(R·C) time and space: each cell is visited once. Using DFS here would find *a* path but not the shortest, and could wander deep into a dead-end corner first — the wrong tool for a fewest-steps question.

Common pitfalls

• No visited set → infinite loop. The cardinal graph-traversal sin. Cycles will trap you; mark visited on discovery.
• Marking visited too late in BFS. Mark a vertex when you *enqueue* it, not when you dequeue it — otherwise the same vertex can be enqueued multiple times before it's processed, inflating work and sometimes breaking distances.
• Using DFS for shortest paths. DFS finds a path, not the shortest one. Fewest-edges questions are BFS; anything with edge weights needs Dijkstra, not plain BFS.
• Recursive DFS stack overflow. A deep graph (a long chain of 100,000 vertices) overflows the call stack. Convert to an explicit stack when depth is untrusted — the recursion lesson's warning applies directly.
• Forgetting disconnected components. One traversal covers one component. To process the whole graph, loop over all vertices and launch a traversal from each still-unvisited one.

Practice problems

1. Word ladder. Given two words of the same length and a dictionary, find the shortest sequence of one-letter changes transforming the first word into the second (each intermediate word must be in the dictionary). Model each word as a vertex and add an edge between words that differ by one letter. What traversal finds the shortest transformation sequence?
2. Number of islands. Given a 2-D grid of '1' (land) and '0' (water), count the number of islands (connected groups of land cells). For each unvisited land cell, launch a DFS/BFS to mark the entire island visited. The number of launches equals the number of islands.
3. Course schedule. Given a list of courses and prerequisites (course A requires course B first), determine whether all courses can be completed. Model as a directed graph and detect whether a cycle exists using DFS.

Key takeaways

• BFS (queue) explores nearest-first and finds shortest paths on unweighted graphs; DFS (stack/recursion) explores deepest-first and exposes structure.
• Both are O(V + E) time, O(V) space, and both require a visited set to survive cycles.
• DFS powers cycle detection (back edge to a vertex on the recursion stack) and topological sort (reverse finish order on a DAG).
• Swapping the queue for a stack literally turns one into the other — the choice is about the goal, not efficiency.
• Many problems are graphs in disguise; solving them is choosing BFS or DFS and computing neighbors, often without ever materializing the graph.

BFS handled shortest paths when every edge cost the same. But roads have lengths and networks have latencies — next, shortest paths on *weighted* graphs with Dijkstra and Bellman-Ford. Drill BFS/DFS and topological-sort questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play