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

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->