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 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)

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  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` 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**
- "Order of dependencies" or "prerequisite chain"
- "Is the directed graph a DAG?"
- "Process tasks in valid order"
- Build systems, course scheduling, compilation order

**Core Idea**

Topological sort produces a linear ordering of vertices such that for every directed edge (u, v), u appears before v. It only exists for DAGs. Kahn's algorithm (BFS-based) processes zero-indegree nodes iteratively and naturally detects cycles when the output is shorter than V. DFS-based topo sort appends nodes in reverse finish order.

**Kahn's Algorithm (BFS)**

```python
from collections import deque

def topological_sort_kahn(graph: dict[int, list[int]], n: int) -> list[int] | None:
    """Return topo order for n nodes (0-indexed), or None if cycle exists."""
    indegree: list[int] = [0] * n
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1
    queue: deque[int] = deque(v for v in range(n) if indegree[v] == 0)
    order: list[int] = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else None

For DFS-based topo sort, use WHITE/GRAY/BLACK coloring. Append nodes to the order when they turn BLACK (all descendants processed), then reverse. A GRAY-to-GRAY back edge indicates a cycle.

Key Edge Cases

• Multiple valid orderings: Kahn's with a min-heap gives lexicographically smallest
• Isolated nodes (no edges): appear anywhere in the ordering
• Self-loops: always indicate a cycle
• Empty graph: returns empty list (valid)

Common Mistakes

• Forgetting to initialize indegree for nodes with no incoming edges
• Using Kahn's but not checking len(order) == n for cycle detection
• DFS-based: forgetting to reverse the order at the end

---

Union-Find (Disjoint Set Union)

Recognition Signals

• "Are nodes X and Y connected?" with dynamic edge additions
• "Number of connected components" after a series of merges
• "Detect cycle in an undirected graph"
• "Group" or "cluster" elements incrementally

Core Idea

Union-Find maintains a forest of disjoint sets. Each element has a parent, and the root of the tree is the set representative. Path compression flattens the tree during find, and union by rank keeps the tree balanced. Together they achieve nearly O(1) amortized per operation. To detect a cycle in an undirected graph, check if both endpoints of an edge share the same root before merging.

Python Template

class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent: list[int] = list(range(n))
        self.rank: list[int] = [0] * n
        self.components: int = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        """Merge sets of x and y. Return False if already in same set."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx]  list[tuple[int, int, int]]:
    """Return MST edges. edges = [(weight, u, v), ...]. Returns [] if disconnected."""
    edges.sort()
    uf = UnionFind(n)  # uses UnionFind class from above
    mst: list[tuple[int, int, int]] = []
    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((weight, u, v))
            if len(mst) == n - 1:
                break
    return mst if len(mst) == n - 1 else []

Prim's Algorithm

import heapq

def prim(graph: dict[int, list[tuple[int, int]]], n: int) -> int:
    """Return total MST weight. graph[u] = [(v, weight), ...]. -1 if disconnected."""
    visited: set[int] = {0}
    heap: list[tuple[int, int]] = [(w, v) for v, w in graph.get(0, [])]
    heapq.heapify(heap)
    total = 0
    while heap and len(visited)  list[float] | None:
    """Return distances from start, or None if negative cycle exists.
    edges = [(u, v, weight), ...]."""
    dist: list[float] = [float("inf")] * n
    dist[start] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w  bool:
    """Check if graph with n nodes (0-indexed) is bipartite."""
    color: list[int] = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue: deque[int] = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph.get(node, []):
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

To extract the two partitions, collect nodes by their color value after a successful check: group_a = [v for v in range(n) if color[v] == 0].

Key Edge Cases

• Disconnected graph: each component must be independently bipartite
• Self-loops: immediately make the graph non-bipartite
• Single node with no edges: trivially bipartite
• Tree: always bipartite (no cycles, so no odd cycles)

Common Mistakes

• Only checking one connected component instead of all
• Forgetting that self-loops violate bipartiteness
• Using DFS coloring but not checking the back-edge color correctly

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: sequenzia
• Source: sequenzia/agent-alchemy
• License: MIT
• Homepage: https://sequenzia.github.io/agent-alchemy

Install and usage instructions live in the source repository linked above.