Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in JavaScript

Graph Implementation

Explore how to implement graph data structures in JavaScript using adjacency lists and linked lists. Understand the construction of directed and undirected graphs, including essential methods to add and print edges. This lesson equips you to build functional graph models for your coding interviews.

We'll cover the following...

Introduction

At this point, we’ve understood the theoretical logic behind graphs. In this lesson, we will use the knowledge we have to implement the graph data structure in JavaScript. Our graph will have directed edges.

The implementation will be based on the adjacency list model. The linked list class we created earlier will be used to represent adjacent vertices.

As a refresher, here is the illustration of the graph we’ll be producing using an adjacency list:

Graph Class

Graph class consists of two data members:

  • The total number of vertices in the graph
  • An array of linked lists to store adjacent vertices

So, let’s get down to the implementation!

Node.js
class Graph{
  constructor(vertices){
    //Total number of vertices in the graph
    this.vertices=vertices;
    //Defining an array which can hold LinkedLists equal to the number of vertices in the graph
    this.list=[];
    //Creating a new LinkedList for each vertex/index of the list
    for(i=0; i<vertices.length; i++){
      let temp=new LinkedList();
      this.list.push(temp);
    }
  }
}

We’ve laid down the foundation of our Graph class. The variable vertices contains an integer specifying the total number of vertices.

The second component is an array, which will act as our adjacency list. We simply have to run a loop and create a linked list for each vertex.

Additional Functionality

Now, we’ll add two methods to make this class functional:

  1. printGraph() - Prints the contents of the graph
  2. addEdge() - Connects a source with a destination
Node.js
"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
class Graph {
  constructor(vertices) {
    //Total number of vertices in the graph
    this.vertices = vertices;
    //Array that holds linked lists equal to the number of vertices in the graph
    this.list = [];
    //Creating a new linked list for each vertice of the graph
    var it;
    for (it = 0; it < vertices; it++) {
      let temp = new LinkedList();
      this.list.push(temp);
    }
  }
  addEdge(source, destination) {
    if (source < this.vertices && destination < this.vertices)
    //Since we are implementing a directed list, (0,1) is not the same as (1,0)
    this.list[source].insertAtHead(destination);
    //If we were to implement an undirected graph where (0,1)==(1,0), 
    //we would create an additional edge from destination to source too:
    //this.list[destination].insertAtHead(source);
  }
  printGraph() {
    console.log(">>Adjacency List of Directed Graph<<");
    var i;
    for (i = 0; i < this.list.length; i++) {
      process.stdout.write("|" + String(i) + "| => ");
      let temp = this.list[i].getHead();
      while (temp != null) {
        process.stdout.write("[" + String(temp.data) + "] -> ");
        temp = temp.nextElement;
      }
      console.log("null ");
    }
  }
}
let g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.printGraph();

Let’s break down the two new functions that we’ve implemented.

addEdge (source, destination)

Thanks to the graph constructor, source and destination are already stored as index of our array. This function simply inserts a destination vertex into the adjacency linked list of the source vertex by running the following line of code:

this.list[source].insertAtHead(destination)

One important thing to note is that we are implementing a directed graph, so addEdge(0, 1) is not equal to addEdge(1, 0).

printGraph()

This function uses a simple nested loop to iterate through the adjacency list. Each linked list is being traversed here.

Undirected graph

So far, we have covered the implementation of a directed graph.

In the case of an undirected graph, we will have to create an edge from the source to the destination and from the destination to the source, which makes it a bidirectional edge:

this.list[source].insertAtHead(destination)
this.list[destination].insertAtHead(source)