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

3.5.5 · Coding › Graphs

DFS KYA HAI?

Do equivalent implementations:

Recursive — program ki implicit call stack use karta hai.
Iterative — ek explicit stack data structure use karta hai.

VISITED ARRAY KYUN?

Yahi ek fact DFS ko exponential ki jagah linear banata hai.

YEH KAISE KAAM KARTA HAI — complexity ko first principles se derive karo

Hum $O (V + E)$ yaad nahi karte. Hum kaam count karte hain.

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

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)

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 — DFS se connected components count karna

Har unvisited vertex se DFS chalao; har fresh launch = ek naya 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 phir bhi $O (V + E)$ hai kyunki saare launches mein har vertex/edge ek baar touch hoti hai. Kyun? Shared visited array saare launches mein kaam karta hai.

Recall checkpoints

Recall Feynman: ek 12-saal ke bacche ko samjhao

Tum ek cave explore kar rahe ho jisme tunnels hain. Tum ek tunnel mein jaate ho aur tab tak aage badhte rehte ho jab tak dead-end na aa jaye. Phir tum wapas last fork par jaate ho aur ek aisa tunnel try karte ho jisme tum abhi nahi gaye. Tum har room mein ek glowstick gir aate ho jisme tum ghuste ho (yahi visited array hai) taaki tum kabhi kisi room ko dobara explore na karo ya circles mein chalte na raho. Kyunki tum exactly ek glowstick per room girate ho aur har tunnel mein fixed number of times chalta ho, poora trip (rooms + tunnels) ke proportional time leta hai — fast!

Forecast-then-Verify

Connections

BFS — Breadth-First Search — same $O (V + E)$ , lekin queue (FIFO) use karta hai → level by level explore karta hai.
Stack data structure — DFS ke backtracking ka engine.
Recursion and the Call Stack — kyun recursive DFS "free mein" kaam karta hai.
Cycle Detection — DFS + recursion-stack coloring.
Topological Sort — DFS post-order reversed.
Connected Components — repeated DFS launches.
Handshake Lemma — kyun $\sum de g (v) = 2 E$ .

Graph explore karte waqt DFS kaunsi strategy follow karta hai?

Ek path par jitna deep ho sake jao, phir last vertex par backtrack karo jiske paas ek unexplored neighbor ho (LIFO).

DFS kaun sa data structure use karta hai (explicit ya implicit)?

Ek stack — iterative DFS mein explicit stack, ya recursive DFS mein implicit call stack.

DFS ko visited array kyun chahiye?

Cycles par infinite loops se bachne ke liye aur yeh ensure karne ke liye ki har vertex exactly ek baar process ho (graphs mein cycles aur multiple paths ho sakte hain).

Recursive DFS mein visited[u]=True kahan set karna chahiye?

explore(u) ki PEHLI line par, neighbors scan karne se pehle, taaki u par wapas cyclic edges block ho jayein.

DFS ki time complexity kya hai aur kyun?

O(V+E): har vertex ek baar visit (V) plus har edge ek baar scan jab uska endpoint process hota hai (sum of degrees = 2E ya E).

Yeh O(V+E) kyun hai aur sirf O(E) kyun nahi?

Ek graph mein bina edges ke vertices ho sakti hain (E=0); phir bhi tumhe har vertex touch karni hai, isliye V term zaroori hai.

DFS ki space complexity kya hai?

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

Iterative DFS mein pop par visited check kyun karo, sirf push par nahi?

Ek vertex ko pop hone se pehle alag-alag neighbors dwara multiple baar push kiya ja sakta hai; pop par check karna ek processing guarantee karta hai.

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

DFS deta hai 0,1,3,2 (pehle deep); BFS deta hai 0,1,2,3 (level by level).

DFS se connected components kaise count karo?

Har abhi-unvisited vertex se ek shared visited array par DFS launch karo; har naya launch = ek naya component.

Kaun sa graph theorem explain karta hai ki edge kaam 2E tak kyun sum hota hai?

Handshake Lemma: ek undirected graph mein saare vertex degrees ka sum 2E ke barabar hota hai.