Basic operations in Graph Data structure

Graphs are non-linear data structures consisting of a finite set of nodes and edges. In our last blog, we studied and understood what really is a Graph data structure, its importance, and its application.

This blog will teach different operations associated with the Graph data structure, like adding vertex or edge and removing vertex or edge. 

Graphs Adjacency List vs Graphs Adjacency Matrix

Unlike a Binary tree or other data structure which has a simple way of storing and presenting them, with Graphs things become a little tricky. There are many ways we can store and represent a graph using some heavy-handed approach but there are two standard approaches that many people follow.

The main difference between the Adjacency list and Adjacency Matrix is representing if we have a large number of connections. In the Adjacency list, it is easy to store as we only have to store how many connections a particular node has whereas in Adjacency Matrix we have to store each vertex with each node connected or not.

Even though a node has one connection but still has to store all the vertices.

Also Read, Simple Explanation of Tree traversal Operations with JavaScript

Differences

Differences in BIG O

Note:- |V| – number of vertices & |E| – number of edges

Also Read, Mark Zuckerberg has been teaching his daughter to code since age three 

That is why I am going to move forward with the Adjacency list because of two main reasons,

• Small space it takes up
• And most of the data in real-world like social media networks or Wikipedia pages generally have a humongous amount of data connected with lots of vertices that may not be connected together

That is why it makes more sense to use the Adjacency list.

Also Read, Simple Explanation of Sorting Algorithms with JavaScript | Part 2

Various Operations in Graph Data structure

Before moving forward to implement various operations associated with Graph, first, we need to set a basic Undirected Graph data structure class,

class Graph{
    constructor(){
        this.adjacencyList = {}
    }
}

Adding Vertex

Adding a Vertex is a very simple process, here are a few steps you need to follow in order to add a vertex,

• Create a method and name it as addVertex, which accepts a name of a vertex,
• It should have a key to the adjacency list with the name of the vertex and set its value to be an empty array,

addVertex(vertex){
    if(!this.adjacencyList[vertex]){
        this.adjacencyList[vertex] = [];
    }
}

Also Read, Simple Explanation of Stack and Queue with JavaScript

Adding Edge

An edge represents the connection between two vertices, here are a few steps you need to follow in order to add an edge between two vertices,

• Create a method and name it as addEdge, which accepts two vertices, let’s say vertex1 and vertex2
• This method should find in the key of vertex1 in the adjacency list and push vertex2 to the array
• And, This method should find in the key of vertex2 in the adjacency list and push vertex1 to the array
• To play safe you can also add error handling to make sure that the given key is valid

addEdge(v1,v2){
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1 );
}

Remove Edge

Removing an edge is one of the fundamental operations in graphs, here are a few steps you need to follow in order to remove an edge between two vertices,

• Create a method and name it as removeEdge, which accepts two vertices, let’s say vertex1 and vertex2.
• This method should be able to reassign the key of vertex1 to an array that includes all the elements except vertex2.
• This method should be able to reassign the key of vertex2 to an array that includes all the elements except vertex1.
• To play safe you can also add error handling to make sure that the given vertices are valid

removeEdge(v1,v2){
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(vertex => vertex != v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(vertex => vertex != v1);
}

Also Read, Simple Explanation on Searching Algorithms with JavaScript

Remove Vertex

Removing a Vertex is a very simple process, here are a few steps you need to follow in order to remove a vertex,

• Create a method and name it as removeVertex, which accepts a vertex,
• The function should keep looping until there are vertices that contain a given vertex that needs to be removed from their adjacency list.
• We also need to remove all the edges, as vertex does not increase, so does the edge, so in order to remove edges we need to call removeEdge function and pass the vertex.
• Finally, delete the key in the adjacency list for that vertex,
• To play safe you can also add error handling to make sure that the given vertex is valid

removeVertex(vertex){
    while(this.adjacencyList[vertex].length){
        let adjacentVertex = this.adjacencyList[vertex].pop()
        this.removeEdge(vertex, adjacentVertex)
    }

    delete this.adjacencyList[vertex]
}

Also Read, Introduction to Graph Data Structure

Final Words

Having strong knowledge of Graph data structure not only help you in cracking interview but also in understanding programming concepts better.

I hope this article gave you a fair understanding of each operation, please share your thoughts in the comment section and share it more with your friends and colleagues if you like it also check out more articles on JavaScript, coding, or even technology.