DFS — algorithm, stack - recursion, O(V+E), visited array: Worked examples

The scenario matrix

Every graph DFS can face falls into one of these case classes. Think of it as a checklist — if we cover every row, we have covered DFS.

#	Case class	What makes it tricky	Covered by
A	Empty / isolated vertices, zero edges	edges $E = 0$ : is $O (V + E)$ still right?	Ex 1
B	Simple tree (no cycles, one root)	pure "go deep, backtrack" — the clean case	Ex 2
C	Cycle present (undirected or directed)	visited array must stop the infinite loop	Ex 3
D	Disconnected (many components)	one DFS launch is not enough	Ex 4
E	Directed graph, edge direction matters	you can reach a node but not come back	Ex 5
F	Complete graph $K_{n}$ (densest possible)	limiting behaviour: cost $\to O (n^{2})$	Ex 6
G	Neighbour-order sensitivity (same graph, different lists)	proves DFS order isn't unique	Ex 7
H	Real-world word problem	model a maze / network as a graph	Ex 8
I	Exam twist — recursive vs iterative give different orders	iterative-stack reverses neighbour scan	Ex 9

Cell A (zero-edge) and cell F (max-edge) are the two limiting extremes — everything real lives between them.

Case A — the zero-edge extreme

Worked example Example 1 — three isolated dots (cell A)

Graph: 0:[] 1:[] 2:[]. No edges at all. Start at 0.

Forecast: Before reading on — guess how many vertices DFS processes if we launch only from vertex 0. And guess the total work.

Steps.

Mark and process vertex 0. Why this step? It's the source; DFS always begins by claiming its start node.
Scan graph[0] — it's empty, so there are no neighbours to recurse into. Why this step? DFS descends only through edges; no edges means nowhere to go.
explore(0) returns immediately. Vertices 1 and 2 are never touched from this single launch. Why this step? They are unreachable — no path leads to them.

So a single DFS launch processes 1 vertex here.

Verify: Work done $= 1$ vertex visit $+ 0$ edge scans $= 1$ . The formula $O (V + E)$ with the reachable subgraph $V_{reach} = 1, E = 0$ gives $1$ . ✓ This is exactly why we write $O (V + E)$ and not $O (E)$ : here $E = 0$ but work is not zero. See the figure.

Figure — DFS — algorithm, stack - recursion, O(V+E), visited array

Case B — the clean tree

Worked example Example 2 — depth order on a branching tree (cell B)

Graph: 0:[1,4] 1:[2,3] 2:[] 3:[] 4:[]. Start at 0.

Forecast: Guess the visiting order. Will it be 0,1,2,3,4? Or something else?

Steps.

Visit 0. Neighbours [1,4] — take 1 first. Why this step? Rule: leftmost unvisited neighbour first. Order so far: 0.
Visit 1. Neighbours [2,3] — take 2. Why this step? Go deep, not wide — we dive into 1's subtree before looking at 4. → 0,1.
Visit 2. No neighbours → dead end → backtrack to 1. → 0,1,2.
Back at 1, next neighbour 3 is unvisited → visit 3. Why this step? Backtracking means "resume 1's neighbour loop where we paused." → 0,1,2,3.
3 dead-ends → backtrack to 1 (done) → backtrack to 0. Next neighbour 4 unvisited → visit 4. Why this step? Only now, after 1's whole subtree finished, do we try 0's second branch. → 0,1,2,3,4.

DFS order: 0, 1, 2, 3, 4.

Verify: 5 vertices each visited once; each of the 4 edges scanned once (tree ⇒ $E = V - 1 = 4$ ). Work $= 5 + 4 = 9$ . Contrast with BFS which would give 0,1,4,2,3 (level by level) — see BFS — Breadth-First Search. ✓

Case C — a cycle, where visited earns its keep

Worked example Example 3 — undirected square with a diagonal (cell C)

Graph (undirected): 0:[1,3] 1:[0,2] 2:[1,3] 3:[0,2]. Start at 0. This is a 4-cycle 0-1-2-3-0. Without a visited array DFS would spin around it forever.

Forecast: Guess the order, and guess where the visited-check first prevents a loop.

Steps.

Visit 0. Neighbours [1,3] → take 1. → 0.
Visit 1. Neighbours [0,2] → 0 is already visited, skip; take 2. Why this step? The edge back to 0 exists but visited[0]=True stops re-entry — first save. → 0,1.
Visit 2. Neighbours [1,3] → 1 visited, skip; take 3. → 0,1,2.
Visit 3. Neighbours [0,2] → both visited, skip. Why this step? Every exit from 3 loops back to a marked node — the cycle is fully sealed off. → 0,1,2,3.
Backtrack all the way; nothing new. Done.

DFS order: 0, 1, 2, 3.

Verify: 4 vertices, undirected edges $= 4$ (each scanned from both ends ⇒ $2 E = 8$ inspections, by the Handshake Lemma). Total work $= 4 + 8 = 12$ , finite — no infinite loop. ✓ This is the machinery behind Cycle Detection.

Case D — disconnected graph, multiple launches

Worked example Example 4 — two islands (cell D)

Graph (undirected): 0:[1] 1:[0] 2:[3] 3:[2] 4:[]. Two edges 0-1 and 2-3, plus lonely vertex 4.

Forecast: Guess how many DFS launches are needed to touch everyone, i.e. the number of Connected Components.

Steps. Use the component-counting loop over every unvisited vertex.

u=0 unvisited → launch DFS: visits 0,1. count=1. Why this step? 0 was reachable from no earlier root, so it opens a new component.
u=1 already visited → skip. Why this step? The launch from 0 already claimed 1.
u=2 unvisited → launch DFS: visits 2,3. count=2. Why this step? No edge bridges island {0,1} to island {2,3}, so 2 was unreachable before now.
u=3 visited → skip.
u=4 unvisited → launch DFS: visits 4 alone. count=3. Why this step? Isolated vertex is its own component (echo of Case A).

Number of connected components: 3.

Verify: Total work across all launches $= 5$ vertices $+ 2 \cdot 2 = 4$ edge-inspections $= 9$ , still $O (V + E)$ — the shared visited array means no vertex is re-launched. ✓

Case E — direction matters

Worked example Example 5 — a directed graph (cell E)

Graph (directed): 0:[1,2] 1:[3] 2:[3] 3:[]. Arrows point one way only.

Forecast: From 0, can DFS reach 3 by two different paths? How many times is 3 processed?

Steps.

Visit 0. Out-neighbours [1,2] → take 1. → 0.
Visit 1. Out-neighbour [3] → take 3. → 0,1.
Visit 3. No out-edges → backtrack to 1 → backtrack to 0. → 0,1,3.
Back at 0, next out-neighbour 2 unvisited → visit 2. → 0,1,3,2.
Visit 2. Out-neighbour [3] → visited[3]=True, skip. Why this step? 3 is reachable via both 0→1→3 and 0→2→3, but processed once — the visited array kills the duplicate. → done.

DFS order: 0, 1, 3, 2. Vertex 3 processed exactly once despite two incoming paths.

Verify: In a directed graph $\sum outdeg (v) = E = 4$ , so edge work $= 4$ (not $2 E$ ). Total $= 4 + 4 = 8$ . Note you cannot get from 3 back to 0 — direction blocks it. This one-way structure is the basis of Topological Sort. ✓

Case F — the dense extreme $K_{n}$

Worked example Example 6 — complete graph

$K_{4}$ (cell F) $K_{4}$ : 4 vertices, every pair joined. 0:[1,2,3] 1:[0,2,3] 2:[0,1,3] 3:[0,1,2]. Start 0.

Forecast: $K_{n}$ has the most edges possible. Guess $E$ for $K_{4}$ and guess total DFS work.

Steps.

Number of edges: $E = (2 4) = \frac{4 \cdot 3}{2} = 6$ . Why this step? Every unordered pair of the 4 vertices is one edge, and $(2 n)$ counts pairs.
Visit 0 → neighbour 1 → neighbour 2 → neighbour 3 (each time the leftmost unvisited). → order 0,1,2,3. Why this step? DFS still just dives; density doesn't change the order rule, only how many edges get skipped.
From 3, all neighbours [0,1,2] are visited → skip all; backtrack up the chain, every remaining edge hits an already-visited node. Why this step? In a complete graph, after the deep spine 0-1-2-3 is built, every other edge is a "back edge" to a visited vertex.
Total edge-inspections $= 2 E = 12$ (undirected). Vertex work $= 4$ .

DFS order: 0, 1, 2, 3. Total work $= 4 + 12 = 16$ .

Verify (limiting behaviour): cost $= O (V + E) = O (n + \frac{n ( n - 1 )}{2}) = O (n^{2})$ . For $n = 4$ : $4 + 6 = 10$ distinct touches, or $4 + 12 = 16$ counting each edge from both ends — both are $O (n^{2})$ -consistent. As $n \to \infty$ , the $E$ term dominates: DFS on a dense graph is quadratic. ✓

Case G — order isn't unique

Worked example Example 7 — same graph, reordered neighbours (cell G)

Take Example 2's graph but list 0's neighbours reversed: 0:[4,1] 1:[2,3] 2:[] 3:[] 4:[].

Forecast: Same edges, same vertices. Will the DFS order change?

Steps.

Visit 0. Neighbours now [4,1] → leftmost is 4. → 0.
Visit 4. Dead end → backtrack to 0. → 0,4. Why this step? We committed to 4's (empty) subtree first because it's now listed first.
Next neighbour 1 → visit 1 → its neighbours [2,3] → visit 2, backtrack, visit 3. → 0,4,1,2,3.

DFS order: 0, 4, 1, 2, 3 — different from Example 2's 0,1,2,3,4, same graph.

Verify: Both orders visit all 5 vertices exactly once; work $= 5 + 4 = 9$ in both. The set visited is identical; only the sequence differs — DFS order is defined only up to neighbour ordering. ✓

Case H — a real-world maze

Worked example Example 8 — escaping a 5-room dungeon (cell H)

Rooms A,B,C,D,E. Doors (undirected): A–B, A–C, B–D, C–D, D–E. You start in A and want to know: is room E reachable, and one path to it?

Forecast: Model rooms as vertices, doors as edges. Guess whether DFS reaches E.

Steps. Index A=0,B=1,C=2,D=3,E=4. Adjacency: 0:[1,2] 1:[0,3] 2:[0,3] 3:[1,2,4] 4:[3].

Visit A. Neighbours [B,C] → B. Why this step? Model the maze as a graph, then just run DFS. → A.
Visit B. Neighbours [A,D] → A visited, → D. → A,B.
Visit D. Neighbours [B,C,E] → B visited, → C. Why this step? Deep-first: we dive into C before finishing E, because C is listed before E. → A,B,D.
Visit C. Neighbours [A,D] both visited → backtrack to D. → A,B,D,C.
Back at D, next neighbour E unvisited → visit E. Why this step? E is finally reached — the maze is solvable. → A,B,D,C,E.

E is reachable. A concrete escape path (the recursion spine when E was found): A → B → D → E.

Verify: 5 rooms, 5 doors ⇒ work $= 5 + 2 \cdot 5 = 15$ inspections, finite. Path A-B-D-E uses only real doors (A–B ✓, B–D ✓, D–E ✓) — a valid route. ✓

Case I — the exam twist

Worked example Example 9 — recursive vs iterative give different orders (cell I)

Graph: 0:[1,2,3] 1:[] 2:[] 3:[]. A star: 0 connected to 1,2,3. Start 0. Run recursive DFS and iterative (explicit-stack) DFS. Do they match?

Forecast: Same code idea, same graph — surely the same order? Guess before checking.

Steps.

Recursive: visit 0, loop neighbours [1,2,3] in order → visit 1 (dead end), 2, 3. Order = 0,1,2,3. Why this step? The for loop processes neighbours left-to-right.
Iterative: stack=[0]. Pop 0, visit it, push neighbours 1,2,3 → stack=[1,2,3]. Why this step? We append in list order.
Pop from the top (right end): pop 3 → visit 3. Then pop 2 → visit 2. Then pop 1 → visit 1. Why this step? A stack is LIFO — the last pushed (3) comes out first, reversing the neighbour order. Order = 0,3,2,1.

Recursive: 0,1,2,3. Iterative: 0,3,2,1. Both are valid DFS orders; they differ because the explicit stack reverses each neighbour batch.

Verify: Both visit all 4 vertices once; work $= 4 + 2 \cdot 3 = 10$ each. Neighbour list [1,2,3] reversed is [3,2,1] — exactly the iterative visiting order after 0. To make iterative match recursive, push neighbours in reverse (3,2,1) so they pop as 1,2,3. ✓ See Stack data structure and Recursion and the Call Stack.

Recall checkpoints

Recall Did you internalise every cell?

Cover the matrix mentally and answer:

Why is a zero-edge graph the reason we write $O (V + E)$ not $O (E)$ ? ::: Because with $E = 0$ the work is still $V > 0$ ; $O (E)$ would wrongly say constant.
In a graph with a cycle, at which step does the visited array first prevent a loop? ::: The moment a neighbour edge points to an already-marked vertex — that vertex is skipped instead of re-entered.
How many DFS launches does a graph with $k$ connected components need to cover all vertices? ::: Exactly $k$ — one per component.
Does DFS order change if you reorder a vertex's neighbour list? ::: Yes — the set visited is fixed but the sequence depends on neighbour order.
Why do recursive and explicit-stack DFS sometimes visit in different orders? ::: The stack is LIFO, so pushing neighbours left-to-right pops them right-to-left, reversing each batch.

Connections

3.5.05 DFS — algorithm, stack - recursion, O(V+E), visited array (Hinglish) — the parent, in Hinglish.
BFS — Breadth-First Search — compare orders (Ex 2, Ex 9).
Stack data structure · Recursion and the Call Stack — the LIFO twist in Ex 9.
Cycle Detection — built on Ex 3's machinery.
Topological Sort — needs the directed structure of Ex 5.
Connected Components — the multi-launch idea of Ex 4.
Handshake Lemma — the $2 E$ used in Ex 3, 6.