Saturday, August 13, 2022
HomeData Structures and AlgorithmIntroduction to Graph Data Structure

Introduction to Graph Data Structure

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.

graph data structure

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.

undirected graph

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.

directed graph

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.

Weighted graph

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.

Adjacency Matrix graph

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.

Adjacency List graph

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.

graph example
Credit – TouchGraph

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.

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