Graphs in Data Structure: Types, Storing & Traversal

# Graphs in Data Structure: Types, Storing & Traversal

Last updated:
1st Jul, 2024
Views
12 Mins
View All

In my experience with Data Science, I’ve found that choosing the right data structure is crucial for organizing information effectively. Graphs are particularly important in this field because they allow us to represent data in a non-linear way, using nodes (or vertices) and edges (or paths).

Interestingly, many of us interact with graphs in the data structure every day without realizing it. They help us navigate our commutes, suggest nearby eateries or entertainment options, and even optimize travel routes.

Graph terminology in data structure encompasses nodes (vertices), representing entities, and edges, denoting relationships between nodes. It includes concepts like directed edges (arcs) for one-way connections and weighted edges for representing costs or distances. Understanding these terms is essential for manipulating and analyzing graph data effectively.

A graph is a data structure comprising nodes (vertices) connected by edges. It’s used to represent relationships or connections between objects, facilitating modeling and analysis in various fields such as networks, logistics, and social relationships.

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

G={01,12,23,34,45,05,03}

Now let’s study the types of graphs.

## Elements of Graph

As I have been on the road to explore the world of graphs in data structures, I have understood that they form the backbone of modern computing. Composed of nodes and edges they beautifully reflect the relations among a number of entities. Nodes act as entities, while edges indicate relationships or interactions among them. This basic structure eases up the representation of complex data, making it more manageable and understandable.

A graph is a fundamental data structure used to represent relationships between objects. It consists of nodes, also known as vertices, which are connected by edges. Each edge may or may not have a direction and can optionally carry additional information such as weights or costs, making it a weighted graph.

Graphs are versatile and used in various applications such as social networks, computer networks, and logistics. Depending on their characteristics, graphs can be categorized into several types.

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

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

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

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

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

 Top Data Science Skills to Learn 1 Data Analysis Course Inferential Statistics Courses 2 Hypothesis Testing Programs Logistic Regression Courses 3 Linear Regression Courses Linear Algebra for Analysis

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 Representation

I found that graphs in ds can come in different presentations of adjacency matrices, adjacency lists, and edge lists. There is uniqueness in each of the representations as they offer benefits and drawbacks in terms of performance, memory usage and manipulation. Understanding the form of these representations enables us developers to freely select the best one fitting our needs the most.

## Graph Traversal in Data Structure

Graph traversal is a method used to search nodes in a graph. The traversal of graph in data structure 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

 Data Science Career Path: A Comprehensive Career Guide Data Science Career Growth: The Future of Work is here Why is Data Science Important? 8 Ways Data Science Brings Value to the Business Relevance of Data Science for Managers The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have Top 6 Reasons Why You Should Become a Data Scientist A Day in the Life of Data Scientist: What do they do? Myth Busted: Data Science doesn’t need Coding Business Intelligence vs Data Science: What are the differences?

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

## Basic Operations of Graphs

In my investigation, I have come to realize that graphs in dsa provide basic functionalities such as adding or deleting nodes and edges, traveling through the graph to visit all nodes or find specific paths, and identifying the patterns or motifs within the graph. These operations form the basis on which more advanced graph algorithms and applications are built increasing my confidence in handling intricate problems swiftly.

## Usage of Graphs

I’ve seen in many domains that graph type in DSA is adaptable in applications like social networks, transportation systems, recommendation engines, and bioinformatics. The ability to model relations between entities renders them invaluable for studying complex systems and tackling practical issues.

## Practical Applications of Graphs

In my experiences, I’ve seen graphs in data structure power numerous practical applications, from social media platforms utilizing friend networks to recommend connections, to logistics companies optimizing delivery routes for maximum efficiency. They play vital roles in bioinformatics, financial fraud detection, and e-commerce recommendation systems, among others. Additionally, graph databases facilitate querying and analyzing complex relationships in interconnected datasets, enabling insights that traditional databases struggle to provide.

## When to Use Graphs

From my experiences, I realized that graphs in data structures are used in various practical applications; for instance, social media platforms make use of friend networks to recommend connections and logistics companies use graphs to optimize delivery routes. They are significant in bioinformatics, financial fraud detection, e-commerce recommendation systems and others. Graph databases also allow for querying and analyzing the complex relationships in interconnected datasets thus leveraging insights traditional databases cannot provide.

## Pros & Cons of Graphs

### Pros of Graphs in Data Structures:

• Modeling Complex Relations: Graphs in data structure are viewed as a natural representation of the real world and a simple graphical way to display relationships between entities.
• Efficient Shortest Path Traversal: Shortest paths between nodes are defined and efficient in graphs for which well-known algorithms exist.
• Visual Representation: Graphs in data structure are more favorable over charts for people wishing to understand relationships, as well as structures.
• Analyzing Continuous Data: Graphs in data structure are commonly used for continuous data analysis, hence, offering a wider functional variety.

### Cons of Graphs in Data Structures:

• Computational Complexity: Inputting and changing large-scale graphs in data structures are computational and memory-intensive.
• Long Processing Times: For some operations, principal actors, especially in complex graphs, are expected to consume a large amount of time to complete the task.
• Data Consistency Challenges: Ensuring data consistency and concurrency on the distributed graph databases (high concurrency) is a hard task to accomplish.

## Conclusion

In this article, I’ve explained what Graphs are and why they matter in Data Structure. We’ve looked at different types of Graphs in data structure and how they work, plus how we store them and find information in them. I’ve also shared some real-life examples of where we use graph data, such as in social networks, road maps, and computer networks – all essential “Graphs in data structure examples”.

Understanding Graphs in Data Structure is important for learning about Graph databases, search algorithms, programming, and more. To get good at it, it’s helpful to learn from experts in the field.

### Why Choose a Course with upGrad?

I strongly 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, www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

“Math Insight.” Directed Graph Definition – Math Insight, mathinsight.org/definition/directed_graph.

Singh, Amritpal. “Graph Data Structure.” Medium, Medium, 29 Mar. 2020, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

Solo. “The Real-Life Applications of Graph Data Structures You Must Know.” Graph Data and GraphQL API Development-Leap Graph, leapgraph.com/graph-data-structures-applications.

#### Rohit Sharma

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

Select
Select Area of interest
Select Work Experience
By clicking 'Submit' you Agree to

#### Data Science Skills to Master

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?

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.

4What is a data graph?

A data graph is a visual representation of data points (nodes) connected by relationships (edges), allowing for the analysis and visualization of complex relationships and patterns within datasets.

## Suggested Blogs

101429
Why data mining techniques are important like never before? Businesses these days are collecting data at a very striking rate. The sources of this eno

07 Jul 2024

142163
Association Rule Mining in data mining, as the name suggests, involves discovering relationships between seemingly independent relational databases or

07 Jul 2024

16859
Introduction to Data Mining In its raw form, data requires efficient processing to transform into valuable information. Predicting outcomes hinges on

04 Jul 2024

82564
What is a Data Analytics Lifecycle? Data is crucial in today’s digital world. As it gets created, consumed, tested, processed, and reused, data goes

04 Jul 2024

9935
Introduction Data structures are one of the most fundamental concepts in object-oriented programming. To explain it simply, a data structure is a par

03 Jul 2024

70120
Summary: In this article, you will learn, Difference between Data Science and Data Analytics Job roles Skills Career perspectives Which one is right

02 Jul 2024

14756
The banking sector has many applications for programming and IT solutions. If you’re interested in working on a project for the banking sector,

25 Jun 2024

66246
In my journey through data structures, I’ve navigated the nuances of linear search vs binary search in data structure, especially when dealing w