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.