Steps to Solve Graph Problems

General Steps for Solving Graph Problems

Understand the Problem and Constraints:
- Read the problem to identify the input (e.g., adjacency list, matrix, edge list), output (e.g., path length, connectivity, order), and constraints (e.g., number of nodes/edges, directed/undirected, weighted/unweighted).
- Determine the problem type: connectivity (e.g., number of components), path-finding (e.g., shortest path), cycle detection, or ordering (e.g., topological sort).
- Example: For LeetCode #200 (Number of Islands), the input is a grid, and the output is the number of connected land components.
Identify the Graph Pattern:
- Match the problem to a known graph pattern (e.g., DFS, BFS, Shortest Path, MST, Topological Sort, Union-Find, Graph Coloring, Cycle Detection, SCC).
- Look for clues:
  - Connectivity/components → DFS, BFS, or Union-Find.
  - Shortest path → BFS (unweighted), Dijkstra’s (weighted), Bellman-Ford (negative weights).
  - Ordering in DAG → Topological Sort.
  - Cycle detection → DFS or Union-Find.
- Example: For Course Schedule (LeetCode #207), the need to check prerequisites suggests a DAG and cycle detection, pointing to Topological Sort or DFS.
Model the Problem as a Graph:
- Determine the graph representation:
  - Nodes: What do nodes represent? (e.g., grid cells, cities, courses).
  - Edges: What do edges represent? (e.g., adjacency, prerequisites, distances).
  - Type: Directed/undirected, weighted/unweighted.
- Choose a data structure:
  - Adjacency list for sparse graphs (O(V + E) space).
  - Adjacency matrix for dense graphs or grid problems (O(V²) space).
  - Edge list for MST or Union-Find problems.
- Example: In Word Ladder (LeetCode #127), nodes are words, and edges connect words differing by one character.
Define the Algorithmic Approach:
- Select the appropriate algorithm based on the pattern:
  - DFS: For connectivity, cycles, or topological sort.
  - BFS: For shortest paths in unweighted graphs or level-order traversal.
  - Dijkstra’s/Bellman-Ford: For shortest paths in weighted graphs.
  - Kruskal’s/Prim’s: For MST.
  - Union-Find: For connected components or cycle detection.
- Example: For Network Delay Time (LeetCode #743), use Dijkstra’s for shortest paths from a source in a weighted graph.
Formulate the State or Objective:
- Define what you’re computing:
  - Connectivity: Number of components or whether nodes are connected.
  - Path: Shortest distance, path existence, or actual path.
  - Order: Valid ordering of nodes (e.g., topological sort).
- For DP-based graph problems (e.g., TSP), define states like dp[pos][mask] for visited nodes.
- Example: In Number of Islands, the objective is to count distinct connected components of land cells.
Design the Algorithm:
- Write pseudocode or a high-level plan:
  - Initialize data structures (e.g., visited set, queue, heap, Union-Find).
  - Process nodes/edges using the chosen algorithm (e.g., DFS, BFS, Dijkstra’s).
  - Handle edge cases (e.g., empty graph, disconnected components).
- Example: For Number of Provinces (LeetCode #547):
```
Initialize UnionFind with n nodes
For each edge (i, j) in adjacency matrix:
    Union(i, j)
Count unique parents to get number of provinces
```
Optimize Time and Space:
- Optimize traversal: Use adjacency lists for sparse graphs, sets for O(1) lookups.
- Reduce space: Use in-place modifications (e.g., mark grid cells in Number of Islands) or reuse arrays.
- Example: In BFS for Rotting Oranges (LeetCode #994), use the grid itself to track rotting states, reducing space to O(1).
Implement the Solution:
- Use appropriate data structures (e.g., deque for BFS, heap for Dijkstra’s, Union-Find for components).
- Handle constraints like large graphs or negative weights.
- Example: For Is Graph Bipartite? (LeetCode #785):

from collections import deque
def isBipartite(graph):
    n = len(graph)
    colors = [-1] * n  # -1: uncolored, 0: color1, 1: color2
    for start in range(n):
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]
                    queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True

Test and Debug:
- Test with small inputs to verify logic (e.g., single node, small grid).
- Check edge cases: empty graph, disconnected components, cycles.
- Debug issues: incorrect edge traversal, missing components, or cycle detection errors.
- Example: For Course Schedule, test numCourses = 2, prerequisites = [[1,0]] (valid) and [[1,0],[0,1]] (cycle).
Formulate the Answer:
- Return the result in the required format (e.g., integer, list, boolean).
- Ensure output matches the problem’s requirements (e.g., -1 for unreachable paths).

How to Think of a Solution

Thinking through a graph solution involves modeling the problem, recognizing patterns, and selecting the right algorithm. Here’s how to approach it:

Model the Problem as a Graph:
- Identify nodes and edges:
  - Nodes: Entities like cities, courses, or grid cells.
  - Edges: Relationships like roads, prerequisites, or adjacency.
- Example: In Word Ladder (LeetCode #127), words are nodes, and edges connect words differing by one character.
- Ask: Is the graph directed, weighted, or cyclic? This guides the algorithm choice.
Pattern Recognition:
- Match the problem to a graph pattern:
  - Connectivity: DFS, BFS, or Union-Find (e.g., Number of Provinces).
  - Shortest Path: BFS (unweighted), Dijkstra’s (weighted), Bellman-Ford (negative weights).
  - Cycle Detection: DFS (directed), Union-Find (undirected).
  - Ordering: Topological Sort for DAGs.
  - Coloring: BFS/DFS for bipartite graphs.
- Example: If the problem involves scheduling with dependencies (e.g., LeetCode #210), think Topological Sort.
Ask Key Questions:
- What is the goal? (e.g., count components, find shortest path, detect cycle).
- What is the graph type? (e.g., directed, weighted, grid-based).
- Do I need to visit all nodes or a subset? (e.g., all components vs. single-source path).
- Are there constraints like negative weights or cycles?
- Example: In Network Delay Time (LeetCode #743), ask: “What’s the shortest time to reach all nodes from a source in a weighted graph?”
Test Intuition with Examples:
- Use small test cases to simulate the algorithm:
- Check for overlapping subproblems (DP) vs. single-pass solutions (Greedy or BFS).
- Example: In Rotting Oranges, simulate rotting with a small grid to verify BFS level-order spread.
Contrast with DP and Greedy: