Graphs & Representations

A Graph is a non-linear data structure consisting of Vertices (Nodes) connected by Edges. Actually, a Tree is just a highly restricted Graph! A Tree is a graph with no cycles, where every node only has one parent.

Graphs are used to model real-world relationships: social networks (friends), computer networks (routers), and mapping systems (cities and roads).

Types of Graphs

1. Undirected Graph: Edges have no direction. If A is connected to B, then B is connected to A. (e.g., Facebook Friends).
2. Directed Graph (Digraph): Edges have a specific direction. A points to B, but B might not point to A. (e.g., Twitter Followers, webpage links).
3. Weighted Graph: Edges have a numerical cost or weight attached to them. (e.g., Google Maps, where the edge weight is the distance or traffic time between two cities).
4. Cyclic vs Acyclic: If you can start at Node A, follow a path of edges, and end up back at Node A, the graph has a Cycle. A Directed Acyclic Graph (DAG) is heavily used in job scheduling and build systems.

How to Represent a Graph in Code

Unlike Trees, Graphs do not have a "Root" node. To represent a graph in code, we primarily use one of two methods: Adjacency Matrices or Adjacency Lists.

1. Adjacency Matrix

A 2D array (grid) of size V x V (where V is the number of vertices). If matrix[i][j] === 1, there is an edge from node i to node j.

• Pros: Instant $O(1)$ lookups to check if an edge exists between two specific nodes.
• Cons: Terrible Space Complexity $O(V^2)$. If a social network has 1 billion users, creating a 1 billion x 1 billion grid will crash any server, especially since 99.9% of the grid will be empty 0s (a sparse graph).

2. Adjacency List (The Industry Standard)

An Array or Hash Map where every vertex stores a List of its direct neighbors.

• Pros: Excellent Space Complexity $O(V + E)$ (Vertices + Edges). It only stores actual connections. Extremely fast for iterating over a node's neighbors (which is what graph algorithms like BFS and DFS do).
• Cons: Checking if an edge exists between A and B takes $O(E_{A})$ time, as you have to scan A's neighbor list.

Implementation (Adjacency List in TypeScript)

// Implementing an Undirected Graph using an Adjacency List Map
class Graph {
  // Map stores Node -> Array of Neighbors
  private adjacencyList: Map<string, string[]>;

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

  // Add a Vertex O(1)
  public addVertex(vertex: string): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Add an Edge O(1)
  public addEdge(v1: string, v2: string): void {
    // Because it's undirected, we add to BOTH lists!
    this.adjacencyList.get(v1)?.push(v2);
    this.adjacencyList.get(v2)?.push(v1);
  }

  public printGraph(): void {
    for (const [vertex, neighbors] of this.adjacencyList.entries()) {
      console.log(`${vertex} -> [${neighbors.join(', ')}]`);
    }
  }
}

// Usage
const g = new Graph();
g.addVertex("Tokyo");
g.addVertex("Dallas");
g.addVertex("London");

g.addEdge("Tokyo", "Dallas");
g.addEdge("Dallas", "London");

g.printGraph();
// Tokyo -> [Dallas]
// Dallas -> [Tokyo, London]
// London -> [Dallas]