Graphs

🧠 Spot It

• Input is a network, grid, or dependency structure
• Problem asks for connectivity, shortest path, cycles, ordering
• Keywords: nodes, edges, neighbors, connected components, path

---

Graph Representations

# Adjacency list (most common in interviews)
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

# Build from edge list
from collections import defaultdict
def build_graph(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # remove for directed
    return graph

---

Pattern 1 — DFS (Recursive / Iterative)

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

---

Pattern 2 — BFS (Shortest Path in unweighted graph)

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    distance = {start: 0}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return distance

---

Pattern 3 — Topological Sort (Kahn's Algorithm)

from collections import deque, defaultdict

def topo_sort(n, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    queue = deque([i for i in range(n) if indegree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []  # empty = cycle exists

---

Pattern 4 — Union Find (Disjoint Set)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False  # already connected (cycle)
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

---

Pattern 5 — Dijkstra (Weighted Shortest Path)

import heapq

def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]: continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
    return dist

---

Pattern 6 — Grid DFS / BFS (4-Directional)

Grid = implicit graph. Cells are nodes, adjacent cells are edges.

# LC 200 — Number of Islands
def numIslands(grid):
    rows, cols = len(grid), len(grid[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] = '0'   # mark visited (in-place)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

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

# BFS variant — use when you need shortest path / level distances
def bfs_grid(grid, start_r, start_c):
    from collections import deque
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c, 0)])  # (row, col, dist)
    visited = {(start_r, start_c)}
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

Key: For DFS, mark visited by mutating grid in-place (restore after if needed) OR use a visited set. BFS = shortest path. DFS = connectivity/count.

---

Pattern 7 — Cycle Detection in Directed Graph

Use DFS with a "currently in stack" set. Back edge = cycle.

def hasCycle(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = set()    # fully processed nodes
    in_stack = set()   # current DFS path

    def dfs(node):
        in_stack.add(node)
        for neighbor in graph[node]:
            if neighbor in in_stack:
                return True   # back edge = cycle
            if neighbor not in visited and dfs(neighbor):
                return True
        in_stack.remove(node)
        visited.add(node)
        return False

    return any(dfs(i) for i in range(n) if i not in visited)

Directed vs Undirected: Directed: use in_stack. Undirected: track parent to avoid false cycle from parent edge.

---

Problems