Graphs in Data Structure: Types, Storing & Traversal

Did you know that facts presented in words and numbers attain 68% attention from viewers? However, a graph claim can raise attention span by 97%. This is where graphs in data structure become important, as they provide a visually stunning way to represent complex relationships and data interaction

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.

Professionals often use different types of graphs, such as weighted, directed, and more, to address practical problems, representing the problem area as a particular network. Understanding these terms is essential for manipulating and analyzing graph data effectively.

In this blog, we will explore the role of graphs in data structures, along with their types, storage, and traversal. 

Want to comprehensively learn graphs in data structure? upGrad’s Data Analysis Courses can equip you with tools and strategies to stay ahead. Enroll today!

Elements of Graph 

 Graphs in data structures are critical for modeling relationships and connections between entities. As fundamental components of modern computing, they represent data through nodes (vertices) and edges, allowing you to express complex relationships in a structured manner. Graphs in data structures can be categorized based on their characteristics. These categories help optimize their representation, storage, and traversal methods to suit specific applications

If you want to learn skills to help you understand the importance of graphs in data structures, the following courses can help you succeed.

• Master’s Degree in Artificial Intelligence and Data Science
• Executive Diploma in Data Science & AI with IIIT-B
• Executive Post Graduate Certificate Programme in Data Science & AI

Here are the key elements of a graph:

• Nodes (Vertices): Entities in the graph, representing objects such as users, locations, or products.
• Edges: Connections between nodes that define the relationship between them. These can be directed (arcs) or undirected, indicating one-way or two-way relationships.
• Edge Weights: Optional values assigned to edges, representing costs, distances, or other metrics.
• Directed vs. Undirected: Directed graphs (digraphs) have edges that point from one node to another, whereas undirected graphs allow two-way relationships.
• Graph Type: Depending on structure, graphs can be cyclic or acyclic, connected or disconnected, and can even have loops.
• Graph Representation: Common methods for storing graphs include adjacency matrices, adjacency lists, and edge lists, each offering benefits based on the graph's size and sparsity.

Visualization of Graphs

Graphs can be analyzed visually through tools such as scatter plots, box plots, and histograms to uncover patterns and relationships within the data:

• Scatter Plot: Scatter plots visualize relationships between two continuous variables, helping identify correlations or clusters in data represented as nodes and edges.
• Box Plot: A box plot helps visualize the spread of data and identify outliers, providing insights into node relationships or distributions.
• Histograms: Histograms represent the frequency distribution of node attributes (e.g., the number of edges connected to a node), giving insights into data centrality and skewness.

If you want to learn how you can use AI for data analysis and visualization, check out upGrad’s Generative AI Mastery Certificate for Data Analysis. The program will help you gain expertise on industry-relevant tools like Power BI and more to automate your analytics. 

Now, let’s look at some of the major types of graphs in data structures. 

Types of Graphs

Graphs, in their various types, are used to model real-world relationships, where nodes represent entities, and edges represent the connections between them. In modern computing, understanding the different types of graphs is crucial for selecting the most efficient approach to data manipulation and analysis. 

The choice of graph type, weighted or unweighted, directed or undirected, depends mainly on the problem you're solving and the computational constraints. Graphs are implemented using data structures in different programming languages like Python, Java, C#, and C++.

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:  

• Weights Represent Costs: In network routing, weights may represent latency, bandwidth, or time delay between two nodes.
• Edge Weight Calculation: Often, the weight is a numeric value, representing distance (e.g., miles between cities), cost (e.g., transportation expenses), or time.
• Algorithm Application: Algorithms like Dijkstra's shortest path or Prim's algorithm are designed to work with weighted graphs to find the least-cost path or minimum spanning tree.

Use Case:

In a real-world scenario like GPS navigation (e.g., Google Maps), weighted graphs are used to find the shortest driving route between two locations. The weights in this case represent the distance or time taken to travel between different points. In Java or Python, libraries like NetworkX or Java's JGraphT can be used to model and process weighted graphs for such applications.

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

2. Unweighted Graph

An unweighted graph does not assign any weights to its edges. Each edge is considered equal in terms of distance or cost. These graphs are typically used for modeling simple relationships without the need for differentiation between connections.

• No Edge Value: All edges are treated equally, with no cost.
• Basic Connectivity: Used in cases where the relationship between nodes is symmetric and doesn't require a measure of intensity or weight.
• Simpler Algorithms: Algorithms like BFS (Breadth-First Search) or DFS (Depth-First Search) are particularly useful for unweighted graphs as they focus on structure and connectivity.

Use Case:

In social networks (e.g., Facebook), an unweighted graph could represent users as nodes, with edges connecting friends. Each edge would have the same significance, showing only whether a user is connected to another, without considering the strength of the relationship. In Python, libraries like NetworkX allow easy construction and manipulation of unweighted graphs for such applications.

upGrad’s Exclusive Data Science Webinar for you –

How upGrad helps for your Data Science Career?

3. Undirected Graph

In an undirected graph, edges do not have a direction. The relationship between two nodes is bidirectional, meaning that if there's a connection from node A to node B, you can traverse from B to A. These graphs often represent mutual relationships, such as friendships in social networks

• Bidirectional Connections: The relationship between nodes is reciprocal, meaning traversal in either direction is allowed.
• Symmetric Edges: There’s no specific direction for edges; they are treated equally in both directions.
• Used in Simple Network Models: Ideal for representing symmetric relationships where direction doesn’t matter, like undirected social networks or undirected communication networks.

Use Case:

Consider a simple undirected graph for a friendship network on a platform like LinkedIn. Each node represents a user, and an edge between two nodes indicates a mutual connection (friendship). The graph representation is symmetric; if user A is connected to user B, then user B is also connected to user A. In Java, one could use the JGraphT library to model and traverse such undirected graphs for tasks like network analysis.

Must read: Free excel courses!

4. Directed Graph

A directed graph (also known as a digraph) is a graph with edges that have a direction. Each edge has a starting node and an ending node, meaning the connection from one node to another is one-way. Directed graphs are useful for modeling asymmetric relationships such as flows, dependencies, or causality, where the direction of the relationship matters.

• Directed Edges: Each edge has a direction, pointing from one node to another, denoted as an ordered pair (A -> B).
• Applications in Data Flow: Commonly used in applications where the direction of the connection is essential, like modeling web page link structures or dependency graphs in software systems.
• Used for Graph Traversal Algorithms: Algorithms like Topological Sorting, used in scheduling tasks or determining the order of operations in a directed acyclic graph (DAG), are applied to directed graphs.

Use Case:
In web crawling (e.g., Google Search Engine), a directed graph can represent web pages as nodes, with directed edges indicating hyperlinks between pages. The direction of the edge signifies the flow from one page to another when a user clicks a link. In Python, frameworks like Scrapy or libraries like NetworkX can create and analyze directed graphs in such use cases.

Checkout: Data Visualization Projects You Can Replicate

Let’s explore the sorting of graphs in data structures for effective data analysis. 

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

The adjacency list is one of the most common ways to represent graphs, especially when the graph is sparse (i.e., not all nodes are connected). Each node is stored as an index in a one-dimensional array, and its edges are stored as a list of adjacent nodes. 

This method is memory-efficient, as it only stores the edges that exist. It is often used in web applications, social networks, and other systems where connections are dynamic and frequently updated, like ReactJS applications.

• Efficient Space Usage: Adjacency lists only store the edges that exist, leading to lower memory usage compared to other representations like adjacency matrices.
• Array-Based Indexing: The adjacency list uses an array of lists, where the index represents the node, and each list contains its adjacent nodes.
• Dynamic Graph Representation: Suitable for graphs with many nodes but relatively fewer edges, which is common in applications like social networks and web scraping.

Use Case:
An adjacency list can represent the friendships between users in a React application that manages connections between users. Each user’s ID (node) can be mapped to an array of other user IDs (edges) they are connected to.

This setup is ideal for managing dynamic connections where users may frequently add or remove friends. In React, you could manage the graph using JavaScript objects or arrays, updating the adjacency list as users connect and disconnect.

Top Data Science Skills to Learn to upskill

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.   

The adjacency matrix is a two-dimensional array that represents a graph, where rows and columns correspond to nodes. Each entry in the matrix indicates whether there is an edge between two nodes. A value of "1" denotes the presence of an edge, while "0" indicates no connection. 

This representation benefits dense graphs (where most nodes are connected). It is easy to implement in environments that leverage parallel processing, such as with Docker containers or Kubernetes for scaling. Adjacency matrices are also used in graph neural networks (GNNs) to represent graph structures in machine learning applications like TensorFlow. 

• Memory Usage: The adjacency matrix requires O(n^2) space, where n is the number of nodes, making it less space-efficient for sparse graphs but ideal for dense graphs with many edges.
• Ease of Access: It allows constant-time access (O(1)) to check whether an edge exists between any two nodes, making it highly efficient for some algorithms like matrix multiplication in graph-related computations.
• Implementation Simplicity: The matrix structure is straightforward in programming languages like Python, C++, or JavaScript.

Use Case:
In a machine learning model built with TensorFlow, the adjacency matrix can represent the connectivity between nodes in a graph, especially when implementing GNNs. With Kubernetes or Docker, you could scale the matrix operations in a distributed environment, processing graph data across multiple containers for faster computations. This approach is common in applications like social network analysis, where nodes represent users and edges represent interactions or relationships between them.

If you want to enhance your knowledge of JavaScript to understand data structures better, check out upGrad’s JavaScript Basics from Scratch. The 19-hour program will help you understand coding and the environment for data structures and analysis. 

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. 

Let’s understand what graph traversal is in data structures. 

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: The stack size must accommodate all the nodes in the graph to ensure that no node is left unvisited during traversal. For an efficient depth-first search (DFS) implementation, a dynamic stack is used to manage nodes as they are visited.
• Step 2: The traversal begins from a specified starting node pushed onto the stack. This node is marked as visited, ensuring it is not revisited later in the search process.
• Step 3: From the current node, explore its adjacent nodes that have not been visited. Each unvisited node is pushed onto the stack, marking it for future exploration. This step continues until all reachable adjacent nodes are added to the stack.
• Step 4: Visiting and pushing unvisited adjacent nodes continues recursively, ensuring that all potential paths from the current node are explored. The stack grows as new nodes are discovered, keeping track of the remaining nodes to visit.
• Step 5: If no unvisited adjacent nodes are found, the algorithm backtracks by popping the stack. This ensures that the traversal proceeds through alternative paths that may have been skipped during earlier steps.
• Step 6: Continue with the traversal and backtracking process, emptying the stack by visiting and popping nodes until no more nodes are left. This iterative process ensures that every node and edge is visited.
• Step 7: Once the stack is empty, the algorithm terminates, and a spanning tree is formed by retaining only the edges that connect the visited nodes. This tree contains no cycles and represents the most efficient path from the starting node through the graph, reducing computational overhead in subsequent analysis.

Applications of DFS:

1. Solving Puzzles with Only One Solution:
DFS is often used in solving problems like mazes, Sudoku, and other puzzles where only one valid solution exists. By exploring all possible paths recursively, DFS ensures that all potential solutions are tested until the correct one is found. 

For example, when solving a Sudoku puzzle using DFS in Python, you can implement backtracking techniques to explore possible number placements recursively. 
2. To Test if a Graph is Bipartite:
A graph is bipartite if its vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. DFS can be applied to check bipartiteness by attempting to color the graph with two colors. 

As you traverse using DFS, you alternate the color of adjacent nodes. However, if you find two adjacent nodes of the same color, the graph is not bipartite. This approach can be implemented in AWS Lambda to scale efficiently for large graphs in cloud-based environments.

3. Topological Sorting for Scheduling Jobs:
DFS is a crucial algorithm in topological sorting, used to order tasks or jobs based on their dependencies. For example, in job scheduling systems like Azure Databricks, tasks must be executed in a specific order based on their dependencies. 

The nodes are processed so that all prerequisites (edges) are handled before a task is executed. This makes DFS an essential part of dependency management in cloud computing architectures.

Also read: Top 14 Data Analytics Trends Shaping 2025

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: The first step in BFS is to define the queue size according to the number of nodes in the graph. This queue will hold the nodes as they are explored.
• Step 2: Select the initial node to begin the traversal, adding it to the queue. This node will serve as the starting point for the BFS algorithm.
• Step 3: As the BFS traversal proceeds, it checks adjacent nodes that haven’t been visited yet. These unvisited adjacent nodes are added to the queue for further exploration. In cloud environments like AWS or Azure, this process can be distributed to handle graph-based data for applications like recommendation systems or network traffic analysis.
• Step 4: Nodes with no further adjacent nodes to visit and are not in the queue are removed. This ensures that we only explore nodes contributing to the graph’s search process, keeping the traversal efficient.
• Step 5: The queue is processed by repeating steps 4 and 5 until no more nodes are left to explore.
• Step 6: After the queue is empty, the traversal concludes, and the graph's spanning tree is formed by removing unused edges. 

Applications of BFS are:

• Peer-to-Peer Networks (e.g., BitTorrent): BFS is utilized in peer-to-peer (P2P) networks like BitTorrent to find all adjacent nodes (peers) and distribute files efficiently. By traversing the network in a level-order manner, BFS ensures that all peers are connected and data can be transferred across the network most efficiently.
• Crawlers in Search Engines: In web crawlers, BFS helps explore web pages level by level, starting from the root. This ensures that all links within the website are visited systematically, which is crucial for indexing websites and ensuring that search engines capture relevant pages.
• Social Networking Websites: BFS can be used for friend suggestions in social networks. By starting from a user (node), BFS explores their direct friends (level 1), then friends of friends (level 2). This is often the basis for friend recommendations in platforms like Facebook or LinkedIn.

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

Let’s explore the basic operations of graphs in detail. 

Basic Operations of Graphs 

Graphs in data structures and algorithms (DSA) serve as fundamental tools for representing complex relationships between entities. These operations allow for efficient management and manipulation of nodes and edges. 

Here's a technical breakdown of some of the core functionalities:

• Adding and Deleting Nodes and Edges: Nodes can be added or removed from a graph, and edges can be introduced or eliminated, providing flexibility in dynamically changing graph structures.
• Graph Traversal: Traversing through the graph using various algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS) allows visiting all nodes and edges systematically, ensuring that no critical node is overlooked.
• Pattern Identification: Identifying motifs or subgraphs within a graph allows for the detection of recurring patterns and structures, critical for applications like clustering and graph mining.

Example Scenario:

Consider a graph in a social media platform where each node represents a user, and edges represent friendships. Using graph traversal methods, we can analyze the entire network of users to find specific communities or identify the shortest path between two users. Identifying recurring patterns in user interactions can be used to enhance personalized content delivery or optimize the friend suggestion algorithm.

Also read: Top 12 Best Practices for Creating Stunning Dashboards with Data Visualization Techniques

Let’s explore some of the common uses of graphs.

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 

Graphs in data structures are integral to various applications, providing efficient solutions in diverse fields. They model complex relationships, optimize logistics, enhance social media recommendations, and enable fraud detection. In bioinformatics and e-commerce, graphs uncover insights beyond traditional data structures. Graph databases further enable powerful querying, offering deeper analysis of interconnected datasets.

• Social Media Networks: Graphs model user relationships, enabling platforms like Facebook and LinkedIn to recommend friends based on mutual connections.
• Logistics Optimization: Graphs are used to calculate optimal delivery routes, minimizing time and cost, particularly in industries like transportation and logistics.
• Bioinformatics: In genomics, graphs represent genetic data to identify relationships and patterns, aiding drug discovery and disease prediction.
• Financial Fraud Detection: Graphs help trace and detect fraudulent transactions by analyzing real-time connections between different economic entities.
• E-commerce Recommendation Systems: Graphs power recommendation algorithms by analyzing user behavior and item relationships to suggest relevant products to customers.
• Graph Databases: Systems like Neo4j and Amazon Neptune provide efficient querying of complex networks of relationships, which traditional relational databases struggle to perform.

Now, let’s see when you can use graphs for several enterprise-related data analysis tasks. 

When to Use Graphs 

Graphs are essential in various advanced algorithms that solve real-world problems efficiently. Dijkstra's Algorithm finds the shortest path between two nodes in weighted graphs. In contrast, Prim's Algorithm helps compute the minimum spanning tree by connecting all nodes with the least weight.

Additionally, graph databases like Neo4j and Amazon Neptune are used for storing and querying complex data, offering advantages over traditional databases for graph-based data analysis.

Dijkstra's Algorithm:

• Finds the shortest path between nodes in a weighted graph.
• Iteratively selects the node with the smallest tentative distance and updates neighboring nodes until the destination is reached.

Use case:

GPS navigation for calculating optimal travel routes.
Prim's Algorithm:

• Computes the minimum spanning tree (MST) for a connected, weighted graph.
• Starts from an arbitrary node and gradually adds the nearest node to form a spanning tree with the minimum total weight.

Use case:

Network design involves minimizing the cost of connecting multiple points.
Graph Databases:

• Specialized databases for storing and querying complex relationships using graph theory.
• Efficiently handles complex queries involving traversing nodes and edges, ideal for highly connected data.

Use case:

Used by platforms like LinkedIn or Facebook for social graph data to provide real-time connections, recommendations, and relationship queries.

Let’s comprehensively discuss some of the pros and cons of graphs in data analytics. 

Pros & Cons of Graphs 

Graphs in data structures are powerful for modeling complex relationships, offering efficient shortest-path traversal and visual representations that simplify understanding intricate connections. They are well-suited for analyzing continuous data and provide versatile solutions across various domains. 

However, handling large-scale graphs introduces computational complexity, long processing times, and challenges maintaining data consistency and concurrency, especially in distributed graph databases.

Here’s a comparative table to address the pros and cons of graphs. 

Also read: Benefits and Advantages of Big Data & Analytics in Business

Conclusion

Graphs in data structures are fundamental for representing complex relationships between entities, offering efficient ways to model interactions in various fields. They are categorized into weighted, unweighted, directed, and undirected graphs, each suited for specific applications. 

Storing and traversing graphs can be achieved through adjacency lists and matrices, with algorithms like DFS and BFS enabling graph exploration.

If you want to learn skills to understand graphs in data structures, these additional courses from upGrad can help you succeed.

• Professional Certificate Program in Business Analytics & Consulting in association with PwC Academy
• Analyzing Patterns in Data and Storytelling
• Case Study using Tableau, Python and SQL

Curious which courses can help you gain expertise in graphs in data structures? Contact upGrad for personalized counseling and valuable insights. For more details, you can also visit your nearest upGrad offline center. 

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles

References

1. https://blog.csgsolutions.com/15-statistics-prove-power-data-visualization