Exploring Graph Data Structures in TypeScript

A graph models relationships. Nodes (vertices) represent entities. Edges represent connections between them. That's it. And that simple structure can model almost anything: social networks, road maps, dependency trees, circuit boards.

Graphs can be directed (edges have a direction, like "A follows B") or undirected (edges go both ways, like "A is friends with B"). They can be weighted (edges have a cost) or unweighted.

Adjacency List Implementation

The most common representation. Each vertex stores a list of its neighbors. Space-efficient for sparse graphs.

class Graph {
  private adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex: number): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(source: number, destination: number): void {
    if (!this.adjacencyList.has(source)) this.addVertex(source);
    if (!this.adjacencyList.has(destination)) this.addVertex(destination);

    this.adjacencyList.get(source)!.push(destination);
    this.adjacencyList.get(destination)!.push(source); // undirected
  }

  getNeighbors(vertex: number): number[] | undefined {
    return this.adjacencyList.get(vertex);
  }

  removeEdge(source: number, destination: number): void {
    const sourceList = this.adjacencyList.get(source);
    const destList = this.adjacencyList.get(destination);

    if (sourceList) {
      const idx = sourceList.indexOf(destination);
      if (idx !== -1) sourceList.splice(idx, 1);
    }
    if (destList) {
      const idx = destList.indexOf(source);
      if (idx !== -1) destList.splice(idx, 1);
    }
  }

  removeVertex(vertex: number): void {
    this.adjacencyList.delete(vertex);
    this.adjacencyList.forEach((neighbors) => {
      const idx = neighbors.indexOf(vertex);
      if (idx !== -1) neighbors.splice(idx, 1);
    });
  }
}

const graph = new Graph();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
console.log(graph.getNeighbors(2)); // [0, 1, 3]

Adjacency List vs Adjacency Matrix

An adjacency matrix uses a 2D array where matrix[i][j] = 1 means there's an edge from i to j. It gives O(1) edge lookup but uses O(V²) space. Good for dense graphs. Bad for sparse ones.

An adjacency list uses O(V + E) space and is better for most real-world graphs, which tend to be sparse.

When to Use Graphs

• Social networks: Users are nodes, friendships are edges. Finding mutual friends is graph traversal.
• Navigation and routing: Cities are nodes, roads are weighted edges. Shortest path is Dijkstra's algorithm. (Dijkstra's Algorithm)
• Dependency management: Packages are nodes, dependencies are directed edges. Topological sort determines install order.
• Recommendation engines: Users and items are nodes. Interactions are edges. Graph algorithms find patterns.
• Network analysis: Servers are nodes, connections are edges. Find bottlenecks, single points of failure.
• Spanning trees: Find the minimum cost to connect all nodes. (Kruskal's Algorithm)

The Trade-off

Graphs are powerful but complex. Traversal algorithms (BFS, DFS) are straightforward, but pathfinding, cycle detection, and optimization on graphs can get computationally expensive fast. The representation you choose (list vs matrix) and the algorithm you pick depend entirely on the density of your graph and the operations you need.

No data structure models relationships as naturally as a graph. When your problem is about connections between things, a graph is almost certainly the right tool.