Graph

A non-linear data structure consisting of vertices (nodes) connected by edges. Graphs model relationships and networks, making them essential for solving real-world problems.

Overview

Graphs represent pairwise relationships between objects. This implementation uses an adjacency list representation, which is space-efficient for sparse graphs.

Graph Types

Directed Graph: Edges have direction (A → B doesn’t imply B → A)
Undirected Graph: Edges are bidirectional (A — B means both A → B and B → A)

Implementation

Vertex Class

class Vertex<T = number> {
  value: T;
  edges: Vertex<T>[] = [];

  constructor(value: T) {
    this.value = value;
  }
}

Each vertex stores its value and a list of adjacent vertices (edges). Reference: vertex.ts:1-9

Graph Class

class Graph<T = number> {
  directed: boolean;
  vertices: Vertex<T>[] = [];

  constructor(directed = false) {
    this.directed = directed;
  }
  
  // ... methods
}

Reference: graph.ts:3-10

Adjacency List: Each vertex maintains an array of its adjacent vertices. This representation is efficient for sparse graphs (few edges relative to vertices).

API Reference

constructor(directed: boolean = false)

Creates a new graph.

// Undirected graph
const graph = new Graph<number>();

// Directed graph
const directedGraph = new Graph<number>(true);

Parameters:

directed: Whether edges are directional (default: false)

addVertex(value: T): Vertex<T>

Adds a vertex to the graph.

const graph = new Graph<number>();
const v1 = graph.addVertex(1);
const v2 = graph.addVertex(2);
const v3 = graph.addVertex(3);

Returns: The newly created vertex Complexity: O(1) Reference: graph.ts:12-17

addEdge(value1: T, value2: T): void

Adds an edge between two vertices. Creates vertices if they don’t exist.

const graph = new Graph<number>();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);

// Undirected graph:
// 1 -- 2, 3
// 2 -- 1, 3  
// 3 -- 1, 2

Parameters:

value1: First vertex value
value2: Second vertex value

Behavior:

For undirected graphs: Creates bidirectional edge (A ↔ B)
For directed graphs: Creates unidirectional edge (A → B)

Complexity: O(V) - needs to find vertices Reference: graph.ts:23-40

toString(): string

Returns a string representation of the graph.

const graph = new Graph<number>();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);

console.log(graph.toString());
// Output:
// 1 -- 2 3
// 2 -- 1 3
// 3 -- 1 2

For directed graphs, uses -> instead of --:

const directedGraph = new Graph<number>(true);
directedGraph.addEdge(1, 2);
directedGraph.addEdge(2, 3);

console.log(directedGraph.toString());
// Output:
// 1 -> 2
// 2 -> 3
// 3 ->

Complexity: O(V + E) Reference: graph.ts:42-56

Usage Examples

const socialNetwork = new Graph<string>();

// Add friendships (bidirectional)
socialNetwork.addEdge('Alice', 'Bob');
socialNetwork.addEdge('Alice', 'Charlie');
socialNetwork.addEdge('Bob', 'David');
socialNetwork.addEdge('Charlie', 'David');

console.log(socialNetwork.toString());
// Alice -- Bob Charlie
// Bob -- Alice David
// Charlie -- Alice David
// David -- Bob Charlie

Directed Graph (Web Pages)

const webGraph = new Graph<string>(true);

// Add hyperlinks (unidirectional)
webGraph.addEdge('home.html', 'about.html');
webGraph.addEdge('home.html', 'contact.html');
webGraph.addEdge('about.html', 'contact.html');
webGraph.addEdge('contact.html', 'home.html');

console.log(webGraph.toString());
// home.html -> about.html contact.html
// about.html -> contact.html
// contact.html -> home.html

Weighted Graph (Cities and Distances)

interface WeightedEdge {
  to: string;
  weight: number;
}

class WeightedGraph {
  private adjacencyList = new Map<string, WeightedEdge[]>();
  
  addEdge(from: string, to: string, weight: number) {
    if (!this.adjacencyList.has(from)) {
      this.adjacencyList.set(from, []);
    }
    this.adjacencyList.get(from)!.push({ to, weight });
  }
}

const cityGraph = new WeightedGraph();
cityGraph.addEdge('NYC', 'Boston', 215);
cityGraph.addEdge('NYC', 'Philadelphia', 95);
cityGraph.addEdge('Boston', 'Philadelphia', 310);

Graph Traversal

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking.

function dfs<T>(graph: Graph<T>, startValue: T): T[] {
  const visited = new Set<T>();
  const result: T[] = [];
  
  const vertex = graph.vertices.find(v => v.value === startValue);
  if (!vertex) return result;
  
  function traverse(vertex: Vertex<T>) {
    visited.add(vertex.value);
    result.push(vertex.value);
    
    for (const neighbor of vertex.edges) {
      if (!visited.has(neighbor.value)) {
        traverse(neighbor);
      }
    }
  }
  
  traverse(vertex);
  return result;
}

// Example:
const graph = new Graph<number>();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);

console.log(dfs(graph, 1)); // [1, 2, 4, 3]

Complexity: O(V + E) Use cases: Cycle detection, topological sorting, pathfinding

Breadth-First Search (BFS)

Explores all neighbors at the current depth before moving to the next level.

function bfs<T>(graph: Graph<T>, startValue: T): T[] {
  const visited = new Set<T>();
  const result: T[] = [];
  const queue: Vertex<T>[] = [];
  
  const vertex = graph.vertices.find(v => v.value === startValue);
  if (!vertex) return result;
  
  queue.push(vertex);
  visited.add(vertex.value);
  
  while (queue.length > 0) {
    const current = queue.shift()!;
    result.push(current.value);
    
    for (const neighbor of current.edges) {
      if (!visited.has(neighbor.value)) {
        visited.add(neighbor.value);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

// Example:
console.log(bfs(graph, 1)); // [1, 2, 3, 4]

Complexity: O(V + E) Use cases: Shortest path in unweighted graphs, level-order traversal

Common Graph Algorithms

Has Path

Check if a path exists between two vertices.

function hasPath<T>(
  graph: Graph<T>,
  start: T,
  end: T,
  visited = new Set<T>()
): boolean {
  if (start === end) return true;
  if (visited.has(start)) return false;
  
  visited.add(start);
  
  const vertex = graph.vertices.find(v => v.value === start);
  if (!vertex) return false;
  
  for (const neighbor of vertex.edges) {
    if (hasPath(graph, neighbor.value, end, visited)) {
      return true;
    }
  }
  
  return false;
}

Find Connected Components

Find all connected components in an undirected graph.

function findConnectedComponents<T>(graph: Graph<T>): T[][] {
  const visited = new Set<T>();
  const components: T[][] = [];
  
  function dfs(vertex: Vertex<T>, component: T[]) {
    visited.add(vertex.value);
    component.push(vertex.value);
    
    for (const neighbor of vertex.edges) {
      if (!visited.has(neighbor.value)) {
        dfs(neighbor, component);
      }
    }
  }
  
  for (const vertex of graph.vertices) {
    if (!visited.has(vertex.value)) {
      const component: T[] = [];
      dfs(vertex, component);
      components.push(component);
    }
  }
  
  return components;
}

Detect Cycle (Undirected Graph)

function hasCycle<T>(graph: Graph<T>): boolean {
  const visited = new Set<T>();
  
  function dfs(vertex: Vertex<T>, parent: T | null): boolean {
    visited.add(vertex.value);
    
    for (const neighbor of vertex.edges) {
      if (!visited.has(neighbor.value)) {
        if (dfs(neighbor, vertex.value)) return true;
      } else if (neighbor.value !== parent) {
        return true; // Back edge found (cycle)
      }
    }
    
    return false;
  }
  
  for (const vertex of graph.vertices) {
    if (!visited.has(vertex.value)) {
      if (dfs(vertex, null)) return true;
    }
  }
  
  return false;
}

Topological Sort (Directed Acyclic Graph)

function topologicalSort<T>(graph: Graph<T>): T[] {
  const visited = new Set<T>();
  const stack: T[] = [];
  
  function dfs(vertex: Vertex<T>) {
    visited.add(vertex.value);
    
    for (const neighbor of vertex.edges) {
      if (!visited.has(neighbor.value)) {
        dfs(neighbor);
      }
    }
    
    stack.unshift(vertex.value); // Add to front
  }
  
  for (const vertex of graph.vertices) {
    if (!visited.has(vertex.value)) {
      dfs(vertex);
    }
  }
  
  return stack;
}

Graph Representations

Adjacency List (This Implementation)

// Graph: 1--2, 1--3, 2--3
{
  1: [2, 3],
  2: [1, 3],
  3: [1, 2]
}

Pros: Space-efficient O(V + E), fast neighbor iteration Cons: Slower edge existence check O(V)

Adjacency Matrix

// Graph: 1--2, 1--3, 2--3
[
  [0, 1, 1],  // Vertex 1
  [1, 0, 1],  // Vertex 2
  [1, 1, 0]   // Vertex 3
]

Pros: O(1) edge existence check, simple representation Cons: O(V²) space, slow to iterate neighbors

Edge List

// Graph: 1--2, 1--3, 2--3
[
  { from: 1, to: 2 },
  { from: 1, to: 3 },
  { from: 2, to: 3 }
]

Pros: Simple, compact for sparse graphs Cons: Slow for most operations

Complexity Summary

Operation	Adjacency List	Adjacency Matrix
Add vertex	O(1)	O(V²)
Add edge	O(1)	O(1)
Remove vertex	O(E)	O(V²)
Remove edge	O(E)	O(1)
Check if edge exists	O(V)	O(1)
Find neighbors	O(1)	O(V)
Space	O(V + E)	O(V²)

This implementation uses adjacency lists, which are optimal for sparse graphs (E << V²).

Real-World Applications

Social Networks

Web Crawling

Web pages are vertices, hyperlinks are directed edges. PageRank algorithm, sitemap generation.

Navigation Systems

Dependency Resolution

Packages/tasks are vertices, dependencies are directed edges. Topological sort for build order.

Recommendation Systems

Users/items are vertices, interactions are edges. Collaborative filtering, similar items.

Network Flow

Nodes are vertices, connections are weighted edges. Max flow, min cut problems.

Graph Properties

Degree

function getDegree<T>(graph: Graph<T>, value: T): number {
  const vertex = graph.vertices.find(v => v.value === value);
  return vertex ? vertex.edges.length : 0;
}

In-degree (directed): Number of incoming edges Out-degree (directed): Number of outgoing edges Degree (undirected): Number of edges

Density

function getDensity<T>(graph: Graph<T>): number {
  const V = graph.vertices.length;
  let E = 0;
  
  for (const vertex of graph.vertices) {
    E += vertex.edges.length;
  }
  
  // For undirected graphs, each edge is counted twice
  if (!graph.directed) {
    E = E / 2;
  }
  
  const maxEdges = graph.directed ? V * (V - 1) : (V * (V - 1)) / 2;
  return E / maxEdges;
}

Sparse graph: E ≈ V (density ≈ 0) Dense graph: E ≈ V² (density ≈ 1)

Key Characteristics

Advantages:

Models complex relationships naturally
Flexible structure (add/remove vertices and edges)
Powerful algorithms for analysis
Adjacency list is space-efficient

Limitations:

Can be complex to implement and reason about
Some operations are expensive (finding edge, removing vertex)
Memory overhead for storing edges
No random access to elements

When to Use Graphs

Use graphs when:

Modeling relationships between entities
Finding paths or connections
Analyzing networks
Solving optimization problems
Working with hierarchies that can have cycles

Graph Choice Guide:

Sparse graph (few edges): Use adjacency list
Dense graph (many edges): Use adjacency matrix
Simple queries: Use edge list
Weighted edges: Add weight field to edge objects

Tree

Special case: connected acyclic graph

Binary Heap

Used in graph algorithms (Dijkstra, Prim)

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

​Graph

​Overview

​Graph Types

​Implementation

​Vertex Class

​Graph Class

​API Reference

​constructor(directed: boolean = false)

​addVertex(value: T): Vertex<T>

​addEdge(value1: T, value2: T): void

​toString(): string

​Usage Examples

​Undirected Graph (Social Network)

​Directed Graph (Web Pages)

​Weighted Graph (Cities and Distances)

​Graph Traversal

​Depth-First Search (DFS)

​Breadth-First Search (BFS)

​Common Graph Algorithms

​Has Path

​Find Connected Components

​Detect Cycle (Undirected Graph)

​Topological Sort (Directed Acyclic Graph)

​Graph Representations

​Adjacency List (This Implementation)

​Adjacency Matrix

​Edge List

​Complexity Summary

​Real-World Applications

​Graph Properties

​Degree

​Density

​Key Characteristics

​When to Use Graphs

​Related Data Structures

Tree

Binary Heap

Build docs developers (and LLMs) love

Graph

Overview

Graph Types

Implementation

Vertex Class

Graph Class

API Reference

constructor(directed: boolean = false)

addVertex(value: T): Vertex<T>

addEdge(value1: T, value2: T): void

toString(): string

Usage Examples

Undirected Graph (Social Network)

Directed Graph (Web Pages)

Weighted Graph (Cities and Distances)

Graph Traversal

Depth-First Search (DFS)

Breadth-First Search (BFS)

Common Graph Algorithms

Has Path

Find Connected Components

Detect Cycle (Undirected Graph)

Topological Sort (Directed Acyclic Graph)

Graph Representations

Adjacency List (This Implementation)

Adjacency Matrix

Edge List

Complexity Summary

Real-World Applications

Graph Properties

Degree

Density

Key Characteristics

When to Use Graphs

Related Data Structures