BFS and DFS Graph Traversal in Hindi (Hinglish)

Hindi mein samjho (Hinglish)

Neeche is topic ka Hinglish explanation hai, wahi jo hamare course lesson mein audio narration ke saath chalta hai. Code English mein hai, samjhana Hindi mein.

Number of Islands

Number of Islands ek textbook problem hai interview ke sabse zyada reuse hone waale ideas mein se ek ke liye: ek 2D grid actually ek graph hi hai disguise mein. Har cell ek node hai, har horizontal ya vertical neighbour ek edge hai, aur islands count karna basically connected components count karna hai. Yeh lens yahan lock kar lo to ek darjan LeetCode problems same template mein collapse ho jaate hain.

Pattern: implicit graph pe connected components, jahan graph ek 2D grid hai 4-direction adjacency ke saath. Disguise: koi bhi problem jo regions count karne, region ka size nikalne, do cells reach kar sakte hain ya nahi decide karne, ya kisi starting cell se flood-fill karne ko bole. Fingerprints hain ek 2D matrix, neighbour rules, aur ek sawaal jo iss baat pe depend kare ki kaunse cells kaunse cells se reachable hain. Same template, different sawaal.

Unlock do parts mein hai. Pehla: grid ke har cell ko row-major order mein walk karo; sirf tab DFS kick off karo jab tum ek 1 pe land karo jo abhi tak visit nahi hua. Wo ek launched DFS poora ek island hai; count ek baar bump karo aur DFS ko poori region nigal lene do. Doosra: alag visited matrix ke bajaay, har visit ki hui land cell ko ek sentinel jaise hash se overwrite kar do, taaki same cell dobara count na ho. Result ek O(M times N) sweep hai jahan har cell at most do baar touch hota hai: ek baar bahar ke scan se, ek baar kisi DFS se.

Python solution: Number of Islands

def numIslands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '#'
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Complexity: Brute force (DFS per land cell + frozenset dedupe): time O((M · N)²) worst case, space O(M · N); Brute force (DFS per land cell + frozenset dedupe): time O((M·N)²), space O(M·N); DFS + in-place mark (optimal): time O(M·N), space O(M·N) worst case; BFS + queue (optimal, deeper grids): time O(M·N), space O(min(M,N)).

Clone Graph

Clone Graph wo medium graph problem hai jo ek transferable trick sikhata hai. Graph mein cycles hain, isliye naive walk hamesha loop karta rehta hai. Fix hai original node ko key banakar ek hash map: yeh ek saath do sawaal answer karta hai: kya maine yeh node clone kar liya hai, aur agar haan toh clone kahan hai. Yeh idea sahi aa gaya toh code khud likh jaata hai bees lines ke andar.

Pattern hai identity mapping for graph-style cloning. Jab bhi tumhe ek structure deep-clone karna ho jahan pointers ek graph banate hain, undirected edges, directed edges, random pointers, parent pointers, tum ek hash map rakhte ho original node object se clone tak. Map "kya maine yeh node pehle dekha hai?" sawaal ko constant-time lookup mein badal deta hai, aur yahi cycle problem ko maarta hai.

Unlock ek line ka hai: visited set aur new-node array ko ek hi hash map mein combine karo, original node se uske clone tak. Ab DFS trivial ho jaata hai. Agar node map mein already hai, existing clone return karo. Warna clone allocate karo, map mein turant store karo taaki cycles terminate ho, phir har neighbour pe recurse karo aur returned clone ko new neighbours list mein append karo. Bas yahi pura algorithm hai.

Python solution: Clone Graph

def cloneGraph(node):
    if not node:
        return None
    old_to_new = {}

    def dfs(n):
        if n in old_to_new:
            return old_to_new[n]
        copy = Node(n.val)
        old_to_new[n] = copy
        for nb in n.neighbors:
            copy.neighbors.append(dfs(nb))
        return copy

    return dfs(node)

Complexity: Pseudo-brute (BFS + index array + second wiring pass): time O(V + E), space O(V).

Course Schedule

Welcome to Course Schedule. Framing clever hai, courses with prerequisites, par asli sawaal hai "kya is directed graph mein cycle hai?" Agar yeh paanch minute mein solve kar liya, tumne ek pura category unlock kar liya: topological sort, dependency resolution, build order, schedule planning. Sab variations hain isi exact skeleton ke.

Pehle pattern pehchano. Jab bhi dekho "tasks with dependencies", "build order", "compile order", ya "kya yeh kisi sequence mein schedule ho sakte hain": yeh cycle detection in a directed graph hai, equivalently "kya topological ordering exist karta hai?" Do standard tools handle karte hain: DFS three colours ke saath, ya Kahn's BFS indegrees use karke. Koi bhi chuno: dono O of V plus E hain.

Do beautiful unlocks. Pehla: DFS three colour. White matlab unvisited, gray matlab current recursion stack par hai, black matlab fully done. Agar DFS kabhi gray node mein step kar gaya, tumne back edge dhoondh liya: wahi cycle hai. Doosra: Kahn's BFS. Baar baar koi bhi zero incoming edges waala node uthao, hatao, aur uske neighbours ka indegree decrement karo. Saare hat gaye, no cycle. Dono O of V plus E mein chalte hain.

Python solution: Course Schedule

from collections import deque

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)        # edge b → a: do b before a
        indeg[a] += 1
    queue = deque(i for i in range(numCourses) if indeg[i] == 0)
    done = 0
    while queue:
        node = queue.popleft()
        done += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return done == numCourses

Complexity: Brute force (DFS restart from every node): time O(V × (V + E)), space O(V + E); Kahn's BFS (or DFS three-colour): time O(V + E), space O(V + E).