Graph Problem Patterns and Templates

Introduction to Graph Problems

Graph problems involve vertices (nodes) and edges (connections) and often require traversing or analyzing the graph to solve optimization, connectivity, or path-finding tasks. Common techniques include Depth-First Search (DFS), Breadth-First Search (BFS), shortest path algorithms, and advanced structures like Union-Find or Priority Queues. Unlike DP or Greedy, graph problems often focus on structural properties (e.g., cycles, connectivity) or path optimization.

Common Graph Patterns

Below are the major graph problem patterns, their characteristics, and templates for solving them.

1. Depth-First Search (DFS)

Description: DFS explores as far as possible along each branch before backtracking, useful for detecting cycles, connected components, or topological sorting in directed acyclic graphs (DAGs).

Examples:

• Number of Islands (LeetCode #200)
• Course Schedule (LeetCode #207)
• Graph Valid Tree (LeetCode #261)

Template (Recursive DFS):

def dfs(graph, node, visited):
    if node in visited:
        return  # Handle cycles or visited nodes
    visited.add(node)
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)
    # Post-processing (e.g., topological sort)

Template (Iterative DFS):

def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

Key Points:

• Use: Cycle detection, connected components, topological sorting.
• Data Structure: Adjacency list or matrix; recursive stack or explicit stack.
• Time Complexity: O(V + E) for adjacency list; O(V²) for adjacency matrix.
• Space Complexity: O(V) for recursion stack or visited set.