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

WHAT is DFS?

Two equivalent implementations:

Recursive — uses the program's implicit call stack.
Iterative — uses an explicit stack data structure.

WHY a visited array?

This single fact is what makes DFS linear rather than exponential.

HOW it works — derive the complexity from first principles

We don't memorize $O(V+E)$ . We count the work.

Formula Time complexity — derived

Let $V$ = number of vertices, $E$ = number of edges.

Step 1 — vertices. Each vertex is marked visited and processed once (the visited check blocks re-entry). That's $\sum_{v} 1 = V$ work.

Step 2 — edges. When we process a vertex $v$ , we scan its adjacency list once — that's $\deg(v)$ edge-inspections. Summing over all vertices: $\sum_{v \in V} \deg(v) = 2E \quad\text{(undirected)}, \qquad \sum_{v \in V} \text{outdeg}(v) = E \quad\text{(directed)}.$ This is the Handshake Lemma: every undirected edge contributes to two endpoints' degrees.

Total: $T(V,E) = \underbrace{O(V)}_{\text{visit each node}} + \underbrace{O(E)}_{\text{scan each edge}} = \boxed{O(V+E)}$

Space: $O(V)$ for the visited array + up to $O(V)$ for the stack/recursion depth = $O(V)$ .

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

The algorithm — recursive

def dfs(graph, start):
    visited = [False] * len(graph)   # WHY: prevent revisiting / infinite loops
    def explore(u):
        visited[u] = True            # WHY: mark BEFORE recursing, else cycles re-enter
        process(u)                   # pre-order: do work on entry
        for v in graph[u]:           # scan adjacency list -> deg(u) work
            if not visited[v]:       # WHY: only descend into new nodes
                explore(v)           # recurse deep first
    explore(start)

The algorithm — iterative (explicit stack)

def dfs_iter(graph, start):
    visited = [False] * len(graph)
    stack = [start]
    while stack:
        u = stack.pop()              # LIFO -> depth-first
        if visited[u]:               # WHY: a node can be pushed twice before popping
            continue
        visited[u] = True
        process(u)
        for v in graph[u]:
            if not visited[v]:
                stack.append(v)      # push neighbors; deepest explored next

Worked examples

Worked example Example 3 — counting connected components with DFS

Run DFS from every unvisited vertex; each fresh launch = one new component.

count = 0
for u in range(n):
    if not visited[u]:
        explore(u); count += 1   # WHY: this u was unreachable from earlier roots

Total cost is still $O(V+E)$ because across all launches each vertex/edge is touched once. Why? The shared visited array spans launches.

Recall checkpoints

Recall Feynman: explain to a 12-year-old

You're exploring a cave with tunnels. You walk into one tunnel and keep going deeper until it dead-ends. Then you walk back to the last fork and try a tunnel you haven't been in. You drop a glowstick in every room you enter (that's the visited array) so you never re-explore a room or get stuck walking in circles. Because you drop exactly one glowstick per room and walk down each tunnel a fixed number of times, the whole trip takes time proportional to (rooms + tunnels) — fast!

Forecast-then-Verify

Connections

BFS — Breadth-First Search — same $O(V+E)$ , but uses a queue (FIFO) → explores level by level.
Stack data structure — the engine behind DFS's backtracking.
Recursion and the Call Stack — why recursive DFS works "for free".
Cycle Detection — DFS + recursion-stack coloring.
Topological Sort — DFS post-order reversed.
Connected Components — repeated DFS launches.
Handshake Lemma — why $\sum \deg(v) = 2E$ .

What strategy does DFS follow when exploring a graph?

Go as deep as possible along one path, then backtrack to the last vertex with an unexplored neighbor (LIFO).

What data structure does DFS use (explicit or implicit)?

A stack — explicit stack in iterative DFS, or the implicit call stack in recursive DFS.

Why does DFS need a visited array?

To avoid infinite loops on cycles and to ensure each vertex is processed exactly once (graphs can have cycles and multiple paths).

Where must you set visited[u]=True in recursive DFS?

As the FIRST line of explore(u), before scanning neighbors, so cyclic edges back to u are blocked.

What is the time complexity of DFS and why?

O(V+E): each vertex visited once (V) plus each edge scanned once when its endpoint is processed (sum of degrees = 2E or E).

Why is it O(V+E) and not just O(E)?

A graph may have vertices with no edges (E=0); you still must touch every vertex, so the V term is required.

What is the space complexity of DFS?

O(V): visited array O(V) plus stack/recursion depth up to O(V).

In iterative DFS, why check visited on pop, not only on push?

A vertex can be pushed multiple times by different neighbors before being popped; checking on pop guarantees one processing.

DFS order vs BFS order for 0:[1,2],1:[3]?

DFS gives 0,1,3,2 (deep first); BFS gives 0,1,2,3 (level by level).

How do you count connected components with DFS?

Launch DFS from every still-unvisited vertex over a shared visited array; each new launch = one new component.

What graph theorem explains why edge work sums to 2E?

The Handshake Lemma: sum of all vertex degrees in an undirected graph equals 2E.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

DFS ka matlab hai Depth-First Search — yaani kisi bhi ek raaste mein "andar tak ghus jao" jab tak dead-end na aa jaye, phir peeche backtrack karke doosra raasta try karo. Soch lo ek maze ya gufa hai: ek tunnel mein ghuste jao deep, jab aage rasta na bache tab last fork pe wapas aakar naya tunnel pakdo. Yahi "dive, fail, step-back" wala behaviour DFS hai.

Iska engine hota hai stack — LIFO, matlab jo node sabse last visit kiya wahi sabse pehle wapas explore hota hai. Recursion khud ek stack hota hai (call stack), isliye DFS recursive likhna sabse natural hai. Ek cheez bilkul mat bhoolna: visited array. Graph mein cycles hote hain (A→B→C→A), agar visited nahi rakhoge to program infinite loop mein ghoomta rahega. Isliye node ko visited=True mark karo ENTER karte hi — explore function ki pehli line mein.

Complexity rattna mat — derive karo. Har vertex ek baar visit hota hai → V kaam. Har vertex pe uski adjacency list scan hoti hai, sab milake total edges = 2E (undirected, Handshake Lemma) → E kaam. Total = O(V+E). E ki jagah sirf E kyun nahi? Kyunki kuch graph mein vertices hote hain par edges zero — tab bhi har vertex touch karna padta hai, isliye V term zaroori hai. Space O(V) — visited array plus stack depth.

Exam aur interview mein DFS bahut kaam aata hai: connected components count karna, cycle detect karna, topological sort (DFS post-order ulta). Bas teen cheezein yaad rakho — deep jao, visited mark karo entry pe, aur cost V+E gino edges aur nodes ko alag-alag.

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

WHAT is DFS?

WHY a visited array?

HOW it works — derive the complexity from first principles

The algorithm — recursive

The algorithm — iterative (explicit stack)

Worked examples

Recall checkpoints

Forecast-then-Verify

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections