# Graph Algorithms

> >-

- **Type:** Skill
- **Install:** `agentstack add skill-sequenzia-agent-alchemy-graph-algorithms`
- **Verified:** Yes — security-reviewed for prompt injection and unsafe behavior
- **Seller:** [sequenzia](https://agentstack.voostack.com/s/sequenzia)
- **Installs:** 0
- **Category:** [Agent Skills](https://agentstack.voostack.com/c/agent-skills)
- **Latest version:** 0.1.0
- **License:** MIT
- **Upstream author:** [sequenzia](https://github.com/sequenzia)
- **Source:** https://github.com/sequenzia/agent-alchemy/tree/main/claude/cs-tools/skills/graph-algorithms
- **Website:** https://sequenzia.github.io/agent-alchemy

## Install

```sh
agentstack add skill-sequenzia-agent-alchemy-graph-algorithms
```

Requires the [AgentStack CLI](https://agentstack.voostack.com/docs/cli). Works with Claude Code, Cursor, and any MCP-compatible agent.

## About

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

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

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

```python
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](https://github.com/sequenzia)
- **Source:** [sequenzia/agent-alchemy](https://github.com/sequenzia/agent-alchemy)
- **License:** MIT
- **Homepage:** https://sequenzia.github.io/agent-alchemy

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

## Pricing

- **Free** — Free

## Security capabilities

Automated source analysis of v0.1.0 — what this tool can access:

- **Network access:** no
- **Filesystem access:** no
- **Shell / process execution:** no
- **Environment & secrets:** no
- **Dynamic code execution:** no

*"Yes" means the capability is present in the source — more access means more to trust, not that it is unsafe.*


## Versions

- **0.1.0** — security scan: passed — Imported from the upstream source.

## Links

- Listing page: https://agentstack.voostack.com/l/skill-sequenzia-agent-alchemy-graph-algorithms
- Seller: https://agentstack.voostack.com/s/sequenzia
- Browse the marketplace: https://agentstack.voostack.com/browse

---
Listed on AgentStack — the marketplace for AI agent skills and MCP servers. Every listing is security-reviewed. Creators keep 70%.