Implementing Graphs Using Adjacency List

Hello everyone! 👋🏻 Welcome back to another post in Data Structures 101 Series 🥷

In the previous post, we learned what is a graph data structure, applications of graphs, and ways of implementing the graphs.

We learned that we can implement graphs using two ways:

Adjacency List.
Adjacency Matrix.

In this post, we are going to learn how to implement graphs using an adjacency list.

✨ Implementing Graph Using Adjacency List

We are going to implement this graph using an adjacency list.

Note: I have chosen a small and simple graph just to make things simpler for you. The main focus is to understand the concept.

If we map the nodes and edges on the list, it will look something like this:

graph = {
 A: ['B'],
 B: ['C'],
 C: ['E'],
 D: ['B'],
 E: ['D', 'F'],
}

We have an object in which keys are vertices. The value of every vertex is an array of vertices. These vertices are the connected nodes. For example, A is connected to B, B is connected to C and E is connected to both D and F.

For the sake of simplicity, we have used a simple graph, you can create any complex graph.

Let's implement it in javascript now!

First, we will create a Graph class in which we will create a new list that is going to be a Map data structure of JavaScript.

Note: We are using Map for having unique values for vertices. You can use a plain object as well. Depends on your use case.

class Graph {
  constructor() {
    // we are going to use Map() of javascript because it can't hold duplicate values.
    this.list = new Map();
  }
}

✨ Add Vertex

First, we need an operation to add a vertex into our new graph, for this purpose we have the addVertex method which adds a new vertex to our graph.

addVertex(newVertex) {
   // We will set the newVertex value as a key in map.
   // Initially, the value of this key (vertex) will be an empty array.
  this.list.set(newVertex, []);
}

✨ Add Edge

We have the functionality to add vertices, now we need a function to add edges that will connect the vertices together. For this purpose, we have the addEdge method which will add a vertex to the list of connected vertices.

addEdge(vertex, edgeNode) {
  // We are adding the edge between one vertex to another.
  // For this, we will first get the vertex from our map, which is an array
  // then we will push the edgeNode into it.
  this.list.get(vertex).push(edgeNode);
}

✨ Removing Vertex

Let's take a look at how we can implement the functionality to remove a particular vertex. For this purpose, we have removeVertex method which will remove vertex and all of its references.

removeVertex(vertexName) {
    // delete the vertex
    this.list.delete(vertexName);
    // decrement the size
    this.totalVertices--;
    // remove all the references of that vertex
    const vertices = this.list.keys();
    // loop over all the vertices
    for (let vertex of vertices) {
      // get the connected node
      const connectedNodes = this.list.get(vertex);
      // if any node has connection to the deleted vertex
      if (connectedNodes.find((node) => node === vertexName)) {
        // remove the connection
        const newNodes = connectedNodes.filter((node) => node !== vertexName);
        this.list.set(vertex, newNodes);
      }
    }
  }

✨ Removing Edge

We have the functionality to remove a vertex, now let's take a look at how we can remove an edge. For this purpose, we have removeEdge method which will remove the edge and its connection.

removeEdge(vertex, edgeNode) {
  // get the connections of that vertex
  const connectedNodes = this.list.get(vertex);
  // remove the edge connection
  const updatedNodes = connectedNodes.filter((node) => node !== edgeNode);
  // update the vertex connections
  this.list.set(vertex, updatedNodes);
}

✨ Printing Graph

printGraph() {
  const vertices = this.list.keys();
  for (let vertex of vertices) {
    const connectedNodes = this.list.get(vertex);
    console.log(`${vertex} -> ${connectedNodes.join(', ')}`);
  }
}

✨ Using Graph Class

We have implemented the graph, let's test it now.

const graph = new Graph();

// Adding vertices
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');

// Adding edges
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'E');
graph.addEdge('D', 'B');
graph.addEdge('E', 'F');
graph.addEdge('E', 'D');
graph.printGraph();

/**
 * Output:
 * A -> B
 * B -> C
 * C -> E
 * D -> B
 * E -> F, D
 */

graph.removeVertex('A'); // Vertex A -> Removed
graph.printGraph();

/**
 * Output:
 * B -> C
 * C -> E
 * D -> B
 * E -> F, D
 */
graph.removeEdge('D', 'B'); // Edge from D to B is removed
graph.printGraph();

/**
 * Output:
 * A -> B
 * B -> C
 * C -> E
 * D ->
 * E -> F, D
 */

That's it, folks! hope it was a good read for you. Thank you! ✨

Rehan Sattar