Data Structure: Graph in JavaScript and TypeScript

Graphs are data structures with connected nodes/vertexes. We are using the adjacency list approach to represent a Graph here.

Graph of cities
Graph of cities

NOTE

In this article, we are discussing the implementation of Graph in JavaScript and TypeScript.

Check the link below to check the details of Graph-

Implementation

We are storing the graph information in an adjacency list. Using JavaScript Map to store the elements and each element has an array. It will look like the below when represented in a JS object-

Graph elements saved in an Adjacency List
Graph elements saved in an Adjacency List

Here is how we can implement a graph data structure in JavaScript and TypeScript-

Step #1: Graph Class

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
}

Step #2: Add Vertex

class Graph {
  // ...

  // Add vertex to graph
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  
 //...
}

Step #3: Remove Vertex

class Graph {
  // ...

   // Remove vertex from graph
  removeVertex(vertex) {
    // If the vertex does not exist then no need for processing
    if (!this.adjacencyList[vertex]) {
      return;
    }

    // Remove all the edges that has the provided vertex
    for (const vertexItem of this.adjacencyList[vertex]) {
      this.removeEdge(vertex, vertexItem);
    }

    // Remove the reference of the vertext completely
    delete this.adjacencyList[vertex];
  }
  
  //...
}

Step #4: Add Edge

class Graph {
  // ...

  // Add edge to graph
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
  
  // ...
}

Step #5: Remove Edge

class Graph {
  // ...

  // Add remove edge from graph
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }
  
  // ...
}

Step #6: DFS

class Graph {
  // ...

  // Depth first search for nodes
  dfs(start) {
    const result = [];
    const visited = {[start]: true};
    const stack = [start];

    while(stack.length) {
      const currentVertex = stack.pop();
      result.push(currentVertex);

      for (const neightbor of this.adjacencyList[currentVertex]) {
        if(!visited[neightbor]) {
          visited[neightbor] = true;

          stack.push(neightbor);
        }
      }
    }

    return result;
  }
  
  // ...
}

Step #7: DFS with Recursion

class Graph {
  // ...

  // Depth First Search for the nodes
  // Using recursion
  dfsRecursive(start) {
    const result = [];
    const visited = {};

    (function processDfs(adjacencyList, vertex) {
      if (!vertex) {
        return null;
      }

      visited[vertex] = true;
      result.push(vertex);

      for (let neighbor of adjacencyList[vertex]) {
        if (!visited[neighbor]) {
          processDfs(adjacencyList, neighbor);
        }
      }
    })(this.adjacencyList, start);

    return result;
  }
  
  // ...
}

Step #8: BFS

class Graph {
  // ...

  // Breadth first search
  bfs(start) {
    const result = [];
    const visited = { [start]: true };
    const stack = [start];

    while (stack.length) {
      const currentVertex = stack.shift(); // Only difference between BFS and DFS is this line
      result.push(currentVertex);

      for (const neightbor of this.adjacencyList[currentVertex]) {
        if (!visited[neightbor]) {
          visited[neightbor] = true;

          stack.push(neightbor);
        }
      }
    }

    return result;
  }
  
  // ...
}

Full Source Code

Here is the full source code of Graph implementation-

// graph/graph.js

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  // Add vertex to graph
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // Remove vertex from graph
  removeVertex(vertex) {
    // If the vertex does not exist then no need for processing
    if (!this.adjacencyList[vertex]) {
      return;
    }

    // Remove all the edges that has the provided vertex
    for (const vertexItem of this.adjacencyList[vertex]) {
      this.removeEdge(vertex, vertexItem);
    }

    // Remove the reference of the vertext completely
    delete this.adjacencyList[vertex];
  }

  // Add edge to graph
  addEdge(vertex1, vertex2) {
    // Checking required

    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  // Add remove edge from graph
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }

  // Depth first search for nodes
  dfs(start) {
    const result = [];
    const visited = { [start]: true };
    const stack = [start];

    while (stack.length) {
      const currentVertex = stack.pop(); // Only difference between BFS and DFS is this line
      result.push(currentVertex);

      for (const neightbor of this.adjacencyList[currentVertex]) {
        if (!visited[neightbor]) {
          visited[neightbor] = true;

          stack.push(neightbor);
        }
      }
    }

    return result;
  }

  // Depth First Search for the nodes
  // Using recursion
  dfsRecursive(start) {
    const result = [];
    const visited = {};

    (function processDfs(adjacencyList, vertex) {
      if (!vertex) {
        return null;
      }

      visited[vertex] = true;
      result.push(vertex);

      for (let neighbor of adjacencyList[vertex]) {
        if (!visited[neighbor]) {
          processDfs(adjacencyList, neighbor);
        }
      }
    })(this.adjacencyList, start);

    return result;
  }

  // Breadth first search
  bfs(start) {
    const result = [];
    const visited = { [start]: true };
    const stack = [start];

    while (stack.length) {
      const currentVertex = stack.shift(); // Only difference between BFS and DFS is this line
      result.push(currentVertex);

      for (const neightbor of this.adjacencyList[currentVertex]) {
        if (!visited[neightbor]) {
          visited[neightbor] = true;

          stack.push(neightbor);
        }
      }
    }

    return result;
  }
}

export default Graph;

Demo

Use the following code to check the implementation-

// graph/demo.js

import Graph from "./graph.js";

// Create a new Graph
let bigBoxGraph = new Graph();

console.log("\n---------- Graph - Add Vertex example -----------\n");

bigBoxGraph.addVertex('Paris');
bigBoxGraph.addVertex('Tokyo');
bigBoxGraph.addVertex('Rome');
bigBoxGraph.addVertex('Berlin');
bigBoxGraph.addVertex('Moscow');
bigBoxGraph.addVertex('London');
bigBoxGraph.addVertex('Some Remote Place');


console.log(bigBoxGraph.adjacencyList);


console.log("\n---------- Graph - Add Edge example -----------\n");

bigBoxGraph.addEdge('Paris', 'Tokyo');
bigBoxGraph.addEdge('Paris', 'Rome');
bigBoxGraph.addEdge('Paris', 'London');
bigBoxGraph.addEdge('Tokyo', 'London');
bigBoxGraph.addEdge('Rome', 'London');
bigBoxGraph.addEdge('Berlin', 'Moscow');
bigBoxGraph.addEdge('Berlin', 'London');
bigBoxGraph.addEdge('Moscow', 'London');
bigBoxGraph.addEdge('Moscow', 'Some Remote Place');


console.log(bigBoxGraph.adjacencyList);


console.log("\n---------- Graph - DFS example -----------\n");

console.log("DFS starting from London: ", bigBoxGraph.dfs('London'));
console.log("DFS starting from Moscow: ", bigBoxGraph.dfs('Moscow'));
console.log("DFS starting from Tokyo: ", bigBoxGraph.dfs('Tokyo'));


console.log("\n---------- Graph - DFS (using Recursion) example -----------\n");

console.log("DFS starting from London: ", bigBoxGraph.dfsRecursive('London'));
console.log("DFS starting from Moscow: ", bigBoxGraph.dfsRecursive('Moscow'));
console.log("DFS starting from Tokyo: ", bigBoxGraph.dfsRecursive('Tokyo'));


console.log("\n---------- Graph - BFS example -----------\n");

console.log("BFS starting from London: ", bigBoxGraph.bfs('London'));
console.log("BFS starting from Moscow: ", bigBoxGraph.bfs('Moscow'));
console.log("BFS starting from Tokyo: ", bigBoxGraph.bfs('Tokyo'));


console.log("\n---------- Graph - Remove Edge example -----------\n");

bigBoxGraph.removeEdge('Paris', 'Tokyo');
bigBoxGraph.removeEdge('Tokyo', 'London');
bigBoxGraph.removeEdge('Moscow', 'Berlin');


console.log(bigBoxGraph.adjacencyList);


console.log("\n---------- Graph - Remove Vertex example -----------\n");

bigBoxGraph.removeVertex('Berlin');

console.log(bigBoxGraph.adjacencyList);

Output:

Here is the output of the above demo code-

---------- Graph - Add Vertex example -----------

{
  Paris: [],
  Tokyo: [],
  Rome: [],
  Berlin: [],
  Moscow: [],
  London: [],
  'Some Remote Place': []
}

---------- Graph - Add Edge example -----------

{
  Paris: [ 'Tokyo', 'Rome', 'London' ],
  Tokyo: [ 'Paris', 'London' ],
  Rome: [ 'Paris', 'London' ],
  Berlin: [ 'Moscow', 'London' ],
  Moscow: [ 'Berlin', 'London', 'Some Remote Place' ],
  London: [ 'Paris', 'Tokyo', 'Rome', 'Berlin', 'Moscow' ],
  'Some Remote Place': [ 'Moscow' ]
}

---------- Graph - DFS example -----------

DFS starting from London:  [
  'London',
  'Moscow',
  'Some Remote Place',
  'Berlin',
  'Rome',
  'Tokyo',
  'Paris'
]
DFS starting from Moscow:  [
  'Moscow',
  'Some Remote Place',
  'London',
  'Rome',
  'Tokyo',
  'Paris',
  'Berlin'
]
DFS starting from Tokyo:  [
  'Tokyo',
  'London',
  'Moscow',
  'Some Remote Place',
  'Berlin',
  'Rome',
  'Paris'
]

---------- Graph - DFS (using Recursion) example -----------

DFS starting from London:  [
  'London',
  'Paris',
  'Tokyo',
  'Rome',
  'Berlin',
  'Moscow',
  'Some Remote Place'
]
DFS starting from Moscow:  [
  'Moscow',
  'Berlin',
  'London',
  'Paris',
  'Tokyo',
  'Rome',
  'Some Remote Place'
]
DFS starting from Tokyo:  [
  'Tokyo',
  'Paris',
  'Rome',
  'London',
  'Berlin',
  'Moscow',
  'Some Remote Place'
]

---------- Graph - BFS example -----------

BFS starting from London:  [
  'London',
  'Paris',
  'Tokyo',
  'Rome',
  'Berlin',
  'Moscow',
  'Some Remote Place'
]
BFS starting from Moscow:  [
  'Moscow',
  'Berlin',
  'London',
  'Some Remote Place',
  'Paris',
  'Tokyo',
  'Rome'
]
BFS starting from Tokyo:  [
  'Tokyo',
  'Paris',
  'London',
  'Rome',
  'Berlin',
  'Moscow',
  'Some Remote Place'
]

---------- Graph - Remove Edge example -----------

{
  Paris: [ 'Rome', 'London' ],
  Tokyo: [],
  Rome: [ 'Paris', 'London' ],
  Berlin: [ 'London' ],
  Moscow: [ 'London', 'Some Remote Place' ],
  London: [ 'Paris', 'Rome', 'Berlin', 'Moscow' ],
  'Some Remote Place': [ 'Moscow' ]
}

---------- Graph - Remove Vertex example -----------

{
  Paris: [ 'Rome', 'London' ],
  Tokyo: [],
  Rome: [ 'Paris', 'London' ],
  Moscow: [ 'London', 'Some Remote Place' ],
  London: [ 'Paris', 'Rome', 'Moscow' ],
  'Some Remote Place': [ 'Moscow' ]
}

Testing

Here is the test cases for the Graph implementation-

Tests are implemented with ‘vitest‘.

// graph.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Graph from "./graph";

describe("Graph", () => {
  let graph;

  beforeEach(() => {
    graph = new Graph();
    graph.addVertex("Paris");
    graph.addVertex("Tokyo");
    graph.addVertex("Rome");
    graph.addVertex("Berlin");
    graph.addVertex("Moscow");
    graph.addVertex("London");
  });

  describe("Add vertext to graph", () => {
    it("Should have correct length", () => {
      expect(Object.keys(graph.adjacencyList).length).toBe(6);
    });

    it("Should have correct sequence of items", () => {
      expect(Object.keys(graph.adjacencyList)).toMatchObject([
        "Paris",
        "Tokyo",
        "Rome",
        "Berlin",
        "Moscow",
        "London",
      ]);
    });
  });

  describe("Add edge to graph", () => {
    it("Should have correct edges", () => {
      graph.addEdge("Paris", "Tokyo");
      graph.addEdge("Paris", "Rome");
      graph.addEdge("Paris", "London");
      graph.addEdge("Tokyo", "London");
      graph.addEdge("Rome", "London");
      graph.addEdge("Berlin", "Moscow");
      graph.addEdge("Berlin", "London");
      graph.addEdge("Moscow", "London");

      expect(graph.adjacencyList.Paris).toMatchObject([
        "Tokyo",
        "Rome",
        "London",
      ]);
      expect(graph.adjacencyList.Tokyo).toMatchObject(["Paris", "London"]);
      expect(graph.adjacencyList.Rome).toMatchObject(["Paris", "London"]);
      expect(graph.adjacencyList.Berlin).toMatchObject(["Moscow", "London"]);
      expect(graph.adjacencyList.Moscow).toMatchObject(["Berlin", "London"]);
      expect(graph.adjacencyList.London).toMatchObject([
        "Paris",
        "Tokyo",
        "Rome",
        "Berlin",
        "Moscow",
      ]);
    });
  });

  describe("Remove edge from graph", () => {
    beforeEach(() => {
      graph.addEdge("Paris", "Tokyo");
      graph.addEdge("Paris", "Rome");
      graph.addEdge("Paris", "London");
      graph.addEdge("Tokyo", "London");
      graph.addEdge("Rome", "London");
      graph.addEdge("Berlin", "Moscow");
      graph.addEdge("Berlin", "London");
      graph.addEdge("Moscow", "London");
    });

    it("Should have correct edges", () => {
      graph.removeEdge("Paris", "Tokyo");
      graph.removeEdge("Tokyo", "London");
      graph.removeEdge("Moscow", "Berlin");

      expect(graph.adjacencyList.Paris).toMatchObject(["Rome", "London"]);
      expect(graph.adjacencyList.Rome).toMatchObject(["Paris", "London"]);
      expect(graph.adjacencyList.Moscow).toMatchObject(["London"]);
      expect(graph.adjacencyList.London).toMatchObject([
        "Paris",
        "Rome",
        "Berlin",
        "Moscow",
      ]);
    });
  });

  describe("Remove vertex from graph", () => {
    it("Should have correct edges", () => {
      graph.removeVertex("Berlin");

      expect(graph.adjacencyList.Berlin).toBeUndefined();
    });
  });

  describe("Traverse graph nodes using DFS", () => {
    beforeEach(() => {
      graph.addEdge("Paris", "Tokyo");
      graph.addEdge("Paris", "Rome");
      graph.addEdge("Paris", "London");
      graph.addEdge("Tokyo", "London");
      graph.addEdge("Rome", "London");
      graph.addEdge("Berlin", "Moscow");
      graph.addEdge("Berlin", "London");
      graph.addEdge("Moscow", "London");
    });

    it("Should traverse the graph correctly", () => {
      expect(graph.dfs("London")).toMatchObject([
        "London",
        "Moscow",
        "Berlin",
        "Rome",
        "Tokyo",
        "Paris",
      ]);
      expect(graph.dfs("Moscow")).toMatchObject([
        "Moscow",
        "London",
        "Rome",
        "Tokyo",
        "Paris",
        "Berlin",
      ]);
      expect(graph.dfs("Tokyo")).toMatchObject([
        "Tokyo",
        "London",
        "Moscow",
        "Berlin",
        "Rome",
        "Paris",
      ]);
    });
  });

  describe("Traverse graph nodes using BFS", () => {
    beforeEach(() => {
      graph.addEdge("Paris", "Tokyo");
      graph.addEdge("Paris", "Rome");
      graph.addEdge("Paris", "London");
      graph.addEdge("Tokyo", "London");
      graph.addEdge("Rome", "London");
      graph.addEdge("Berlin", "Moscow");
      graph.addEdge("Berlin", "London");
      graph.addEdge("Moscow", "London");
    });

    it("Should traverse the graph correctly", () => {
      expect(graph.bfs("London")).toMatchObject([
        "London",
        "Paris",
        "Tokyo",
        "Rome",
        "Berlin",
        "Moscow",
      ]);
      expect(graph.bfs("Moscow")).toMatchObject([
        "Moscow",
        "Berlin",
        "London",
        "Paris",
        "Tokyo",
        "Rome",
      ]);
      expect(graph.bfs("Tokyo")).toMatchObject([
        "Tokyo",
        "Paris",
        "London",
        "Rome",
        "Berlin",
        "Moscow",
      ]);
    });
  });
});

Source Code

Use the following links to get the source code used in this article-

Related Data Structures

CommandDetails
Binary Heap Binary Heap

Other Code Implementations

Use the following links to check the BFS implementation in other programming languages-

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.