Graphs in Data Structure: Types, Storing & Traversal

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.

Read: Top 10 Data Visualization Techniques

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 –

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

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

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.