Graphs in Data Structure: Types, Storing & Traversal

A data structure is an efficient way of organising data in a database 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

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

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.

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. 

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.

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.

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.    

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.

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

Conclusion

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