Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconData Sciencebreadcumb forward arrow iconGraphs in Data Structure: Types, Storing & Traversal

Graphs in Data Structure: Types, Storing & Traversal

Last updated:
6th Oct, 2020
Read Time
9 Mins
share image icon
In this article
Chevron in toc
View All
Graphs in Data Structure: Types, Storing & Traversal

A data structure is an efficient way of organising data in data science so that that data can be accessed easily and used effectively. There are many types of databases, but why graphs play a vital role in data management is discussed in this article. 

Spoiler alert: you use Graphs in data structure every day to fetch the best route to your office, to get suggestions for your lunch, movie and to optimise your next flight route. Sounds interesting! Let us see about the graph’s properties and its application.  

First, let’s see what a Graph is?  It is a representation of data in a non-linear structure consisting of nodes (or vertices) and edges (or paths).

A Graph in the data structure can be termed as a data structure consisting of data that is stored among many groups of edges(paths) and vertices (nodes), which are interconnected. Graph data structure (N, E) is structured with a collection of Nodes and Edges. Both nodes and vertices need to be finite.

In the above graph representation, Set of Nodes are N={0,1,2,3,4,5,6}and set of edges are


Now let’s study the types of graphs.

Read: Top 10 Data Visualization Techniques

Types of Graphs

1. Weighted Graph

Graphs whose edges or paths have values. All the values seen associated with the edges are called weights. Edges value can represent weight/cost/length.

Values or weights may also represent:  

  • Distance covered between two points- Ex: To look for that shortest path to the office, the distance between two workstations in an office network.
  •  Speed of the data packet in a network or bandwidth.

Our learners also read: Free Data structures and Algorithms course!

2. Unweighted Graph

Where there is no value or weight associated with the edge. By default, all the graphs are unweighted unless there is a value associated. 

upGrad’s Exclusive Data Science Webinar for you –

How upGrad helps for your Data Science Career?

3. Undirected Graph

Where a set of objects are connected, and all the edges are bidirectional. The below image showcases the undirected graph, 

It’s like the associativity of two Facebook users after connecting as a friend. Both users can refer and share photos, comment among each other.

Must read: Free excel courses!

4. Directed Graph

Also called a digraph, where a set of objects (N, E) are connected, and all the edges are directed from one node to another. The above image showcases the directed graph.

Checkout: Data Visualization Projects You Can Replicate

Storing of Graph 

Every storage method has its pros and cons, and the right storage method is chosen based on the complexity. The two most commonly used data structures to store graphs are: 

1. Adjacency list

Here nodes are stored as an index of the one-dimension array followed by edges being stored as a list.

Top Data Science Skills to Learn

2. Adjacency matrix

Here nodes are represented as the index of a two-dimensional array, followed by edges represented as non-zero values of an adjacent matrix.

Both rows and columns showcase Nodes; the entire matrix is filled with either “0” or “1”, representing true or false. Zero represents that there is no path, and 1 represents a path.   

Our learners also read: Free Online Python Course for Beginners  

Graph Traversal 

Graph traversal is a method used to search nodes in a graph. The graph traversal is used to decide the order used for node arrangement. It also searches for edges without making a loop, which means all the nodes and edges can be searched without creating a loop. 

There are two graph traversal structures.

1. DFS (Depth First Search): In-depth search method  

The DFS search begins starting from the first node and goes deeper and deeper, exploring down until the targeted node is found. If the targeted key is not found, the search path is changed to the path that was stopped exploring during the initial search, and the same procedure is repeated for that branch.

The spanning tree is produced from the result of this search. This tree method is without the loops. The total number of nodes in the stack data structure is used to implement DFS traversal.

Steps followed to implement DFS search: 

Step 1 – Stack size needs to be defined depending on the total number of nodes.

Step 2 – Select the initial node for transversal; it needs to be pushed to the stack by visiting that node.   

Step 3 – Now, visit the adjacent node that is not visited before and push that to the stack.  

Step 4 – Repeat Step 3 until there is no adjacent node that is not visited.  

Step 5 – Use backtracking and one node when there are no other nodes to be visited.

Step 6 – Empty the stack by repeating steps 3,4, and 5.  

Step 7 – When the stack is empty, a final spanning tree is formed by eliminating unused edges.

Applications of DFS are:

  • Solving puzzles with only one solution.
  • To test if a graph is bipartite.
  • Topological Sorting for scheduling the job and many others.

Read our popular Data Science Articles

2. BFS (Breadth-First Search): Search is implemented using a queuing method

Breadth-First Search navigates a graph in a breadth motion and utilises based on the Queue to jump from one node to another, after encountering an end in the path. 

Steps followed to implement BFS search,

Step 1 – Based on the number of nodes, the Queue is defined.

Step 2 – Start from any node of the traversal. Visit that node and add it to the Queue.

Step 3 – Now check the non-visited adjacent node, which is in front of the Queue, and add that into the Queue, not to the start.

Step 4 – Now start deleting the node that doesn’t have any edges that need to be visited and is not in the Queue.

Step 5 – Empty the Queue by repeating steps 4 and 5.

Step 6 – Remove the unused edges and form the spanning tree only after the Queue is empty.

Applications of BFS are:

  • Peer to Peer Networks- Like in Bittorrent, it is used to find all adjacent nodes.
  • Crawlers in Search Engine.
  • Social Networking Websites and many more.

Real-world Applications of Graph in the Data Structure

Graphs are used in many day-to-day applications like network representation (roads, optical fibre mapping, designing circuit board, etc.). Ex: In the Facebook data network, nodes represent the user, his/her photo or comment, and edges represent photos, comments on the photo.   

The Graph in data structure has extensive applications. Some of the notable ones  are:

  •  Social Graph APIs– It is the primary way the data is communicated in and out of the Facebook social media platform. It is an HTTP-based API, which is used to programmatically query data, upload photos and videos, make new stories, and many other tasks. It is composed of nodes, edges, and fields; to query, the specific object nodes are used. Edges for a group of objects subjected to a single object and fields are used to fetch data about each object among the group.
  • Yelp’s GraphQL API– It’s a recommendation engine used to fetch the specific data from the Yelp platform. Here, orders are used to find the edges, after which the specific node is queried to fetch the exact result. This speeds up the retrieval process.   

On the Yelp platform, the nodes represent the business, containing id, name, is_closed, and many other graph properties.

  • Path Optimization Algorithms- They are employed to find the best connection which fits the criteria of speed, safety, fuel, etc. BFS is used in this algorithm. The best example is Google Maps Platform (Maps, Routes APIs).
  • Flight Networks- In flight networks, this is used to find the optimised path that fits the graph data structure. This also aids in the model and optimises airport procedures efficiently.

Also Read: Benefits of Data Visualization


In this article, we first discussed the definition of Graph and Graph in data structure and then learned about the types of graphs with their properties. Later, we learned about commonly used methods for storage of graphs followed by important topic search methods used in Graphs, Graph Traversal. Finally, we discussed the real-world applications of graph data structure.

This article provided insight on Graphs in the data structure; knowledge of this is vital for fundamental understanding in Graph databases, search algorithm implementation, programming, and many more. It must be learned from the industry expert. 

Why Choose a Course with upGrad

We recommend you to choose Executive PG Programme in Data Science offered by IIIT Bangalore hosted on upGrad because here you can get your queries 1-1 with the course instructors. It does not only focus on theoretical learning but gives importance to practical based knowledge, which is essential to get learners ready for facing real-world projects and provide you with India’s 1st NASSCOM certificate, which aids you to get high paying jobs in Data Science.  

Works Cited

Department of Math/CS – Home,

“Math Insight.” Directed Graph Definition – Math Insight,

Singh, Amritpal. “Graph Data Structure.” Medium, Medium, 29 Mar. 2020,

Solo. “The Real-Life Applications of Graph Data Structures You Must Know.” Graph Data and GraphQL API Development-Leap Graph,


Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.

Frequently Asked Questions (FAQs)

1Why are graphs needed in Data Structures?

Many real-world problems are solved using graphs. Networks are represented using graphs. Paths in a city, telephone network, or circuit network are examples of networks. Graphs are also utilized in social networking sites such as LinkedIn and Facebook. Graphs are a strong and adaptable data structure that allows you to easily express real-world connections between many types of data (nodes). A graph is made up of two major components (vertices and edges). The data is stored at the vertices (nodes), which are represented by the numbers in the picture on the left. The edges (connections) that link the nodes in the picture, i.e., the lines connecting the numbers.

2How many types of Data structures are present to store graphs?

A graph can be represented by one of three data structures: an adjacency matrix, an adjacency list, or an adjacency set. An adjacency matrix is similar to a table with rows and columns. The nodes of a graph are represented by the row and column labels. Every vertex in a graph's adjacency list is represented as a node object. The adjacency set alleviates some of the issues raised by the adjacency list. The adjacency set is considerably similar to an adjacency list, but instead of a linked list, it provides a collection of neighboring vertices.

3What is Traversal?

Traversal is a procedure that visits all nodes in a tree and prints their values. Because all nodes are linked together by edges (links), we always begin at the root (head) node. That is, we cannot visit a node in a tree at random. In-order Traversal, Pre-order Traversal, and Post-order Traversal are three methods for traversing a tree.

Explore Free Courses

Suggested Blogs

Python Free Online Course with Certification [2023]
Summary: In this Article, you will learn about python free online course with certification. Programming with Python: Introduction for Beginners Lea
Read More

by Rohit Sharma

20 Sep 2023

Information Retrieval System Explained: Types, Comparison & Components
An information retrieval (IR) system is a set of algorithms that facilitate the relevance of displayed documents to searched queries. In simple words,
Read More

by Rohit Sharma

19 Sep 2023

26 Must Read Shell Scripting Interview Questions & Answers [For Freshers & Experienced]
For those of you who use any of the major operating systems regularly, you will be interacting with one of the two most critical components of an oper
Read More

by Rohit Sharma

17 Sep 2023

4 Types of Data: Nominal, Ordinal, Discrete, Continuous
Summary: In this Article, you will learn about 4 Types of Data Qualitative Data Type Nominal Ordinal Quantitative Data Type Discrete Continuous R
Read More

by Rohit Sharma

14 Sep 2023

Data Science Course Eligibility Criteria: Syllabus, Skills & Subjects
Summary: In this article, you will learn in detail about Course Eligibility Demand Who is Eligible? Curriculum Subjects & Skills The Science Beh
Read More

by Rohit Sharma

14 Sep 2023

Data Scientist Salary in India in 2023 [For Freshers & Experienced]
Summary: In this article, you will learn about Data Scientist salaries in India based on Location, Skills, Experience, country and more. Read the com
Read More

by Rohit Sharma

12 Sep 2023

16 Data Mining Projects Ideas & Topics For Beginners [2023]
Introduction A career in Data Science necessitates hands-on experience, and what better way to obtain it than by working on real-world data mining pr
Read More

by Rohit Sharma

12 Sep 2023

Actuary Salary in India in 2023 – Skill and Experience Required
Do you have a passion for numbers? Are you interested in a career in mathematics and statistics? If your answer was yes to these questions, then becom
Read More

by Rohan Vats

12 Sep 2023

Most Frequently Asked NumPy Interview Questions and Answers [For Freshers]
If you are looking to have a glorious career in the technological sphere, you already know that a qualification in NumPy is one of the most sought-aft
Read More

by Rohit Sharma

12 Sep 2023

Want to build a career in Data Science?Download Career Growth report
footer sticky close icon