Most Planning Problems Are Graph Problems

Take a typical case, made up for illustration. A team kept the deploy order for 30 services on a wiki page. It was out of date, and when someone wrote a script to generate it, the script hung. Pricing called Promotions, Promotions called Catalogue, and Catalogue had recently started calling Pricing. Nobody had drawn that loop, so nobody had seen it.

Dependencies, networks, workflows and call chains are all graphs, and most questions about them are answered by one of two traversals. BFS explores in layers and finds fewest-hop paths; DFS goes deep and gives you ordering and cycle detection. Below is when to use each, topological sort, cycle detection, and the representation choices that keep them fast.

If your dependencies live in a wiki page
  • You used DFS for shortest path and got a wrong answer that "looked right"
  • You can't write topological sort from scratch
  • You can't explain three-colour DFS for cycle detection in a directed graph
  • Your "BFS" uses a Stack instead of a Queue and you didn't notice for weeks

BFS, DFS and What Each Is For

Both BFS and DFS visit every vertex once and every edge once → O(V + E). The difference is the data structure that holds the frontier:

  • BFS uses a Queue (FIFO) → expands the closest unexplored vertices first → finds shortest path by edge count.
  • DFS uses a Stack (LIFO, often the call stack) → goes deep before wide → naturally produces discovery/finish times used by topo sort, SCC, and articulation-point algorithms.

flowchart LR
    G["Graph problem"] --> Q1{"Shortest path?"}
    Q1 -->|unweighted| BFS["BFS<br/>Queue, levels"]
    Q1 -->|weighted +| DJK["Dijkstra<br/>(min-heap)"]
    Q1 -->|no| Q2{"Need ordering?"}
    Q2 -->|yes| TOPO["DFS topo sort<br/>or Kahn's BFS"]
    Q2 -->|no| Q3{"Cycle detection?"}
    Q3 -->|yes| DFS3["DFS 3-colour<br/>WHITE/GRAY/BLACK"]
    Q3 -->|no| CC["BFS or DFS<br/>(connected components)"]

    style BFS fill:#0078D4,color:#fff,stroke:#005a9e
    style DFS3 fill:#dc2626,color:#fff,stroke:#b91c1c

Traversals, Topological Sort and Cycles

Step 1: Adjacency list — the only representation you need

// For nearly every real-world graph (sparse, |E| ≪ |V|²): adjacency list
var graph = new Dictionary<int, List<int>>();
void AddEdge(int u, int v)
{
    if (!graph.ContainsKey(u)) graph[u] = new();
    if (!graph.ContainsKey(v)) graph[v] = new();   // include for "directed" too
    graph[u].Add(v);
    // graph[v].Add(u);   ← uncomment for undirected
}

// Adjacency matrix (bool[V,V]): use only when V is small (< 1000)
// and the graph is dense (|E| ~ V²)

Step 2: BFS — shortest path in unweighted graphs

public static Dictionary<int, int> BFSDistances(Dictionary<int, List<int>> g, int source)
{
    var dist = new Dictionary<int, int> { [source] = 0 };
    var q = new Queue<int>();
    q.Enqueue(source);
    while (q.Count > 0)
    {
        var u = q.Dequeue();
        foreach (var v in g.GetValueOrDefault(u) ?? new())
        {
            if (dist.ContainsKey(v)) continue;
            dist[v] = dist[u] + 1;
            q.Enqueue(v);
        }
    }
    return dist;   // vertex -> hop count; unreachable vertices are absent
}

Step 3: DFS — recursive and iterative

// Recursive — clean, blows the stack on adversarial input
public static void DFS(Dictionary<int, List<int>> g, int u, HashSet<int> seen)
{
    if (!seen.Add(u)) return;
    foreach (var v in g.GetValueOrDefault(u) ?? new()) DFS(g, v, seen);
}

// Iterative — safe for any depth
public static void DFSIter(Dictionary<int, List<int>> g, int start)
{
    var seen = new HashSet<int>();
    var stack = new Stack<int>();
    stack.Push(start);
    while (stack.Count > 0)
    {
        var u = stack.Pop();
        if (!seen.Add(u)) continue;
        foreach (var v in g.GetValueOrDefault(u) ?? new())
            if (!seen.Contains(v)) stack.Push(v);
    }
}

Step 4: Topological sort — Kahn's algorithm (BFS-flavoured)

// For DAGs only. Returns a linear order respecting all edges, or null if a cycle exists.
public static List<int>? TopoSort(Dictionary<int, List<int>> g)
{
    var indeg = g.Keys.ToDictionary(k => k, _ => 0);
    foreach (var (_, vs) in g) foreach (var v in vs) indeg[v] = indeg.GetValueOrDefault(v) + 1;

    var q = new Queue<int>(indeg.Where(kv => kv.Value == 0).Select(kv => kv.Key));
    var order = new List<int>();
    while (q.Count > 0)
    {
        var u = q.Dequeue();
        order.Add(u);
        foreach (var v in g.GetValueOrDefault(u) ?? new())
            if (--indeg[v] == 0) q.Enqueue(v);
    }
    return order.Count == indeg.Count ? order : null;   // null = cycle exists
}

Step 5: Cycle detection in directed graphs — three-colour DFS

// WHITE = unvisited, GRAY = on current DFS path, BLACK = fully processed
// A back-edge to a GRAY vertex == cycle.
enum Color { White, Gray, Black }

public static bool HasCycle(Dictionary<int, List<int>> g)
{
    var color = g.Keys.ToDictionary(k => k, _ => Color.White);
    bool Dfs(int u)
    {
        color[u] = Color.Gray;
        foreach (var v in g.GetValueOrDefault(u) ?? new())
        {
            if (color.GetValueOrDefault(v) == Color.Gray) return true;        // back-edge
            if (color.GetValueOrDefault(v) == Color.White && Dfs(v)) return true;
        }
        color[u] = Color.Black;
        return false;
    }
    return g.Keys.Any(u => color[u] == Color.White && Dfs(u));
}

// For undirected graphs: a back-edge that isn't to the parent == cycle.
// Track parent and ignore it.

Step 6: Connected components / flood-fill

public static List<List<int>> ConnectedComponents(Dictionary<int, List<int>> g)
{
    var seen = new HashSet<int>();
    var components = new List<List<int>>();
    foreach (var start in g.Keys)
    {
        if (seen.Contains(start)) continue;
        var component = new List<int>();
        var q = new Queue<int>(); q.Enqueue(start); seen.Add(start);
        while (q.Count > 0)
        {
            var u = q.Dequeue();
            component.Add(u);
            foreach (var v in g.GetValueOrDefault(u) ?? new())
                if (seen.Add(v)) q.Enqueue(v);
        }
        components.Add(component);
    }
    return components;
}

How Traversals Go Wrong

1. DFS for shortest path. DFS finds a path; not necessarily the shortest. Use BFS for unweighted shortest path, Dijkstra for weighted with non-negative edges, Bellman-Ford for negative edges.

2. Forgetting to mark visited at enqueue time. Marking only at dequeue lets the same vertex be enqueued once per incoming edge, so the queue holds O(E) entries instead of O(V), which is O(V²) on a dense graph. Mark when pushing to the BFS queue. (Iterative DFS is the exception: to get true depth-first order, mark at pop, as Step 3 does.)

3. Recursive DFS on a chain of 100k nodes. Stack overflow. Default to iterative DFS unless you can prove the depth is logarithmic.

4. Stack vs Queue confusion. Swapping Stack for Queue turns BFS into DFS silently — the algorithm still terminates, but distances are wrong. Name your collections clearly.

5. Cycle detection in undirected graphs using directed-graph rules. Every undirected edge looks like a back-edge if you don't track the parent. Pass the parent into the recursive call and skip it.

6. Adjacency matrix for sparse graphs. A bool[10000, 10000] is 100 MB; an adjacency list with a few thousand edges is a few KB. Use a matrix only for dense graphs with V < 1000.

How I Approach Graph Problems

  • Adjacency list (Dictionary<int, List<int>>) is the right default. Matrices only for dense, small graphs.
  • BFS for unweighted shortest path and level-order processing. Queue. Mark visited on enqueue.
  • DFS for ordering (topo sort), cycle detection (three-colour), articulation points, SCC. Stack or recursion.
  • Recursive DFS only when depth is bounded; iterative DFS otherwise.
  • Topological sort: Kahn's (BFS) is easier to reason about; DFS-based is shorter.
  • Cycle detection in directed graphs: three-colour DFS. In undirected: BFS/DFS with parent tracking.
  • For weighted shortest paths, jump straight to Dijkstra / A* / Bellman-Ford. Don't try to coerce BFS.

Graphs in Real Systems

Most engineers meet graphs through interview questions, and then spend years not noticing them at work. Dependency resolution, build systems, workflow engines, permission hierarchies, service call maps and agent plans are all graphs. Knowing that gives you a standard answer and saves you from writing a fragile custom one.

Topological sort is the one you'll use most. Any time you ask "what order should I run these in?", you have a directed acyclic graph. Build tools, database migrations and DAG-based agent planners all rely on it. Kahn's algorithm is the practical form, because it can show you which tasks can run in parallel at each level, and it detects cycles as a side effect: if nodes remain and none has zero in-degree, there's a cycle. The leftover nodes are the cycle plus everything downstream of it, so run a DFS over them to name the loop itself.

Graphs that don't fit in memory

An in-memory traversal works for thousands of nodes. For real data at scale, you have other options. Postgres can walk a graph with a recursive CTE, which is enough for hierarchies such as org charts or category trees:

WITH RECURSIVE reports AS (
    SELECT id, manager_id, 1 AS depth FROM employees WHERE id = 42
    UNION ALL
    SELECT e.id, e.manager_id, r.depth + 1
    FROM employees e
    JOIN reports r ON e.manager_id = r.id
    WHERE r.depth < 10
)
SELECT * FROM reports;

The depth limit is there to stop a cycle in bad data from running forever, since UNION ALL won't catch it. Postgres 14 and later also offer a CYCLE clause. Reach for a dedicated graph database when you need many hops across billions of edges, and not before. Most applications never get there.

Keep the iterative form handy

A recursive DFS on a linked structure 100,000 nodes deep will blow the stack. Use an explicit stack in production code for anything fed by user data. For BFS, mark nodes as visited when you enqueue them, not when you dequeue them, or the queue can fill with duplicates on a dense graph. On very large graphs, a bidirectional search from both ends often explores far fewer nodes than a one-way BFS.

A Quick Way to Choose

Need the fewest hops on an unweighted graph? Use BFS. Need to explore everything, or detect a cycle? Use DFS. Need an order for dependencies? Use a topological sort. Are the edges weighted? Use Dijkstra. Those four cover nearly everything you'll meet at work. Most real bugs come from choosing the right algorithm and forgetting the visited set, so add that first.