Graph Data Structures in JavaScript — Part 1: Graph Basics

Data Structures are of two types — Linear and Non-Linear. Arrays, Linked List, Stacks, Queues, etc comes under linear data structures whereas Trees, BST, Graphs, etc comes under non-linear data structures. In this post, we will cover Graph data structure and its implementation in JavaScript.

Graph Basics and its Terminology

A graph is a set of nodes (or vertices) connected by edges (or connections).

Graphs are used in many real-life applications. Graphs are used to represent roads, flights, communications, and social networks. for eg, We can use graphs to calculate the shortest route between two cities, similarly for social networks like Facebook, Linkedin we can represent each person as a vertex and their friendships as an edge.

Graph Data Structure (image source- geeksforgeeks)

Graphs can be undirected where the edges don’t have any directions (bidirectional) and directed (digraph) where edges have directions.

Undirected and Directed Graph (images source — geeksforgeeks)

Graphs can also be weighted where edges have weights and unweighted where the edges don't have weights.

Weighted Graph (images source — geeksforgeeks)

Representing Graphs

We can represent graphs in two primary ways —

1. Adjacency Matrix
2. Adjacency List

We will represent the graph below in both ways.

(image source — geeksforgeeks)

Adjacency Matrix

Here, we use a two-dimensional array (NxN matrix) to represent the graph. If there is a connection between two vertices then we add 1 else we add 0.
If the graph has fewer connections, then we call it a Sparse Graph and the matrix will waste a lot of space in representing it. So we avoid using the adjacent matrix to represent sparse graphs.

Adjacency Matrix

Adjacency List

Here we maintain a data structure to store all vertices and a list of their adjacent vertices. For storing each vertex we can use hashmaps and for storing the list of adjacent vertices we can use arrays.

Adjacency List

Adjacency List Graph Implementation

Now comes the real part. We will be implementing the Adjacency list.

Let’s start with a simple Graph class.

Graph Class

In the constructor, we create an object to store the adjacency list Also, we are creating one variable to tell what type of graph it is — directed or undirected graph.

Next, we will implement some basic graph methods.

Add Vertex Method

Add Vertex Method

Here we define addVertex method which accepts a vertex as an argument and adds it to the graph. We are assigning an empty array to this new vertex, and later we will store adjacent vertices in it.

Let’s make a new Directed Graph

const g = new Graph(true); // Directed Graph
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');

and it will look like —

{
    A: [],
    B: [],
    C: [],
}

Add Edge Method

Add Edge Vertex

Here we define addEdge method which accepts two vertices as arguments viz. a source vertex (vertex1), and a destination vertex (vertex2). We add an edge between source and destination vertex by adding the destination vertex to the array, if the graph is undirected (bidirectional) then we add an edge between destination and source as well by adding the source vertex to the array.

Let’s add some edges (Directed Graph)—

g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'C');
g.addEdge('B', 'A');
g.addEdge('C', 'A');

Now the adjacency list will look like this —

{
    A: [B, C],
    B: [A, C],
    C: [A]
}

Remove Edge Method

Remove Edge Method

Here we define removeEdge method which accepts two vertices as arguments viz. a source vertex (v1), and a destination vertex (v2). If the graph is directed then we have to remove the destination vertex from the list of source vertex and vice versa for the undirected graph.

Let say we want to remove the edge between A and C (Directed graph) —

g.removeEdge('A', 'C');

After executing the above removeEdge method the adjacency list will look like

{
    A: [B],
    B: [A, C],
    C: [A]
}

Remove Vertex Method

Remove Vertex Method

Here we define removeVertex method which accepts a vertex as an arguments. Along with removing the vertex we also have to remove all its edges. For that we first loop over all its adjacent vertices and call our removeEdge function with the adjacent vertex and the vertex we want to delete. Later we delete the vertex from the adjacency list.

Let say we want to remove the vertex B (Directed graph) —

g.removeVertex('B')

After executing the above removeVertex method the adjacency list will look like

{
    A: [],
    C: [A]
}

Hope you got the basic idea of how we can represent a graph using an adjacency list. We can add more checks to it to handle errors.

The Github link for the Adjacency List is

karan1205/javascript-things

Don’t miss — Graph Data Structures in JavaScript — Part 2: Graph Traversals