Graph Algorithms Every Engineer Should Know

Graphs appear whenever relationships matter more than rows. A deployment service follows dependencies, a navigation system follows roads, an authorization engine follows group membership, and a build tool follows imports. The domain names differ, but the computational questions repeat: What can this node reach? What is the cheapest route? Can these tasks run in a valid order? Does adding this connection create a cycle?

Knowing the names of graph algorithms is not enough. Production code depends on choosing the algorithm whose assumptions match the data, preserving its invariant while implementing it, and defining behavior for awkward inputs such as disconnected components, cycles, duplicate edges, and negative weights. A fast implementation of the wrong algorithm is still wrong.

This guide develops a small TypeScript toolkit around an adjacency list, then uses it to explain breadth-first search, depth-first search, Dijkstra’s algorithm, and topological sorting. The goal is not a competitive-programming catalog. It is a compact decision model for engineering systems in which graph-shaped data quietly does real work.

Model the Graph Before Choosing the Algorithm #

A graph $G = (V, E)$ contains vertices $V$ and edges $E$. Edges may be directed or undirected, weighted or unweighted. Those properties are part of the problem contract, not implementation trivia. A road can be traversable in both directions but have different travel times; a package dependency points one way; a social connection may be symmetric. Converting any of these into the wrong graph changes the answer.

For sparse production graphs, an adjacency list is usually the practical representation. It stores each vertex with its outgoing edges, requiring $O(|V| + |E|)$ space. An adjacency matrix uses $O(|V|^2)$ space but answers “is there an edge from A to B?” in constant time. Matrices make sense for small dense graphs; lists fit dependency graphs, route networks, and most service relationships.

type NodeId = string;

type Edge = Readonly<{
  to: NodeId;
  weight: number;
}>;

class Graph {
  private readonly adjacency = new Map<NodeId, Edge[]>();

  constructor(readonly directed: boolean) {}

  addNode(node: NodeId): void {
    if (!this.adjacency.has(node)) this.adjacency.set(node, []);
  }

  addEdge(from: NodeId, to: NodeId, weight = 1): void {
    if (!Number.isFinite(weight)) throw new Error('Weight must be finite');
    this.addNode(from);
    this.addNode(to);
    this.adjacency.get(from)!.push({ to, weight });
    if (!this.directed) this.adjacency.get(to)!.push({ to: from, weight });
  }

  nodes(): readonly NodeId[] {
    return [...this.adjacency.keys()];
  }

  neighbors(node: NodeId): readonly Edge[] {
    return this.adjacency.get(node) ?? [];
  }
}

This representation deliberately makes isolated vertices explicit through addNode. If vertices exist only when an edge is inserted, a disconnected single-node component vanishes. Decide separately whether parallel edges and self-loops are legal. A flight network may have multiple routes between two airports; a dependency graph may want to reject duplicates. The storage type should not silently decide domain policy.

The isolated audit store in this graph is intentional. Starting a traversal at API will never discover it. “Visit the whole graph” therefore means starting another traversal from every still-unvisited vertex, not merely choosing one convenient root.

Reachability with BFS and DFS #

Breadth-first search (BFS) explores vertices in layers. Its queue invariant is that vertices are removed in nondecreasing distance from the start. In an unweighted graph, the first discovered path to a vertex therefore uses the fewest edges. This makes BFS appropriate for minimum-hop routing, degrees of separation, shallow dependency discovery, and finding the nearest matching state.

Depth-first search (DFS) follows one branch before backtracking. Its useful invariant is that a vertex is marked before another route can schedule it again. DFS is natural for exhaustive reachability, component discovery, cycle detection with coloring, and algorithms built around entry and exit times. It does not promise a shortest path.

type Traversal = Readonly<{
  order: readonly NodeId[];
  parent: ReadonlyMap<NodeId, NodeId>;
}>;

function bfs(graph: Graph, start: NodeId): Traversal & {
  distance: ReadonlyMap<NodeId, number>;
} {
  const order: NodeId[] = [];
  const parent = new Map<NodeId, NodeId>();
  const distance = new Map<NodeId, number>([[start, 0]]);
  const queue: NodeId[] = [start];

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head]!;
    order.push(node);

    for (const { to } of graph.neighbors(node)) {
      if (distance.has(to)) continue;
      distance.set(to, distance.get(node)! + 1);
      parent.set(to, node);
      queue.push(to);
    }
  }

  return { order, parent, distance };
}

function dfs(graph: Graph, start: NodeId): Traversal {
  const order: NodeId[] = [];
  const parent = new Map<NodeId, NodeId>();
  const visited = new Set<NodeId>([start]);
  const stack: NodeId[] = [start];

  while (stack.length > 0) {
    const node = stack.pop()!;
    order.push(node);
    const neighbors = graph.neighbors(node);

    for (let index = neighbors.length - 1; index >= 0; index -= 1) {
      const next = neighbors[index]!.to;
      if (visited.has(next)) continue;
      visited.add(next);
      parent.set(next, node);
      stack.push(next);
    }
  }

  return { order, parent };
}

Both algorithms run in $O(|V| + |E|)$ time over the reachable component and use $O(|V|)$ auxiliary space. The indexed queue avoids JavaScript’s shift(), which repeatedly moves array elements. The iterative DFS avoids overflowing the call stack on a chain with hundreds of thousands of vertices. Reversing neighbors before pushing merely preserves their insertion order in the visible traversal; correctness should never depend on that order unless the contract specifies deterministic tie-breaking.

A common bug marks a vertex only when it leaves the queue or stack. Multiple incoming edges can then enqueue it repeatedly, inflating memory and overwriting its parent. Mark on discovery. Another bug assumes the returned parent map contains every graph vertex. It contains only reached vertices; an absent parent means either “unreachable” or “the start,” so callers should distinguish the start explicitly.

Weighted Paths with Dijkstra #

BFS minimizes edge count, not cost. When edges have nonnegative costs, Dijkstra’s algorithm repeatedly settles the unsettled vertex with the smallest known distance. Its invariant is precise: once the minimum-distance entry is removed from the priority queue, no later path can improve it if every edge weight is nonnegative.

The relaxation step tests whether reaching to through the current vertex is cheaper:

If $alt < dist[v]$, update the distance and predecessor. With a binary heap, the running time is $O((|V| + |E|) \log |V|)$, commonly written $O(|E| \log |V|)$ for connected sparse graphs.

type QueueEntry = { node: NodeId; priority: number };

class MinQueue {
  private readonly heap: QueueEntry[] = [];

  push(entry: QueueEntry): void {
    this.heap.push(entry);
    for (let index = this.heap.length - 1; index > 0; ) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent]!.priority <= entry.priority) break;
      this.heap[index] = this.heap[parent]!;
      index = parent;
      this.heap[index] = entry;
    }
  }

  pop(): QueueEntry | undefined {
    const first = this.heap[0];
    const last = this.heap.pop();
    if (!first || !last || this.heap.length === 0) return first;
    this.heap[0] = last;

    for (let index = 0; ; ) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;
      if (left < this.heap.length &&
          this.heap[left]!.priority < this.heap[smallest]!.priority) smallest = left;
      if (right < this.heap.length &&
          this.heap[right]!.priority < this.heap[smallest]!.priority) smallest = right;
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest]!, this.heap[index]!];
      index = smallest;
    }
    return first;
  }

  get size(): number {
    return this.heap.length;
  }
}

function dijkstra(graph: Graph, start: NodeId): {
  distance: ReadonlyMap<NodeId, number>;
  parent: ReadonlyMap<NodeId, NodeId>;
} {
  const distance = new Map(graph.nodes().map((node) => [node, Infinity]));
  const parent = new Map<NodeId, NodeId>();
  const queue = new MinQueue();

  for (const node of graph.nodes()) {
    for (const edge of graph.neighbors(node)) {
      if (edge.weight < 0) throw new Error('Dijkstra requires nonnegative weights');
    }
  }

  distance.set(start, 0);
  queue.push({ node: start, priority: 0 });

  while (queue.size > 0) {
    const current = queue.pop()!;
    if (current.priority !== distance.get(current.node)) continue;

    for (const edge of graph.neighbors(current.node)) {
      const candidate = current.priority + edge.weight;
      if (candidate >= (distance.get(edge.to) ?? Infinity)) continue;
      distance.set(edge.to, candidate);
      parent.set(edge.to, current.node);
      queue.push({ node: edge.to, priority: candidate });
    }
  }

  return { distance, parent };
}

This heap has no decrease-key operation. Instead, each improvement adds a new entry, and the equality check discards stale entries. That pattern is simple and reliable. Unreachable vertices retain Infinity; they must not be presented as valid routes. To reconstruct a path, walk the parent map backward from the target and reverse the result, but first verify that its distance is finite.

Dependencies, Cycles, and Connectivity #

A topological order places every directed edge from an earlier vertex to a later one. Such an order exists only for a directed acyclic graph (DAG). Kahn’s algorithm tracks each vertex’s indegree, queues all zero-indegree vertices, then removes their outgoing edges conceptually. The invariant is that every queued vertex has no remaining prerequisite.

function topologicalSort(graph: Graph): readonly NodeId[] {
  if (!graph.directed) throw new Error('Topological sort requires a directed graph');

  const indegree = new Map(graph.nodes().map((node) => [node, 0]));
  for (const node of graph.nodes()) {
    for (const { to } of graph.neighbors(node)) {
      indegree.set(to, (indegree.get(to) ?? 0) + 1);
    }
  }

  const queue = graph.nodes().filter((node) => indegree.get(node) === 0);
  const order: NodeId[] = [];

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head]!;
    order.push(node);
    for (const { to } of graph.neighbors(node)) {
      const next = indegree.get(to)! - 1;
      indegree.set(to, next);
      if (next === 0) queue.push(to);
    }
  }

  if (order.length !== graph.nodes().length) {
    throw new Error('Graph contains a cycle');
  }
  return order;
}

This is the basis of build scheduling, migration planning, spreadsheet recalculation, and workflow orchestration. A partial order can have many valid outputs, so tests should verify the edge constraint rather than demand one arbitrary sequence. If stable output matters, use a priority queue for zero-indegree vertices and document the tie-breaker.

Connectivity asks a different question. Repeated BFS or DFS finds components in a static graph. For an evolving undirected graph with many “are these connected?” queries, disjoint-set union (union-find) is often better. Path compression and union by rank give nearly constant amortized operations, $O(\alpha(|V|))$. Union-find cannot recover a route, handle edge deletion cheaply, or represent directed reachability, so it is not a universal replacement for traversal.

Production Applications and Tests #

Algorithm selection starts with the output contract. An incident tool asking “which services can be affected?” needs reachability, usually BFS or DFS. A scheduler needs a topological order and an explicit cycle report. Network latency routing needs Dijkstra only if costs are nonnegative and additive. An account-permission graph may require careful directed traversal with limits, because a high-degree group can turn an innocent query into a resource-exhaustion path.

Real graphs also change while computation runs. Choose whether an operation sees a snapshot, tolerates eventual consistency, or restarts when the graph version changes. For large graphs, storing the entire adjacency list in one process may be impossible; frontier-based database queries or specialized graph systems trade local simplicity for I/O and consistency concerns. Put caps on depth, visited vertices, and runtime for user-controlled traversals, and return a distinct truncated result instead of pretending it is complete.

Tests should assert properties, not only familiar examples:

• For every BFS parent edge, the child’s distance equals the parent’s distance plus one.
• Every reachable vertex appears exactly once in BFS and DFS output.
• For every relaxed edge after Dijkstra, distance[to] <= distance[from] + weight.
• Reconstructing a finite Dijkstra path produces edges whose weights sum to the reported distance.
• Every edge in a topological result points forward; cyclic input throws.
• Empty, single-node, self-loop, parallel-edge, disconnected, and high-degree graphs have explicit expectations.
• Random small graphs can be checked against a slower reference implementation, such as Bellman-Ford for nonnegative shortest paths.

Determinism deserves a deliberate decision. Map and array insertion order makes these examples repeatable, but data fetched concurrently may arrive differently. If output feeds caches, snapshots, or deployment plans, sort neighbors or define a priority rule. If only correctness matters, avoid brittle tests that confuse one valid traversal order with the only valid order.

Observability belongs beside correctness. Record graph size, visited count, frontier or queue peak, elapsed time, and whether a limit truncated the result. These measurements reveal an accidental dense graph, a tenant with pathological fan-out, or a model change that turns a cheap query into a fleet-wide scan.

Takeaways #

Graph algorithms become manageable when assumptions are made explicit. Model direction, weight, and isolated vertices first. Use BFS for layers and minimum hops, DFS for deep structural exploration, Dijkstra for nonnegative weighted paths, topological sorting for DAG dependencies, and union-find for repeated undirected connectivity queries.

Preserve each algorithm’s invariant: mark traversal vertices on discovery, settle only the smallest nonnegative Dijkstra distance, and emit only zero-indegree vertices during topological sorting. Treat negative weights, cycles, and disconnected components as contract cases rather than surprises. Finally, test properties and limits as seriously as example outputs. That is what turns a textbook algorithm into dependable production behavior.