So we have arrived now at our next stop in the series of “Understanding Data Structure and Algorithms with JavaScript 🚀”, which is the Graph data structure. Like the Tree data structure, the graph data structure is also a non-linear structure consisting of nodes and edges. You can imagine it as a pictorial presentation of an object having few properties interlinked with other objects.
In this blog, we will understand more about Graphs, their importance, some important terminologies, types of trees, and their advantages.
What is a Graph Data Structure?
A Graph data structure is a non-linear structure like trees, it is a collection of nodes that are interlinked with each other. It is a very important data structure that has a lot of real-life applications. Many social media giants rely on graph data structure to keep track of likes, comments, and mutual friends you have.
- Each node also known as vertices is used to store data and location to other nodes.
- The connection between two nodes also known as edges is the network between nodes.
Also read, Simple Explanation of Sorting Algorithms with JavaScript | Part 2
Why Graph Data Structure is so Important
There are many ways Graph data structure plays an important role:-
- Graphs are non-linear data structures made up of a finite number of vertices and edges connected between them.
- The tree data structure is just a restricted form of Graph. So whatever you can achieve using a tree, you can also do the same with Graph. You can say that a Tree is just a subset of a Graph data structure.
- But, Graphs are a little more complex than trees, having all or most properties like directed, undirected, cyclic or acyclic, and so on.
- A graph is used to address many real-life examples like representing a network of circuits or telephones also it is nearly impossible to create a substantial social media network of people without using a graph data structure.
Also read, We’re approaching the limits of computer power – we need new programmers now
Important Terminology related to Graph Data Structure
- Vertex:- Every individual data element is known as a vertex or node.
- Edge:- Also known as arc, it is a network connection between two or more nodes.
- Directed Edge:- It is a uni-directional edge.
- Undirected Edge:- It is a bi-directional edge.
- Weighted Edge:- An edge with value on it.
- Degree:- Total number of edges connected to the total vertices in the Graph.
- Indegree:- Total number of incoming edges from a certain vertex.
- Outdegree:- Total number of outgoing edges from a certain vertex.
- Self-loop:- An edge is known as Self-loop when two endpoints of that edge coincide with each other.
- Adjacency:- Vertices are called adjacent to one another when there is an edge connecting them.
Also read, Understanding Binary Search Trees with Js
Different types of Graph Data Structures
UnDirected Graph
A graph in which the edges are bi-direction to each other is known as an Undirected graph. The edge does not point in any certain direction which means you can easily travel to one vertex and back to the original one.
The best example would be the Facebook friends wall, if you have a Facebook account connected with another friend then you can see his posts on his profile and he can see your post as well.
Directed Graph
A graph in which the edges are uni-direction to each other is known as a Directed graph. The edge points at a certain vertex only.
The best example would be Instagram following, if you have followed any celebrity like Justin Bieber, you can see all his posts but Justin does not follow you back, so he cants see your posts.
Weighted Graph
A graph in which the edges have a value associated with it is known as a Weighted graph. The values associated with edges are called weights.
For example, If you look at google maps, and search for any address, like a baker shop, it will show some distance let’s say, X m between you and the baker shop. That X m is the value associated between two locations or vertices.
UnWeighted Graph
A graph in which the edges have no value associated with it is known as an UnWeighted graph. All graphs are unweighted by default.
Also read, Simple Explanation of Tree traversal Operations with JavaScript
Graph Representation
A graph is generally represented in two ways:-
Adjacency Matrix
An Adjacency Matrix is a method of representing a given graph in 2D array form where the total column and row is Total Vertex * Total Vertex.
If the vertex is connected with another vertex then it is represented as 1 but if it is not connected with another vertex or we point to the same vertex then it is represented as 0.
Adjacency List
An Adjacency List is a method of representing a given graph through an array of Linked lists. Each root node in the Linked list is the initial Vertex and later nodes represent vertices that are connected to the root vertex.
Also read, Easy Explanation of Linked list Data Structure in JavaScript
Advantages of using Graph Data Structures
- In the computer science branch, the Graph data structure is used to represent networks of various structures like communication, computational devices, data organization, etc.
- While creating social media, we use graphs to track data of users like friends they have, their likes, comments, etc.
- The graph is also applied in chemistry to understand and study molecule structure.
Applications of Graph Data Structures
- On Facebook, users’ data is considered as vertices and if they have friends then their edges are connected between them. Facebook’s Friends suggestion algorithm uses graph theory to show and suggest mutual friends.
- Facebook also uses a graph data structure to save and show lists of pages users are following, their comments and likes history, and friends they have in common.
- Google also uses graphs in Google’s maps for building routing systems, where the intersection of two or more roads is considered edges and locations are vertexes.
Also read, Introduction to Tree Data Structure
Final Words
I hope you like the article, please comment and share with your friends and bookmark this website, and also do check our detailed articles on Data structure, Javascript, and programming.