codelessgenie guide

A Practical Guide to Implementing Graph Data Structures in JavaScript

Graphs are one of the most versatile and powerful data structures in computer science, enabling us to model relationships between entities. From social networks (users as nodes, friendships as edges) to GPS navigation (locations as nodes, roads as edges with weights for distance), graphs underpin countless real-world systems. Unlike linear structures like arrays or linked lists, or hierarchical structures like trees, graphs have no inherent order—making them uniquely suited for modeling complex, interconnected data. In this guide, we’ll demystify graphs, explore their core concepts, and walk through a step-by-step implementation in JavaScript. By the end, you’ll be able to build, traverse, and manipulate graphs to solve practical problems.

Table of Contents

  1. What is a Graph?
  2. Graph Representations in JavaScript
  3. Implementing a Graph Class in JavaScript
  4. Graph Traversal Algorithms
  5. Practical Examples
  6. Conclusion
  7. References

1. What is a Graph?

A graph is a collection of vertices (or nodes) connected by edges (or links). Formally, a graph is defined as ( G = (V, E) ), where ( V ) is a set of vertices and ( E ) is a set of edges.

1.1 Core Terminology

  • Vertex (Node): The fundamental unit of a graph (e.g., a user in a social network).
  • Edge: A connection between two vertices (e.g., a friendship between two users).
  • Degree: The number of edges connected to a vertex (in directed graphs, this splits into in-degree and out-degree).
  • Path: A sequence of vertices where each consecutive pair is connected by an edge (e.g., A → B → C).
  • Cycle: A path that starts and ends at the same vertex (e.g., A → B → C → A).

1.2 Types of Graphs

Graphs are classified based on edge direction, weight, and structure:

Undirected vs. Directed Graphs

  • Undirected Graph: Edges have no direction (e.g., a friendship: if A is friends with B, B is friends with A).
  • Directed Graph (Digraph): Edges have a direction (e.g., a Twitter follow: if A follows B, B may not follow A).

Weighted vs. Unweighted Graphs

  • Unweighted Graph: Edges have no associated value (only presence/absence matters).
  • Weighted Graph: Edges have a numerical value (e.g., distance between cities, cost of a flight).

Special Cases

  • Tree: An acyclic (no cycles) undirected graph with exactly ( V-1 ) edges.
  • DAG (Directed Acyclic Graph): A directed graph with no cycles (used in task scheduling).
  • Complete Graph: Every pair of distinct vertices is connected by an edge.

2. Graph Representations in JavaScript

To implement a graph in code, we need a way to store vertices and their connections. The two most common representations are adjacency lists and adjacency matrices.

2.1 Adjacency List

An adjacency list uses a collection (e.g., an object or Map) where each key is a vertex, and the value is a list of vertices connected to it.

Example (Undirected, Unweighted):

// Adjacency list for an undirected graph
const adjacencyList = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
};

Example (Directed, Weighted):
For weighted graphs, store edges as objects with node and weight:

const adjacencyList = {
  'A': [{ node: 'B', weight: 5 }, { node: 'C', weight: 3 }],
  'B': [{ node: 'D', weight: 2 }],
  'C': [{ node: 'D', weight: 4 }],
  'D': []
};

Pros:

  • Efficient for sparse graphs (most real-world graphs are sparse).
  • Uses less space: ( O(V + E) ) (stores only existing edges).
  • Fast to iterate over a vertex’s neighbors (( O(k) ), where ( k ) is the number of neighbors).

Cons:

  • Checking if an edge exists between two vertices is ( O(k) ) (must iterate the neighbor list).

2.2 Adjacency Matrix

An adjacency matrix is a 2D array where matrix[i][j] indicates if there’s an edge from vertex ( i ) to vertex ( j ). For weighted graphs, matrix[i][j] stores the edge weight (use 0 or Infinity for no edge).

Example (Undirected, Unweighted):

// Vertices: A(0), B(1), C(2), D(3)
const adjacencyMatrix = [
  [0, 1, 1, 0], // A is connected to B(1), C(2)
  [1, 0, 0, 1], // B is connected to A(0), D(3)
  [1, 0, 0, 1], // C is connected to A(0), D(3)
  [0, 1, 1, 0]  // D is connected to B(1), C(2)
];

Pros:

  • ( O(1) ) time to check if an edge exists between two vertices.
  • Simple to implement for dense graphs.

Cons:

  • Wastes space for sparse graphs: ( O(V^2) ) space complexity.
  • Slow to iterate over a vertex’s neighbors (( O(V) ) time).

2.3 When to Use Which?

  • Adjacency List: Use for sparse graphs (most real-world cases), when you need to iterate neighbors frequently, or when space is a concern.
  • Adjacency Matrix: Use for dense graphs, when edge existence checks are critical, or when working with small graphs (e.g., up to 1000 vertices).

3. Implementing a Graph Class in JavaScript

We’ll implement a flexible Graph class using an adjacency list, supporting both directed/undirected and weighted/unweighted graphs.

3.1 Constructor: Initialization

The constructor initializes the adjacency list and configures the graph as directed/undirected and weighted/unweighted.

class Graph {
  constructor(directed = false, weighted = false) {
    this.adjacencyList = {}; // Stores vertices and their neighbors
    this.directed = directed; // True for directed graphs
    this.weighted = weighted; // True for weighted graphs
  }
}

3.2 Adding Vertices and Edges

addVertex(vertex)

Adds a vertex to the graph (if it doesn’t already exist).

addVertex(vertex) {
  if (!this.adjacencyList[vertex]) {
    this.adjacencyList[vertex] = []; // Initialize with empty neighbor list
  }
}

addEdge(vertex1, vertex2, weight)

Adds an edge between vertex1 and vertex2. For undirected graphs, add edges in both directions. For weighted graphs, store the weight.

addEdge(vertex1, vertex2, weight) {
  // Check if vertices exist (optional: throw error if not)
  if (!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) {
    throw new Error("Both vertices must exist in the graph.");
  }

  // Add edge from vertex1 to vertex2
  if (this.weighted) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
  } else {
    this.adjacencyList[vertex1].push(vertex2);
  }

  // For undirected graphs, add edge from vertex2 to vertex1
  if (!this.directed) {
    if (this.weighted) {
      this.adjacencyList[vertex2].push({ node: vertex1, weight });
    } else {
      this.adjacencyList[vertex2].push(vertex1);
    }
  }
}

3.3 Removing Vertices and Edges

removeEdge(vertex1, vertex2)

Removes the edge between vertex1 and vertex2.

removeEdge(vertex1, vertex2) {
  if (!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) {
    throw new Error("Both vertices must exist in the graph.");
  }

  // Remove vertex2 from vertex1's neighbors
  this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(neighbor => 
    this.weighted ? neighbor.node !== vertex2 : neighbor !== vertex2
  );

  // For undirected graphs, remove vertex1 from vertex2's neighbors
  if (!this.directed) {
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(neighbor => 
      this.weighted ? neighbor.node !== vertex1 : neighbor !== vertex1
    );
  }
}

removeVertex(vertex)

Removes a vertex and all edges connected to it.

removeVertex(vertex) {
  if (!this.adjacencyList[vertex]) return;

  // Remove all edges pointing to the vertex (from other vertices)
  Object.keys(this.adjacencyList).forEach(currentVertex => {
    this.removeEdge(currentVertex, vertex);
  });

  // Delete the vertex itself
  delete this.adjacencyList[vertex];
}

3.4 Handling Weighted Graphs

The weighted flag in the constructor enables weighted edges. Let’s test the class with a weighted, directed graph:

// Create a directed, weighted graph
const flightGraph = new Graph(true, true);

// Add vertices (cities)
flightGraph.addVertex("NYC");
flightGraph.addVertex("London");
flightGraph.addVertex("Tokyo");

// Add edges (flights with distances in miles)
flightGraph.addEdge("NYC", "London", 3456);
flightGraph.addEdge("London", "Tokyo", 5959);
flightGraph.addEdge("NYC", "Tokyo", 6739);

console.log(flightGraph.adjacencyList);
/* Output:
{
  NYC: [ { node: 'London', weight: 3456 }, { node: 'Tokyo', weight: 6739 } ],
  London: [ { node: 'Tokyo', weight: 5959 } ],
  Tokyo: []
}
*/

4. Graph Traversal Algorithms

Traversal is the process of visiting every vertex in a graph systematically. Two foundational algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).

4.1 Breadth-First Search (BFS)

BFS explores vertices level by level, starting from a root vertex. It uses a queue to track vertices to visit next.

Use Cases:

  • Finding the shortest path in an unweighted graph.
  • Level-order traversal (e.g., social network “friends of friends”).

Implementation:

bfs(startVertex) {
  const queue = [startVertex]; // Queue for BFS
  const visited = new Set(); // Track visited vertices
  const result = []; // Store traversal order

  visited.add(startVertex);

  while (queue.length > 0) {
    const currentVertex = queue.shift(); // Dequeue (FIFO)
    result.push(currentVertex);

    // Visit all neighbors of currentVertex
    this.adjacencyList[currentVertex].forEach(neighbor => {
      const neighborNode = this.weighted ? neighbor.node : neighbor;
      if (!visited.has(neighborNode)) {
        visited.add(neighborNode);
        queue.push(neighborNode);
      }
    });
  }

  return result;
}

Example:

// Undirected, unweighted graph
const socialGraph = new Graph();
socialGraph.addVertex("Alice");
socialGraph.addVertex("Bob");
socialGraph.addVertex("Charlie");
socialGraph.addVertex("Diana");
socialGraph.addEdge("Alice", "Bob");
socialGraph.addEdge("Alice", "Charlie");
socialGraph.addEdge("Bob", "Diana");

console.log(socialGraph.bfs("Alice")); // [ 'Alice', 'Bob', 'Charlie', 'Diana' ]

4.2 Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking. It uses a stack (iterative) or recursion (call stack).

Iterative DFS (Stack-Based)

dfsIterative(startVertex) {
  const stack = [startVertex]; // Stack for DFS
  const visited = new Set();
  const result = [];

  visited.add(startVertex);

  while (stack.length > 0) {
    const currentVertex = stack.pop(); // Pop (LIFO)
    result.push(currentVertex);

    // Visit neighbors in reverse order to mimic recursive DFS
    this.adjacencyList[currentVertex].reverse().forEach(neighbor => {
      const neighborNode = this.weighted ? neighbor.node : neighbor;
      if (!visited.has(neighborNode)) {
        visited.add(neighborNode);
        stack.push(neighborNode);
      }
    });
  }

  return result;
}

Recursive DFS

dfsRecursive(startVertex, visited = new Set(), result = []) {
  if (!startVertex) return result;

  visited.add(startVertex);
  result.push(startVertex);

  // Recursively visit unvisited neighbors
  this.adjacencyList[startVertex].forEach(neighbor => {
    const neighborNode = this.weighted ? neighbor.node : neighbor;
    if (!visited.has(neighborNode)) {
      this.dfsRecursive(neighborNode, visited, result);
    }
  });

  return result;
}

Example:

console.log(socialGraph.dfsIterative("Alice")); // [ 'Alice', 'Charlie', 'Bob', 'Diana' ]
console.log(socialGraph.dfsRecursive("Alice")); // [ 'Alice', 'Bob', 'Diana', 'Charlie' ] (order may vary)

5. Practical Examples

5.1 Social Network Friend Suggestions

Use BFS to find “friends of friends” (2nd-degree connections) for a user:

function getFriendSuggestions(graph, user, depth = 2) {
  const queue = [[user, 0]]; // [vertex, current depth]
  const visited = new Set([user]);
  const suggestions = [];

  while (queue.length > 0) {
    const [currentUser, currentDepth] = queue.shift();

    if (currentDepth > 0 && currentDepth <= depth) {
      suggestions.push(currentUser); // Add non-direct friends within depth
    }

    if (currentDepth < depth) {
      graph.adjacencyList[currentUser].forEach(friend => {
        const friendNode = graph.weighted ? friend.node : friend;
        if (!visited.has(friendNode)) {
          visited.add(friendNode);
          queue.push([friendNode, currentDepth + 1]);
        }
      });
    }
  }

  return suggestions;
}

// For socialGraph (Alice is connected to Bob/Charlie; Bob is connected to Diana)
console.log(getFriendSuggestions(socialGraph, "Alice")); // [ 'Bob', 'Charlie', 'Diana' ] (depth=2)

5.2 Finding Connected Components

A connected component is a subgraph where all vertices are reachable from each other. Use DFS/BFS to find all components in an undirected graph:

function findConnectedComponents(graph) {
  const visited = new Set();
  const components = [];

  for (const vertex of Object.keys(graph.adjacencyList)) {
    if (!visited.has(vertex)) {
      const component = graph.dfsRecursive(vertex, visited); // Use DFS to find component
      components.push(component);
    }
  }

  return components;
}

// Example: Graph with two disconnected components
const disconnectedGraph = new Graph();
disconnectedGraph.addVertex("A");
disconnectedGraph.addVertex("B");
disconnectedGraph.addVertex("C");
disconnectedGraph.addVertex("D");
disconnectedGraph.addEdge("A", "B");
disconnectedGraph.addEdge("C", "D");

console.log(findConnectedComponents(disconnectedGraph)); // [ [ 'A', 'B' ], [ 'C', 'D' ] ]

6. Conclusion

Graphs are indispensable for modeling relationships in data. In this guide, we covered:

  • Core graph concepts (vertices, edges, types).
  • Implementing a flexible Graph class in JavaScript with adjacency lists.
  • Traversal algorithms (BFS/DFS) for exploring graphs.
  • Practical use cases like friend suggestions and connected components.

For advanced applications, explore shortest-path algorithms (Dijkstra’s, Bellman-Ford), cycle detection, or graph optimization (minimum spanning trees).

7. References