Graphs

Graph questions usually ask about reachability, shortest distance, or dependencies. First decide what a node represents and which transitions are legal; the input need not explicitly contain a graph.

1. Model the State and Choose a Traversal

A node can be a person, a grid cell, a word, or a complete search state. If future moves depend on keys collected, (row, column) is insufficient: use (row, column, key_mask). Otherwise, marking a cell visited can incorrectly discard a useful route.

With vertices 0..V-1, initialize V adjacency lists, including isolated nodes. Add both directions for an undirected edge. Adjacency lists use $O(V+E)$ space and visit neighbors in degree-proportional time; a matrix uses $O(V^2)$ space and scans $V$ entries per vertex. Count graph construction and generated neighbors in the runtime.

2. Reachability and Connected Components

The visited set contains every vertex already discovered, including those waiting to be processed. Mark when pushing, so multiple incoming edges do not duplicate work.

def component_sizes(graph):
    seen = set()
    sizes = []
    for start in range(len(graph)):
        if start in seen:
            continue
        seen.add(start)
        stack = [start]
        size = 0
        while stack:
            node = stack.pop()
            size += 1
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    stack.append(neighbor)
        sizes.append(size)
    return sizes

This assumes an undirected graph. Each outer-loop launch discovers one entire component; the shared set prevents launching it again. Total time is $O(V+E)$, auxiliary space $O(V)$. An adjacency-matrix input, as in Number of Provinces, instead requires $O(V^2)$ scanning.

Directed reachability is not symmetric. To test whether every vertex can reach every other vertex, choose one start and check that it reaches all vertices in both the original graph and the graph with every edge reversed. A component loop alone does not compute strongly connected components.

3. Shortest Paths and Multiple Sources

from collections import deque

def shortest_distances(graph, sources):
    distance = {node: 0 for node in sources}
    parent = {node: None for node in distance}
    queue = deque(distance)
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                parent[neighbor] = node
                queue.append(neighbor)
    return distance, parent

For a single start, pass [start]. The queue processes distance d before d+1, so a vertex's first discovery gives its shortest unweighted distance. Missing vertices are unreachable. Follow parent backward from a target to a source and reverse that sequence to reconstruct a path; this takes time and output space proportional to path length.

For nearest exit, nearest facility, or simultaneous spread, enqueue all sources initially. The same proof gives distance to the nearest source in $O(V+E)$ time, rather than running a separate BFS for each source. Compare Rotting Oranges. Each distinct source is enqueued once.

4. State That Changes the Answer

• Cloning: Clone Graph needs original_node -> cloned_node, not just a visited flag. Create and record the clone before traversing neighbors; this preserves shared neighbors and terminates on cycles. Key by node identity, not a potentially repeated value.
• Cycle detection: in a directed DFS, distinguish unseen, active on the current path, and finished. An edge to an active node proves a cycle; an edge to a finished node does not. In an undirected simple graph, ignore the edge back to the parent. Parallel edges require edge IDs for that rule.
• Grid graphs: generate neighbors from legal moves instead of constructing an adjacency list. R*C cells with bounded-degree movement give $O(RC)$ traversal; extra state such as a key mask multiplies that bound.
• Shortest path versus all paths: global visited state is correct for reachability/BFS. Enumerating simple paths needs path-local visited state that is undone between branches; that search may be exponential.

5. Key Takeaways

• Mark a vertex when it is enqueued or pushed, and reuse visited state across component searches.
• Use one BFS with all exits as sources for distance to the nearest exit.
• Include every variable affecting legal next moves in the visited key.
• A FIFO queue guarantees fewest edges, not lowest weighted cost. Recursive DFS can use $O(V)$ call-stack depth.

Continue to Topological Sort for dependencies and DAG paths, Backtracking for enumerating paths, and Heaps before studying weighted shortest paths.