Type‑Safe Graph Traversal in TypeScript: Generic DFS & BFS You Can Trust

Introduction

Graphs are the lingua‑franca of many domains: social networks, build pipelines, recommendation engines, and even compiler analyses.
When you write a traversal in plain JavaScript you quickly discover two pain points:

1. Accidental type mismatches – a node may carry a payload of User but the algorithm treats it as a plain string.
2. Hard‑to‑maintain signatures – every new edge property forces you to rewrite the traversal code.

TypeScript’s generic system can eliminate both issues. In this article we’ll build a type‑safe adjacency‑list graph, then implement depth‑first search (DFS) and breadth‑first search (BFS) that preserve the exact node and edge types throughout the walk. The code is deliberately pragmatic: you can copy‑paste it into a Node or Deno project and start solving real problems right away.

1. A Generic Graph Model

1.1 The core interfaces

/** Identifier type – usually string or number */
type ID = string | number;

/** Edge payload – can be anything the domain needs */
interface Edge<E = unknown> {
  /** Target node identifier */
  to: ID;
  /** Optional data attached to the edge */
  data?: E;
}

/** Node payload – the information you care about */
interface Node<N = unknown, E = unknown> {
  /** Unique identifier */
  id: ID;
  /** Domain‑specific data */
  data: N;
  /** Outgoing edges */
  edges: Edge<E>[];
}

The Node type is generic in two dimensions:

• N – the shape of the node’s own data (e.g., a User object).
• E – the shape of edge data (e.g., a Friendship weight).

Because the graph is stored as an adjacency list, each node owns its outgoing edges. This layout works well for sparse graphs and lets us keep the traversal logic simple.

1.2 The container

class Graph<N = unknown, E = unknown> {
  /** Map from id → Node */
  private readonly nodes = new Map<ID, Node<N, E>>();

  /** Add a node – returns the graph for chaining */
  addNode(node: Node<N, E>): this {
    if (this.nodes.has(node.id)) {
      throw new Error(`Node with id ${node.id} already exists`);
    }
    this.nodes.set(node.id, node);
    return this;
  }

  /** Retrieve a node by id (throws if missing) */
  getNode(id: ID): Node<N, E> {
    const n = this.nodes.get(id);
    if (!n) throw new Error(`Node ${id} not found`);
    return n;
  }

  /** Convenience iterator */
  *[Symbol.iterator](): IterableIterator<Node<N, E>> {
    yield* this.nodes.values();
  }
}

The Graph class is fully generic; any consumer can instantiate it with concrete types:

type User = { name: string; age: number };
type Friendship = { since: Date; strength: number };

const social = new Graph<User, Friendship>();

2. Depth‑First Search (DFS)

DFS can be expressed recursively or iteratively. We’ll provide both, each preserving type safety.

2.1 Recursive DFS

function dfsRecursive<N, E, R = N>(
  graph: Graph<N, E>,
  startId: ID,
  /** Visitor receives the node and a depth counter */
  visit: (node: Node<N, E>, depth: number) => R | undefined,
  /** Optional set to avoid revisiting */
  visited = new Set<ID>(),
  depth = 0
): R[] {
  const node = graph.getNode(startId);
  if (visited.has(node.id)) return [];

  visited.add(node.id);
  const results: R[] = [];

  const r = visit(node, depth);
  if (r !== undefined) results.push(r);

  for (const edge of node.edges) {
    results.push(...dfsRecursive(graph, edge.to, visit, visited, depth + 1));
  }
  return results;
}

Why is this type‑safe?

• The visit callback receives a Node<N, E> – you can safely read node.data as N and edge.data as E later on.
• The generic R lets you decide what the traversal should return (e.g., a transformed value, a boolean flag, etc.) without casting.

Real‑world use‑case: Collecting all users older than 30

const seniors = dfsRecursive(
  social,
  'alice',
  (node) => node.data.age > 30 ? node.data : undefined
);
console.log('Seniors reachable from Alice:', seniors);

The compiler guarantees that node.data is a User, so age is always available.

2.2 Iterative DFS (stack‑based)

Recursive calls can overflow on very deep graphs. An explicit stack avoids that risk.

function dfsIterative<N, E, R = N>(
  graph: Graph<N, E>,
  startId: ID,
  visit: (node: Node<N, E>, depth: number) => R | undefined
): R[] {
  const stack: Array<{ id: ID; depth: number }> = [{ id: startId, depth: 0 }];
  const visited = new Set<ID>();
  const results: R[] = [];

  while (stack.length) {
    const { id, depth } = stack.pop()!;
    if (visited.has(id)) continue;
    visited.add(id);

    const node = graph.getNode(id);
    const r = visit(node, depth);
    if (r !== undefined) results.push(r);

    // Push children in reverse order to mimic recursive order
    for (let i = node.edges.length - 1; i >= 0; i--) {
      stack.push({ id: node.edges[i].to, depth: depth + 1 });
    }
  }
  return results;
}

The signature mirrors the recursive version, so you can swap implementations without touching call sites.

3. Breadth‑First Search (BFS)

BFS explores a graph level by level, which is perfect for shortest‑path or “nearest‑neighbors” queries.

function bfs<N, E, R = N>(
  graph: Graph<N, E>,
  startId: ID,
  visit: (node: Node<N, E>, depth: number) => R | undefined
): R[] {
  const queue: Array<{ id: ID; depth: number }> = [{ id: startId, depth: 0 }];
  const visited = new Set<ID>();
  const results: R[] = [];

  while (queue.length) {
    const { id, depth } = queue.shift()!;
    if (visited.has(id)) continue;
    visited.add(id);

    const node = graph.getNode(id);
    const r = visit(node, depth);
    if (r !== undefined) results.push(r);

    for (const edge of node.edges) {
      if (!visited.has(edge.to)) {
        queue.push({ id: edge.to, depth: depth + 1 });
      }
    }
  }
  return results;
}

Real‑world use‑case: Finding the first user who knows a given skill

type Skill = { name: string };
type User = { name: string; skills: Skill[] };

const skillGraph = new Graph<User, never>();

// ...populate graph...

function firstWithSkill(start: ID, skillName: string): User | undefined {
  const found = bfs(
    skillGraph,
    start,
    (node) => node.data.skills.some(s => s.name === skillName) ? node.data : undefined
  );
  return found[0]; // BFS guarantees the closest match
}

Again, the compiler enforces that node.data.skills exists and is an array of Skill.

4. Putting It All Together – A Mini Project

4.1 Scenario

You are building a package‑dependency visualizer for a monorepo. Each package (PackageInfo) lists its direct dependencies (DepInfo). You need two features:

1. List all transitive dependencies (DFS).
2. Show the minimal number of steps to a core library (BFS).

4.2 Types

type PackageInfo = {
  name: string;
  version: string;
};

type DepInfo = {
  /** Version range, e.g. "^1.2.0" */
  range: string;
};

4.3 Build the graph

const repo = new Graph<PackageInfo, DepInfo>();

function addPackage(pkg: PackageInfo, deps: Record<string, DepInfo>) {
  const node: Node<PackageInfo, DepInfo> = {
    id: pkg.name,
    data: pkg,
    edges: Object.entries(deps).map(([to, data]) => ({ to, data }))
  };
  repo.addNode(node);
}

// Example data
addPackage({ name: 'ui', version: '1.0.0' }, { core: { range: '^2.0.0' } });
addPackage({ name: 'core', version: '2.1.0' }, { utils: { range: '^1.0.0' } });
addPackage({ name: 'utils', version: '1.3.0' }, {});

4.4 Transitive dependencies (DFS)

function transitiveDeps(start: ID): PackageInfo[] {
  return dfsRecursive(
    repo,
    start,
    (node) => node.id !== start ? node.data : undefined
  );
}

console.log('All deps of ui:', transitiveDeps('ui'));

4.5 Shortest path to core (BFS)

function stepsToCore(start: ID): number | null {
  const distances = bfs(
    repo,
    start,
    (node, depth) => node.id === 'core' ? depth : undefined
  );
  return distances.length ? distances[0] : null;
}

console.log('Steps from utils to core:', stepsToCore('utils'));

Both functions are type‑checked: you cannot accidentally treat a PackageInfo as a User, and edge data (DepInfo) is available if you need it for version‑range analysis.

5. Performance & Safety Tips

6. Testing the Traversals

A quick Jest‑style test demonstrates the type safety in action:

test('DFS returns only User objects', () => {
  const result = dfsRecursive<User, never>(social, 'bob', n => n.data);
  // TypeScript infers result: User[]
  expect(result.every(u => typeof u.name === 'string')).toBe(true);
});

If you mistakenly return n.id (a string | number) the compiler flags the mismatch because R was inferred as User.

7. Conclusion

By parameterising both node and edge payloads, we turned a classic graph traversal problem into a set of fully type‑checked utilities. The generic signatures let you:

• Reuse the same traversal code across unrelated domains (social graphs, package dependencies, game maps).
• Change the shape of data without touching the algorithm.
• Rely on the compiler to catch accidental misuse, reducing runtime bugs.

Copy the Graph, dfsRecursive, dfsIterative, and bfs implementations into your toolbox, instantiate them with your domain types, and you’ll have a robust, type‑safe foundation for any future graph‑related feature. Happy traversing!