Data Structures 101: Implementing Graphs Using Adjacency List
A guide for you to implement Graph 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! ✨