Crafting Graphs in TypeScript: A Comprehensive Guide to Building and Traversing Data Structures

Graphs are powerful data structures used to model relationships in data, from social networks and navigation systems to dependency tracking and recommendation engines. In this guide, we’ll create a graph in TypeScript, implementing basic operations like adding vertices, edges, and exploring traversal methods.

What is a Graph?

A graph is a data structure made up of vertices (or nodes) connected by edges. Graphs are versatile and can be directed or undirected, weighted or unweighted, and cyclic or acyclic, depending on how nodes are interconnected and how data flows between them.

Types of Graphs

• Directed Graph: Edges have directions, representing a one-way relationship between nodes.

• Undirected Graph: Edges are bidirectional, representing a two-way relationship.

• Weighted Graph: Edges have weights, representing the cost or distance of traversing from one node to another.

• Unweighted Graph: All edges are considered equal in cost.

Step 1: Defining the Graph in TypeScript

To start, we’ll create a Graph class that supports the addition of vertices and edges. We’ll represent the graph as an adjacency list, where each vertex key points to a list of connected vertices.

Graph.ts

// Graph.ts

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

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

  // Adds a new vertex to the graph
  addVertex(vertex: string) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Adds an edge between two vertices
  addEdge(vertex1: string, vertex2: string) {
    if (!this.adjacencyList.has(vertex1)) this.addVertex(vertex1);
    if (!this.adjacencyList.has(vertex2)) this.addVertex(vertex2);
    this.adjacencyList.get(vertex1)?.push(vertex2);
    this.adjacencyList.get(vertex2)?.push(vertex1);
  }

  // Displays the adjacency list for visualization
  displayGraph() {
    for (let [vertex, edges] of this.adjacencyList) {
      console.log(vertex, ":", edges.join(", "));
    }
  }
}

export { Graph };

Step 2: Adding Vertices and Edges

Using the Graph class, we can now add vertices and edges, connecting nodes to represent relationships. The addVertex method adds a node if it doesn't already exist, while addEdge creates a bi-directional connection between two vertices.

Step 3: Implementing Graph Traversal Methods

Now that we can create a graph, let’s add some traversal methods: Depth-First Search (DFS) and Breadth-First Search (BFS).

1. Depth-First Search (DFS)

DFS explores as far down a branch as possible before backtracking. We can implement DFS recursively, visiting each connected node before returning up the branch.

// Adds depth-first traversal to Graph.ts

class Graph {
  // ... previous code ...

  // Depth-First Search traversal
  depthFirstSearch(start: string, visited: Set<string> = new Set()) {
    visited.add(start);
    console.log(start);

    for (let neighbor of this.adjacencyList.get(start) || []) {
      if (!visited.has(neighbor)) {
        this.depthFirstSearch(neighbor, visited);
      }
    }
  }
}

For a more interactive understanding of how Depth-First Search (DFS) works, you can explore this DFS visualization tool. This tool offers a step-by-step visual representation of the DFS algorithm in action, allowing you to observe how nodes are visited by diving deep into each branch before backtracking. It's an excellent resource to enhance your comprehension of DFS and visualize the traversal process in an engaging manner.

2. Breadth-First Search (BFS)

BFS explores all nodes at the current level before moving to the next. We’ll implement BFS iteratively using a queue.

// Adds breadth-first traversal to Graph.ts

class Graph {
  // ... previous code ...

  // Breadth-First Search traversal
  breadthFirstSearch(start: string) {
    const visited = new Set<string>();
    const queue: string[] = [start];

    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift()!;
      console.log(vertex);

      for (let neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
}

For a more interactive understanding of how Breadth-First Search (BFS) works, you can explore this BFS visualization tool. This tool provides a step-by-step visual representation of the BFS algorithm in action, allowing you to see how nodes are visited level by level. It's a great way to reinforce your understanding of BFS and see the traversal process in a dynamic and engaging way.

Step 4: Testing the Graph in the Console

We can set up a basic test to add vertices, connect them with edges, and use DFS and BFS to explore the graph.

index.ts

// index.ts

import { Graph } from './Graph';

const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");

console.log("Graph structure:");
graph.displayGraph();

console.log("\nDFS starting from A:");
graph.depthFirstSearch("A");

console.log("\nBFS starting from A:");
graph.breadthFirstSearch("A");

Compile and Run

Compile the code and run the output in the console:

npx tsc
node dist/index.js

Expected Output

The console output should look like:

Graph structure:
A : B, C
B : A, D
C : A, E
D : B, E
E : C, D

DFS starting from A:
A
B
D
E
C

BFS starting from A:
A
B
C
D
E

Where Are Graphs Used?

Graphs are utilized in a variety of applications due to their ability to represent complex, interconnected data:

• Social Networks: Nodes represent people, and edges represent relationships.

• Web Crawling: Graph traversal techniques (like BFS) explore links between web pages.

• Navigation Systems: Cities are vertices, and roads are edges, with shortest-path algorithms finding efficient routes.

• Dependency Tracking: In project management or programming, nodes represent tasks or files, and edges represent dependencies.

Visualizing the Graph Structure

Here’s a visual representation of the graph we created:

      A
     / \
    B   C
     \ / \
      D - E

In this example:

• A is connected to B and C.

• B and D are connected, as well as C and E.

• D and E are interconnected.

---

This guide outlines how to build a basic graph data structure in TypeScript, exploring vertices, edges, and traversal methods. You can expand this further with weighted edges or directed graphs as needed for specific applications. Try exploring different traversal methods and practice applying graphs in real-world use cases!

Find the full code and interactive examples on our StackBlitz page to experiment with and expand on this foundational structure. Happy coding!