Graph Pattern Guide for LeetCode

More Graphs

How To Graphs

1. Core Graph Templates

Template 1: Graph Representation

# Adjacency List
class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for _ in range(V)]

    def add_edge(self, v1, v2):
        self.adj[v1].append(v2)
        # self.adj[v2].append(v1)  # Uncomment for undirected graph

# Adjacency Matrix
class GraphMatrix:
    def __init__(self, V):
        self.V = V
        self.adj = [[0] * V for _ in range(V)]

Template 2: Basic DFS

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Template 3: Basic BFS

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        vertex = queue.popleft()

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

2. LeetCode Problem Categories

Category 1: Graph Traversal Problems

1. LeetCode 200: Number of Islands

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

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
            return

        # Mark as visited
        grid[i][j] = '#'

        # Check all 4 directions
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1

    return count

1. LeetCode 133: Clone Graph
2. LeetCode 797: All Paths From Source to Target

Category 2: Shortest Path Problems

1. LeetCode 743: Network Delay Time (Dijkstra's)

def networkDelayTime(times, N, K):
    # Create adjacency list with weights
    graph = collections.defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    # Distance dictionary
    distances = {node: float('infinity') for node in range(1, N + 1)}
    distances[K] = 0

    # Priority queue for Dijkstra's
    pq = [(0, K)]  # (distance, node)
    visited = set()

    while pq and len(visited) < N:
        d, node = heapq.heappop(pq)

        if node in visited:
            continue

        visited.add(node)

        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                new_dist = d + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))

    max_distance = max(distances.values())
    return max_distance if max_distance < float('infinity') else -1