Graph Data Structure
Hello Everyone,
Today I will be talking about Graph data structures. Graphs are used in pretty much every social networking when we’re modeling users as well as recommendation engines. For example, when Youtube or Netflix recommends movies to you, Graphs are usually behind the scenes. So What is a Graph? A graph is simply a collection of nodes with edges between them. Graphs can be either directed or undirected. Directed edges are like a one-way street, undirected edges are like a two-way street.
Graphs are awesome data structures, they are used all over the place. Some real-world applications are Google Maps, Google Search, Facebook, Twitter, and many more.
Types of Graphs
Graph Terms:
Vertex → Node
Edge → Connection between nodes
Weighted Graph → If Edges in the Graphs have values then it’s weighed graph
Unweighted Graph → If Edges in the Graphs don’t have values then it’s weighed graph
Undirected Graph → A graph with undirected edges (Like a 2-way street).
You can think of this Undirected Graph example as Facebook modeling friends. When your friend sends your request if you accept the request then you and your friend can see each other’s stuff. It’s a 2-way relationship.
Example of Undirected Graphs used in Mapping
This is an example of how Google gives you directions,
Directed Graph → A graph with only directed edges (Like a 1-way street).
Above an example of a Directed Graph, you can think of this as an Instagram follow request. If you accept the request they see your stuff, however, you must also request them if you would like to see their profile.
Storing Graphs
Adjacency Matrices
An adjacency matrix is a square (NxN) boolean matrix (where N is the number of nodes). In this, we are storing information in rows and columns. We can represent the relationship between the nodes using a matrix.
Above on the right, Matrix representing the relationships for the left Graph. If you wanted to see the relationship between Node A and F, you can simply look at column F and row A. You should see Y, which means Yes. This works both ways you can first go to row F and then column A, you will get the same results.
Every time you add a new node, you will have to add an entirely new row and new column.
Adjacency List
This is the most common way to represent a graph. We can use a hash table to store a key-value pair data structure.
Using a hash table we can see A is connected with (A, B, and A, F). We can do the same for node B (B, A, and B, C).
Implementing Graph Using Adjacency List
class Graph{
constructor(){
this.adjacencyList = {};
}
addVertex(vertex){
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
} addEdge(vertex1,vertex2){
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
removeEdge(vertex1,vertex2){
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex){
while(this.adjacencyList[vertex].length){
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex]
}
}
In comparison, Adjacency List takes less space and is first when iterating, however, it can be slower when looking up specific edges. Adjacency Matrix is completely opposite, it takes more space and is slower when iterating over edges, however, its faster when looking up specific edges.
There you have it. I hope you found this blog helpful. If you’re having any difficulty or need more explanation, I’m more than happy to help you. Please connect with me on LinkedIn or my email is singhamritpal49@gmail.com. Also, check out my last blog on Deploying your React App To Heroku.
Happy Coding :)
