graph-algorithms

What this skill does

# 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**

```python
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)**

```python
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)**

```python
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**

```python
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*