Traversal Mechanics

Core Concepts

The shared contract: O(V + E)

Before separating BFS from DFS, note what they share. Both algorithms visit each vertex exactly once and examine each edge exactly once. This gives them the same time complexity: O(V + E), where V is the number of vertices and E is the number of edges. This complexity assumes an adjacency list representation — and is one of the strongest arguments for preferring adjacency lists over adjacency matrices when you intend to traverse a graph.

The O(V + E) guarantee holds for best, average, and worst-case scenarios for both algorithms. It is a ceiling that does not depend on graph shape, density, or the start node you choose.

BFS: the queue as the engine

BFS uses a queue — a FIFO (first-in, first-out) data structure. When BFS discovers a new vertex, it enqueues it. When it is ready to process a vertex, it dequeues from the front. Because the queue is FIFO, the first vertices enqueued are the first processed. That is what produces level-order traversal: all vertices at distance 1 from the source are enqueued before any vertex at distance 2, and they are all dequeued and processed before any distance-2 vertex is touched.

BFS explores all vertices at distance k from the source before it explores any vertex at distance k+1. The queue enforces this order mechanically — you do not have to think about it; it falls out of FIFO.

This level-by-level property is what makes BFS useful for shortest paths, but more on that below.

DFS: the stack as the engine

DFS uses a stack — a LIFO (last-in, first-out) data structure, either explicit or implicit through the call stack when you implement DFS recursively. When DFS discovers a new vertex, it pushes it. It immediately processes from the top of the stack. Because LIFO means the most recently discovered vertex is next in line, DFS dives as deep as possible along each path before backtracking.

The recursive implementation is the most natural: the call stack is the stack. The iterative implementation makes this explicit by managing a stack object manually.

---

Step-by-Step Procedure

BFS algorithm

BFS(graph, source):
  mark source as visited
  enqueue source

  while queue is not empty:
    u = dequeue
    for each neighbor v of u:
      if v is not visited:
        mark v as visited
        enqueue v

Key decision point: mark a vertex as visited when you enqueue it, not when you dequeue it. If you wait until dequeue, the same vertex can be enqueued multiple times, corrupting the traversal.

DFS algorithm (iterative)

DFS_iterative(graph, source):
  push source onto stack

  while stack is not empty:
    u = pop
    if u is not visited:
      mark u as visited
      for each neighbor v of u:
        if v is not visited:
          push v

DFS algorithm (recursive)

DFS_recursive(graph, u, visited):
  mark u as visited
  for each neighbor v of u:
    if v is not visited:
      DFS_recursive(graph, v, visited)

The recursive form is often cleaner. The call stack does the bookkeeping. The trade-off is that on very deep graphs, deep recursion can cause stack overflow — something the iterative form avoids by using a heap-allocated data structure.

---

Worked Example

Consider this undirected graph with six vertices:

    A
   / \
  B   C
 / \   \
D   E   F

Edges: A–B, A–C, B–D, B–E, C–F. Start at A.

BFS trace

Step	Queue (front → back)	Visited
Start	[A]	{A}
Dequeue A, enqueue B, C	[B, C]	{A, B, C}
Dequeue B, enqueue D, E	[C, D, E]	{A, B, C, D, E}
Dequeue C, enqueue F	[D, E, F]	{A, B, C, D, E, F}
Dequeue D (no new neighbors)	[E, F]	—
Dequeue E (no new neighbors)	[F]	—
Dequeue F (no new neighbors)	[]	—

Visit order: A, B, C, D, E, F

BFS visited level 0 (A), then level 1 (B, C), then level 2 (D, E, F) — the level structure is directly visible in the trace.

DFS trace (recursive, alphabetical neighbor order)

Call	Action	Visited
DFS(A)	visit A	{A}
→ DFS(B)	visit B	{A, B}
→ → DFS(D)	visit D	{A, B, D}
← back to B	→ DFS(E)	{A, B, D, E}
← back to A	→ DFS(C)	{A, B, D, E, C}
→ → DFS(F)	visit F	{A, B, D, E, C, F}

Visit order: A, B, D, E, C, F

DFS committed to the A→B branch and exhausted it before touching C. The order is fundamentally different despite the same starting node.

---

Compare & Contrast

Dimension	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) / recursion
Visit order	Level by level (by distance from source)	Deep branch first, then backtrack
Time complexity	O(V + E)	O(V + E)
Space complexity (worst case)	O(V) — queue holds widest level	O(V) — stack/call stack holds longest path
Space in practice (wide graphs)	Expensive — queue can grow very large	Cheaper — stack holds only the current path
Finds shortest path (unweighted)?	Yes, guaranteed	No, not guaranteed
Edge classification	Not applicable	Classifies into tree, back, forward, cross edges

Space in practice

Both algorithms share an O(V) worst-case space bound, but the constant matters enormously in practice. BFS's queue grows to the width of the current search frontier — in dense graphs, this can mean holding a large fraction of all vertices simultaneously. DFS's stack holds only the nodes along the current path from root to the active node.

When depth is constrained — for example, when you only need to search to a fixed depth limit — DFS becomes significantly more space-efficient: its space usage is proportional to the depth limit, not to the number of vertices at that level. This is why iterative deepening DFS is used in practice for memory-constrained search problems.

Shortest paths

BFS is guaranteed to find the shortest path in an unweighted graph. When BFS first discovers vertex v through vertex u, that discovery represents the shortest available path to v from the source. The level-order exploration ensures this: no shorter path could exist because BFS would have found it at an earlier level.

DFS offers no such guarantee. Because DFS explores as deeply as possible along each branch, it may reach a target vertex via a long winding path before it ever examines a shorter one. In the worked example above, if you were searching for F, DFS would have found it via A→C→F (length 2), but only because of alphabetical tie-breaking — a different graph shape could easily route DFS through a longer path.

DFS edge classification

One capability unique to DFS is edge classification in directed graphs. As DFS runs, it can label every edge it encounters as one of four types:

• Tree edge — leads to an undiscovered vertex. Forms the DFS tree.
• Back edge — leads to a vertex that is currently on the active recursion stack (an ancestor). Signals a cycle.
• Forward edge — leads to a discovered, finished descendant (not an ancestor).
• Cross edge — leads to a discovered, finished vertex that is neither an ancestor nor a descendant.

This classification reveals structural properties of the graph. The presence of a back edge, for example, is a necessary and sufficient condition for the existence of a cycle in a directed graph. Applications like topological sort and strongly connected components rely on this classification — but those are topics for later modules.

---

Common Misconceptions

"BFS and DFS have different time complexity." They do not. Both are O(V + E) when using adjacency lists. The traversal strategy does not change how many vertices and edges are examined — it only changes the order.

"DFS always uses less memory than BFS." Not always true. Both have O(V) worst-case space. On a linear chain (v1 → v2 → ... → vN), DFS's stack reaches depth V, which is the same order as BFS on a wide tree. The practical advantage of DFS is on graphs where you want to constrain search depth.

"The iterative DFS with a stack is exactly equivalent to recursive DFS." This is subtle. A naive iterative DFS that pushes all neighbors at once may visit nodes in a different order than the recursive version, because of how the LIFO stack reverses the neighbor order. The algorithms are semantically equivalent (they visit the same set of reachable nodes), but visit order can differ. If visit order matters for your application, verify your implementation.

"BFS finds the shortest path in any graph." BFS finds the shortest path only in unweighted graphs, where every edge has equal cost. On weighted graphs, you need Dijkstra's algorithm or similar. BFS's level-order property reflects hop count (number of edges), not edge weight.

---

Active Exercise

Work through the following on paper or in code. Do not move to the next step until you have verified the previous one.

Graph for the exercise:

Vertices: 1, 2, 3, 4, 5, 6, 7
Edges (undirected): 1–2, 1–3, 2–4, 2–5, 3–6, 3–7

This is a complete binary tree of depth 2, with 1 as root.

Part A — BFS trace

1. Start at vertex 1. Write out the queue state after each enqueue/dequeue operation.
2. Record the order in which vertices are visited.
3. What is the maximum size the queue reached? What does that tell you?

Part B — DFS trace

1. Start at vertex 1. Use alphabetical (numerical) order when choosing which neighbor to visit first.
2. Write the recursive call stack at each step.
3. Record the visit order.
4. Compare visit order to your BFS result. What changed? What stayed the same?

Part C — Complexity check Count V and E in this graph. Verify that both BFS and DFS would take O(V + E) steps.

Part D — Edge classification (directed version) Add direction to the edges: 1→2, 1→3, 2→4, 2→5, 3→6, 3→7. Also add a back edge: 4→1. Run DFS from vertex 1. Classify each edge. Which edge type indicates the cycle?