A graph is a collection of nodes (vertices) and edges (connections) that link pairs of nodes. Nodes can represent entities such as cities, people, or web pages, while edges represent relationships between them. Graphs can be directed (edges have a specific direction) or undirected (edges have no direction).

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);
  }

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

  removeVertex(vertex: number): void {
    this.adjacencyList.delete(vertex);
    this.adjacencyList.forEach((neighbors, v) => {
      const index = neighbors.indexOf(vertex);
      if (index !== -1) {
        neighbors.splice(index, 1); // Remove the edge
      }
    });
  }

  removeEdge(source: number, destination: number): void {
    if (this.adjacencyList.has(source)) {
      const index = this.adjacencyList.get(source)?.indexOf(destination);
      if (index !== -1) {
        this.adjacencyList.get(source)?.splice(index, 1);
      }
    }
    if (this.adjacencyList.has(destination)) {
      const index = this.adjacencyList.get(destination)?.indexOf(source);
      if (index !== -1) {
        this.adjacencyList.get(destination)?.splice(index, 1); // For undirected graph
      }
    }
  }
}

// Usage
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)); // Output: [0, 1, 3]

When to use Graph?

Graphs are versatile data structures that can be used in various scenarios where relationships or connections between entities need to be represented. Here are some common scenarios where graphs are used:

• Social Networks: Graphs are widely used to represent social networks, where individuals (nodes) are connected by relationships such as friendships or following relationships.
• Routing and Navigation: Graphs are used in routing algorithms to find the shortest path between two points in a network, such as in GPS navigation systems or network routing protocols. (Source: https://gazar.dev/algorithm/dijkstra-algorithm ) (Source: https://gazar.dev/algorithm/kruskal-algorithm )
• Recommendation Systems: Graphs can model user-item interactions in recommendation systems, where users and items are nodes, and edges represent interactions or preferences.
• Network Analysis: Graphs are used to analyze complex networks such as computer networks, biological networks, or transportation networks to understand their structure, connectivity, and behavior.
• Dependency Management: Graphs are used to model dependencies between components in software systems, such as in package management systems or build systems.
• Data Modeling: Graphs are used in various domains to model relationships between entities, such as in knowledge graphs, semantic web applications, or genealogical databases.
• Circuit Design: Graphs are used in electrical engineering to model circuits, where components are nodes, and connections between components are edges.
• Optimization Problems: Graphs are used in optimization problems, such as in scheduling, resource allocation, or logistics, where finding the optimal arrangement or path is required.

Graph data structures are versatile and powerful tools for modeling relationships and solving various computational problems. With TypeScript, we can implement graphs efficiently and leverage the language's features to create robust and type-safe solutions. By understanding the fundamentals of graphs and their operations, developers can tackle complex problems more effectively and build scalable applications.