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

Prerequisite pictures we lean on: Stack data structure (the last-in-first-out pile), Recursion and the Call Stack (the pile you get for free), and the parent DFS topic note.

Step 1 — What even is a graph? (dots and lines)

WHAT. Before we can search anything, we need the thing being searched. A graph is just a set of dots (called vertices or nodes) and lines joining some pairs of them (called edges). That's the entire object — no coordinates, no geometry required, just "who is connected to whom".

WHY. Every symbol later ($V$, $E$, $\mathrm{deg}$, "neighbor") is a name for something you can literally point at in this picture. If we don't fix the picture first, those symbols are floating.

PICTURE. Look at the figure. The blue dots labelled 0..4 are the vertices. Each yellow line is an edge. Vertex 0 touches 1 and 2, so we say 1 and 2 are the neighbors of 0.

We store a graph as an adjacency list: for each dot, the list of its neighbors.

$\underset{\text{the vertex}}{\underbrace{0}}:\underset{\text{its neighbor list}}{\underbrace{[1,2]}}$

Step 2 — The rule of the game: dive, don't wander

WHAT. DFS picks a starting dot, walks to a neighbor, then immediately walks to that dot's neighbor, and keeps going as deep as it can before ever trying a sideways option. Only at a dead end does it step back.

WHY this rule and not "visit all neighbors first"? Visiting all neighbors first is a different algorithm — that's BFS — Breadth-First Search. "Deep first" is a deliberate choice: it means the path we are currently on is always a single unbroken chain from the start, which is exactly what makes backtracking a simple "undo the last step".

PICTURE. The red arrow plunges straight down one chain 0 → 1 → 3. It does not fan out. The greyed sideways edge to 2 is deliberately postponed.

Step 3 — Why we need a glowstick: the visited array

WHAT. Before diving into a dot we set a flag visited[v] = True. This is a plain array of true/false, one slot per vertex.

WHY. Real graphs have cycles — paths that loop back, like 0 → 1 → 2 → 0. Without a memory of where we've been, DFS would follow the loop forever. The flag turns "have I been here?" into an instant yes/no lookup, so we never re-enter a dot.

PICTURE. Each visited dot lights up green (a "glowstick dropped"). When the diving arrow reaches a dot that is already green, it stops — that red ✗ is the cycle being cut.

Step 4 — Counting the vertex work

WHAT. Add up the cost of the "arrive + mark + process" that happens at each dot.

WHY. We refuse to memorize $O(V+E)$; we earn it by literally summing the work. This step handles the "arrive at a dot" half of that sum.

PICTURE. Every dot gets exactly one green pulse. Five dots ⇒ five pulses. The little "$1$" on each dot is its contribution.

$\underset{\text{one unit per dot}}{\underbrace{\sum _{v\in V}1}}=\underset{\text{total dots}}{\underbrace{V}}$

• ${\sum }_{v\in V}$ ::: "add up over every vertex $v$".
• $1$ ::: the constant work of arriving-and-marking one dot (guaranteed once, by Step 3).
• $V$ ::: the answer — vertex work is exactly the number of vertices.

So the vertex part of the cost is $O(V)$.

Step 5 — Counting the edge work (the Handshake Lemma)

WHAT. When we stand on a dot $u$, we scan its neighbor list to decide where to dive. That scan does $\mathrm{deg}(u)$ little checks. Sum this over all dots.

WHY. This is the "look down each line" half of the cost. We need to know: how many line-inspections total?

PICTURE. Colour each edge's two endpoints. Notice every yellow line is looked at from both of its ends — once from each endpoint's scan. So each line is counted twice across the whole run.

$\underset{\text{all neighbor-scans}}{\underbrace{\sum _{v\in V}\mathrm{deg}(v)}}=\underset{\text{each edge counted from both ends}}{\underbrace{2E}}$

• ${\sum }_{v\in V}\mathrm{deg}(v)$ ::: total neighbor-list inspections over the whole run.
• $2E$ ::: because one undirected edge has two endpoints, it appears in two lists — this is the Handshake Lemma.

For a directed graph you only scan outgoing edges, so the sum is ${\sum }_v\text{outdeg}(v)=E$ (each arrow lives in exactly one list). Either way the edge work is $O(E)$.

Step 6 — Adding the halves: where $O(V+E)$ comes from

WHAT. Glue Step 4 and Step 5 together.

WHY. Total work = vertex work + edge work. There is no other work — every operation DFS does is either "arrive at a dot" or "inspect a neighbor line".

PICTURE. Two bars — a $V$-bar (green, vertex work) and an $E$-bar (yellow, edge work) — stacked into one total bar. They add; they do not multiply.

$T(V,E)=\underset{\text{Step 4}}{\underbrace{O(V)}}+\underset{\text{Step 5}}{\underbrace{O(E)}}=\boxed{O(V+E)}$

Step 7 — The disconnected case: launching DFS more than once

WHAT. If the graph is in separate pieces, one dive from a single start can't reach everything. So we loop over all dots and launch a fresh DFS from any that is still unvisited.

WHY. Each fresh launch discovers exactly one previously-unreached island — this is how DFS counts Connected Components. The degenerate worry: "does re-launching multiply the cost?"

PICTURE. Two islands. The first launch (red) fills island A; the second launch (blue) fills island B. The shared glowstick array spans both, so no dot is ever re-entered.

${\sum }_{\text{all launches}}(V_i+E_i)=V+E$

• $V_i,E_i$ ::: the dots and lines inside island $i$.
• Because the islands don't overlap, their pieces add up to the whole. Total cost stays $O(V+E)$ — re-launching is free in the big-O sense.

The one-picture summary

This final figure compresses the whole derivation: the diving arrow (Step 2), the green glowsticks bounding vertex work at $V$ (Steps 3–4), each edge inspected from both ends giving $2E$ (Step 5), and the two costs added into $O(V+E)$ (Step 6) — with the isolated-node reminder for why the "$+$" survives (Step 7).

Connections

• BFS — Breadth-First Search — same picture, but a queue replaces the stack, so it fans out level-by-level instead of diving.
• Stack data structure — the LIFO pile that makes backtracking automatic (Step 2).
• Recursion and the Call Stack — that pile, for free, in recursive DFS.
• Handshake Lemma — the $\sum \mathrm{deg}(v)=2E$ fact behind Step 5.
• Connected Components — the multi-launch idea of Step 7.
• Cycle Detection — builds on the visited/glowstick machinery of Step 3.
• Topological Sort — reuses DFS post-order on directed graphs.