Graphs are data structures with connected nodes/vertexes. We are using the adjacency list approach to represent a Graph here.
NOTE
In this article, we are discussing the implementation of Graph in JavaScript and TypeScript.
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-
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-
| Source Code of | Implementation Code | Demo Code | Test Code |
|---|---|---|---|
| JavaScript Implementation |  GitHub | GitHub | GitHub |
| TypeScript Implementation | GitHub | GitHub | GitHub |
Related Data Structures
| Command | Details |
|---|---|
| Binary Heap | Binary Heap |
Other Code Implementations
Use the following links to check the BFS implementation in other programming languages-
