graph-algorithms

Graph Algorithm Patterns

Graph problems appear frequently in competitive programming and technical interviews. The key challenge is recognizing which technique fits the problem structure. This reference covers eight core patterns with recognition heuristics, templates, and pitfall guides.

Pattern Recognition Table

| Trigger Signals | Technique | Typical Complexity | |---|---|---| | Shortest path, unweighted, fewest steps | BFS | O(V + E) | | Explore all paths, connected components, backtracking | DFS | O(V + E) | | Shortest path, weighted (non-negative) | Dijkstra | O((V + E) log V) | | Dependencies, ordering, DAG | Topological Sort | O(V + E) | | Dynamic connectivity, "are X and Y connected?" | Union-Find (DSU) | O(alpha(N)) per op | | Minimum cost to connect all nodes | MST (Kruskal/Prim) | O(E log E) | | Weighted shortest path with negative edges | Bellman-Ford | O(V * E) | | Two groups, coloring, odd cycle | Bipartite Check | O(V + E) |

Constraint-to-Technique Mapping

Use V (vertices) and E (edges) bounds to narrow viable algorithms:

| Constraint Range | Viable Techniques | Notes | |---|---|---| | V <= 20 | Bitmask DP, brute-force BFS/DFS | Exponential OK | | V <= 1,000, E <= 10,000 | All techniques, Floyd-Warshall for APSP | O(V^3) still feasible | | V <= 100,000, E <= 200,000 | BFS, DFS, Dijkstra, Topo Sort, DSU, MST | Standard competitive range | | V <= 1,000,000 | BFS, DFS, DSU, Kahn's | Avoid O(V log V) heaps if possible | | Negative weights present | Bellman-Ford, SPFA | Dijkstra invalid | | Dense graph (E ~ V^2) | Prim (adj matrix), Floyd-Warshall | Adjacency list Dijkstra still works | | Edges arrive online | Union-Find | Incremental connectivity |

Individual Patterns

BFS (Breadth-First Search)

Recognition Signals

• "Shortest path" or "minimum steps" in an unweighted graph or grid
• "Level-order traversal" or "distance from source"
• Multiple starting points (multi-source BFS)
• "Nearest" something in a grid

Core Idea

BFS explores nodes layer by layer from the source, guaranteeing that the first time a node is reached, it is via the shortest path (in terms of edge count). Use a queue (FIFO) to process nodes in discovery order. Multi-source BFS initializes the queue with all sources at distance 0, treating them as a virtual super-source.

Python Template

from collections import deque

def bfs_shortest_path(graph: dict[int, list[int]], start: int) -> dict[int, int]:
    """Return shortest distance from start to all reachable nodes."""
    dist: dict[int, int] = {start: 0}
    queue: deque[int] = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

For multi-source BFS, initialize dist and queue with all sources at distance 0 instead of a single start node.

Key Edge Cases

• Disconnected graph: unreachable nodes never appear in dist
• Self-loops: handled naturally (node already visited)
• Start node with no edges: returns {start: 0}
• Grid BFS: encode (row, col) as queue elements, check bounds before enqueue

Common Mistakes

• Using a list as a queue (.pop(0) is O(N); use deque)
• Marking visited after popping instead of before enqueuing (causes duplicates)
• Forgetting to handle the case where start == target

DFS (Depth-First Search)

Recognition Signals

• "Find all connected components" or "is there a path?"
• "Cycle detection" in directed or undirected graphs
• "Enumerate all paths" or backtracking required
• Tree traversal (pre-order, post-order, in-order)

Core Idea

DFS explores as deep as possible along each branch before backtracking. It naturally discovers connected components, detects cycles, and computes entry/exit times useful for subtree queries. Use iterative DFS with an explicit stack for large graphs to avoid Python's recursion limit.

Python Template (Iterative)

def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    """Return all nodes reachable from start in DFS order."""
    visited: set[int] = set()
    stack: list[int] = [start]
    order: list[int] = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return order

Cycle Detection (Directed Graph)

def has_cycle_directed(graph: dict[int, list[int]], n: int) -> bool:
    """Detect cycle in a directed graph with n nodes (0-indexed)."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color: list[int] = [WHITE] * n
    for start in range(n):
        if color[start] != WHITE:
            continue
        stack: list[tuple[int, int]] = [(start, 0)]
        color[start] = GRAY
        while stack:
            node, idx = stack.pop()
            if idx < len(graph.get(node, [])):
                stack.append((node, idx + 1))
                neighbor = graph[node][idx]
                if color[neighbor] == GRAY:
                    return True
                if color[neighbor] == WHITE:
                    color[neighbor] = GRAY
                    stack.append((neighbor, 0))
            else:
                color[node] = BLACK
    return False

Key Edge Cases

• Self-loops count as cycles in directed graphs
• Undirected cycle detection must skip the parent edge (not just visited check)
• Single-node graph with no edges has no cycle
• Disconnected graph: must start DFS from every unvisited node

Common Mistakes

• Hitting Python recursion limit on deep graphs (use sys.setrecursionlimit or iterative)
• Confusing undirected vs directed cycle detection logic
• Forgetting to handle disconnected components (only running DFS from node 0)

Dijkstra's Algorithm

Recognition Signals

• "Shortest path" with weighted edges (non-negative weights)
• "Minimum cost to reach target"
• Grid with varying movement costs
• "Cheapest" route or "minimum total weight"

Core Idea

Dijkstra greedily expands the closest unvisited node using a min-heap. Each node is finalized when popped from the heap, and relaxation updates neighbor distances. It fails with negative edge weights because a finalized node's distance may later be improvable. The 0-1 BFS variant handles graphs where edges have weight 0 or 1 using a deque instead of a heap.

Python Template

import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    """Return shortest distance from start. graph[u] = [(v, weight), ...]."""
    dist: dict[int, int] = {start: 0}
    heap: list[tuple[int, int]] = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float("inf")):
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float("inf")):
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

For 0-1 BFS (weights are only 0 or 1), use a deque: appendleft for weight-0 edges, append for weight-1 edges. This avoids the heap overhead and runs in O(V + E).

Key Edge Cases

• Unreachable nodes: never appear in dist
• Multiple edges between same pair: all are considered during relaxation
• Zero-weight edges: Dijkstra handles them, but 0-1 BFS is faster when applicable
• Very large weights: use float("inf") sentinel, not a magic number

Common Mistakes

• Not skipping stale heap entries (the if d > dist guard is essential)
• Using Dijkstra with negative weights (silently gives wrong answers)
• Storing visited set and skipping revisits without the distance check

Topological Sort

Recognition Signals