Saturday, August 13, 2022
HomeData Structures and AlgorithmBasic operations in Graph Data structure

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

Adjacency List Adjacency Matrix
Can take up less space (in sparse graphs) Can take up more space (in sparse graphs)
Faster to iterate over all edges Slower to iterate over all edges
Can be slower to lookup specific edge Faster to lookup specific edge

Differences in BIG O

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

Operation Adjacency List Adjacency Matrix
Add Vertex O(1) O(|V^2|)
Add Edge O(1) O(1)
Remove Vertex O(|V| + |E|) O(|V^2|)
Remove Edge O(|E|) O(1)
Query O(|V| + |E|) O(1)
Storage O(|V| + |E|) O(|V^2|)

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.

Aaquib Ahmedhttps://aaquib.netlify.app
Hi, I'm Aaquib Ahmed, a passionate self-taught frontEnd web developer based in Bangalore, India. I tend to make use of modern web technologies to build websites that look great, feels fantastic, and functions correctly. I am especially focusing on Reactjs.
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments