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

Walk the rule "mark on arrival, then descend into the first unvisited neighbor."

• Arrive 0, mark it. Order so far: 0. First neighbor is 1, unvisited → go in.
• Arrive 1, mark. Order: 0,1. 1's only neighbor is 3, unvisited → go in.
• Arrive 3, mark. Order: 0,1,3. 3 has no neighbors → dead end, backtrack to 1.
• 1 has no more neighbors → backtrack to 0.
• 0's next neighbor is 2, unvisited → go in. Arrive 2, mark. Order: 0,1,3,2. DFS order = 0, 1, 3, 2. Notice it is not 0,1,2,3 — that "finish a level before going deeper" pattern is BFS, not DFS.

• Arrive 0, mark → 0. First neighbor 1, unvisited → in. Arrive 1, dead end, back to 0.
• Next neighbor 2 → in, dead end, back to 0.
• Next neighbor 3 → in, dead end. DFS order = 0, 1, 2, 3. With no deeper structure, DFS just walks the neighbor list of the root.

• Arrive 0, mark → 0. Neighbor 1 unvisited → in (follow the first grey arrow).
• Arrive 1, mark → 0,1. Neighbor 2 unvisited → in (second grey arrow).
• Arrive 2, mark → 0,1,2. 2's neighbor is 0, but visited[0] is True → skip (the coral dashed arrow in the figure). This is the exact line where the visited array stops an infinite loop.
• Backtrack all the way out. DFS order = 0, 1, 2. Work: $V=3$ vertices marked once, $E=3$ directed edges scanned once → $V+E=3+3=6$ basic operations.

In $K_5$ every distinct pair of vertices is joined by exactly one edge, so counting edges = counting pairs. To count pairs: vertex 0 pairs with the other $4$, vertex 1 with $4$, and so on — that's $5\times 4=20$ ordered picks, but pair {0,1} and {1,0} are the same edge, so we divide by $2$: $E=\frac{5\times 4}{2}=10.$ (This "$n$ choose $2$" count is written $\left(\genfrac{}{}{0ex}{}{5}{2}\right)$ — the symbol $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ just means "the number of ways to pick an unordered pair out of $n$ things," which is exactly the number of possible edges. We derived it above rather than quoting it.) DFS cost $=V+E=5+10=15$ basic operations (each treated as one unit). In big-O this is $O(V+E)$; here numerically 15.

The Handshake Lemma says every undirected edge adds $1$ to two endpoints' degrees, so ${\sum }_v\mathrm{deg}(v)=2E$. ${\sum }_v\mathrm{deg}(v)=2+2+3+3+1+1=12⟹2E=12⟹E=6.$ 6 edges. Now the raw operation count. Two separate piles of work:

• Vertex-marks: each of the $V=6$ vertices is marked once → $6$ operations.
• Edge-inspections: DFS walks each undirected edge from both endpoints, so it does $2E=2\times 6=12$ inspections (not $6$). Raw total $=V+2E=6+12=18$ operations. In asymptotic notation this is still $O(V+E)$, because the factor of $2$ on the edge term is a constant the big-O bound absorbs — but the honest raw count is 18, not $12$. (Writing "$V+E=12$" conflates the asymptotic $E$ with the raw $2E$; they differ by that constant factor.)

Recall the iterative loop: pop a node; if already visited, continue; else mark, process, then push each unvisited neighbor. A stack is LIFO — the last pushed is the first popped. The side panel in the figure lists the resulting pop order.

• Stack [0]. Pop 0, mark, process → order 0. Push its neighbors 1, then 2. Stack [1,2].
• Pop 2 (top of stack!), mark, process → 0,2. Push its unvisited neighbor 3. Stack [1,3].
• Pop 3, mark, process → 0,2,3. No unvisited neighbors. Stack [1].
• Pop 1, mark, process → 0,2,3,1. Its neighbor 3 is already visited → not pushed. Stack []. Processing order = 0, 2, 3, 1.

Why 3 could have been pushed twice: both 1 and 2 list 3 as a neighbor (the two coral arrows). If 1 had been popped before 3 was visited, we'd push 3 a second time — and the stack would briefly hold two copies of 3. The if visited[u]: continue check on pop is what discards the stale copy. (In this exact ordering 3 was already visited before 1 was popped, so the second push never happened — but the check must still be there for graphs where it does.)

DFS does two separate, additive chunks of work:

1. Mark each vertex once → $V$ units.
2. Scan each edge a constant number of times total → $O(E)$ units. These add, they don't multiply, because scanning one vertex's neighbors doesn't re-cost the other vertices — the shared visited array guarantees each vertex/edge is touched a bounded number of times overall. Hence $O(V+E)$. A multiplicative $O(V\cdot E)$ would wrongly claim you redo all edge work for every vertex.

For $V=1000$, $E=0$:

• $O(V+E)=O(1000+0)=O(1000)$ — you still must visit and mark all 1000 vertices. Honest.
• $O(E)=O(0)$ — claims zero work, which is nonsense; you obviously still touch every isolated node. This is exactly why both terms are kept: the $V$ term protects the isolated-vertex case.

Loop u from 0 to 6; each time u is unvisited, that's a brand-new component — launch DFS and increment the count.

• u=0 unvisited → launch. DFS reaches 0,1,2. Component #1 = {0,1,2}.
• u=1,2 now visited → skip.
• u=3 unvisited → launch. DFS reaches 3,4. Component #2 = {3,4}.
• u=4 visited → skip.
• u=5 unvisited → launch. DFS reaches just 5. Component #3 = {5}.
• u=6 unvisited → launch. DFS reaches just 6. Component #4 = {6}. Answer: 4 connected components. Cost: the shared visited array spans all launches, so across every launch combined each vertex is marked once ($V$ total) and each edge scanned a bounded number of times ($O(E)$ total). Total = $O(V+E)$, unchanged — the outer loop does not multiply the cost.

Keep two states beyond plain visited: mark a node on-stack (grey) while it is an active ancestor in the current recursion, and done (black) after we finish it. A cycle exists exactly when DFS finds an edge pointing to a node that is currently on-stack.

• explore(0): mark 0 on-stack. Edge 0→1 → recurse.
• explore(1): mark 1 on-stack. Edge 1→2 → recurse.
• explore(2): mark 2 on-stack. Edge 2→0 → 0 is on-stack → cycle detected! The revealing edge is 2→0 (a "back edge" to an active ancestor). This is why plain visited (which the parent used to prevent looping) is not enough for cycle detection — you must distinguish "seen before" from "seen and still on the active path."

Post-order = record a vertex when we finish it (after all its descendants are done). Reverse that list. Trace (neighbors in listed order, mark on arrival):

• explore(0): go to 1. explore(1): go to 3. explore(3): no neighbors → finish 3. Post: [3].
• Back in 1: done → finish 1. Post: [3,1].
• Back in 0: next neighbor 2. explore(2): neighbor 3 already visited → skip → finish 2. Post: [3,1,2].
• Back in 0: done → finish 0. Post: [3,1,2,0]. Reverse post-order = 0, 2, 1, 3. Check every edge points left-to-right in this order: 0→1 ✓, 0→2 ✓, 1→3 ✓, 2→3 ✓. Valid topological order. Why reversal works (for any DAG): when DFS finishes a vertex u, every vertex reachable from u is already finished (they were explored and popped before u). So in post-order, u appears after all its descendants. Reversing puts u before all its descendants — which is exactly the topological requirement "each vertex before everything it points to." A DAG has no cycle, so no back edge ever forces a contradiction.

Vertex work. The visited array blocks re-entry, so explore runs at most once per vertex. Marking + processing is $O(1)$ each → summing $O(1)$ over the (at most $V$) explored vertices gives $O(V)$. Edge work. Inside the single explore(u) call, we scan u's adjacency list once: $\text{outdeg}(u)$ inspections. Summed over all vertices that get explored: ${\sum }_u\text{outdeg}(u)=E(\text{directed}).$ The reason this sum equals $E$: every directed edge leaves exactly one tail vertex u, so it is counted exactly once inside that tail's explore — no edge is double-counted, none is missed. Hence edge work is $O(E)$. Total $=O(V)+O(E)=O(V+E)$. These add (not multiply) because the two sums range independently — the vertex sum runs over dots, the edge sum over lines — and the visited array bounds each contribution to a constant number of touches. Degenerate cases:

• $E=0$ (all vertices isolated): the edge sum is $0$, but we still mark each reachable vertex → cost $O(V)$, correctly captured by the $V$ term (an $O(E)=O(0)$ claim would wrongly say "no work").
• Single vertex 0:[0] (a self-loop): $V=1$, $E=1$. explore(0) marks 0, scans its one edge 0→0, sees visited[0]=True, and skips — no recursion. Work $=1+1=2=O(V+E)$. Crucially, no infinite loop, because the self-edge hits the visited guard the instant it is followed. This completes the proof for all three cases (general, edgeless, self-loop). $■$