Poridhi: Graph

Graph related problems:

This blog post explores four fundamental problems that test your understanding of graph traversal, depth-first search (DFS), breadth-first search (BFS), and backtracking algorithms. It starts with Number of Islands, where we determine how many separate land masses exist in a 2D grid using DFS. Next is Clone Graph, which involves creating a deep copy of a graph structure using recursion and hash mapping. The Course Schedule problem tackles the concept of topological sorting and cycle detection in a directed graph to determine if all courses can be finished. Lastly, Word Search demonstrates backtracking by checking whether a word exists in a grid by moving in four directions. Together, these problems provide essential practice for mastering graph and grid-based problem-solving techniques.

✅ Number of Islands

(Problem: Count connected land areas in a 2D grid)

def numIslands(grid):
    if not grid:
        return 0

    def dfs(r, c):
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

---

✅ Clone Graph

(Problem: Deep copy a graph where nodes have neighbors)

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

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 neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node)

---

✅ Course Schedule

(Problem: Detect if all courses can be completed, cycle detection in graph)

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return completed == numCourses

---

✅ Word Search

(Problem: Check if a word exists in the grid by backtracking)

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False

        temp = board[r][c]
        board[r][c] = '#'
        res = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or 
               dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = temp
        return res

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False