# 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.

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.

### Differences

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

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|)

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.

## 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(){
}
}``````

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){
}
}``````

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){
}``````

### 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){
}``````

### 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){