Types of Graphs in Data Structure & Applications

Introduction

A graph is a non-linear structure comprising nodes and edges. It can include a finite or infinite set of nodes held by an edge connecting a pair of nodes. Data structures are an essential part of any coding concept; thus, having a firm grasp of different types of graphs in data structures can assist you through complex real-world problems.

In today’s world, data is power. Thus, organizing data efficiently for easy access is essential for any programmer. Knowledge of data structures and its variety of graphs empowers your coding skills to target real-world problems and effectively deliver its solutions.

Learn data science to gain edge over your competitors

Let’s take a look at different types of graphs commonly used in data structures and how they are applied in real life.

Types of Graphs in Data Structures 

A data structure is a practical data storage standard for all languages, such as python graph data structure or java graph data structure. Mastering all types of graphs should be a priority for anyone aspiring to study data structures. Since graph theory has many real-life applications, they become vital in data structures.

The various types of graphs in Data structures can be listed below:

1. Null Graph

As the name suggests, the null graph is empty; in other words, it is a graph with no edges. It only consists of isolated vertices in the graph with a vacant edge set.

2. Finite Graph

If the number of edges and nodes consists of a finite number in a graph, then the graph is known as a finite graph.

3. Infinite Graph

If one cannot put a finite number to the number of nodes and the number of edges in a graph, the graph is known as an infinite graph. Infinite graphs are uncountable, which means you cannot count the number of nodes or edges in this type of graph. 

4. Simple Graph

A graph is said to be simple when there is only one edge between a pair of vertices. Thus, two nodes are connected by one edge in a graph, which can identify a definite relationship between them. 

5. Multi Graph

If a pair of nodes is connected with multiple edges in a graph, then the graph is known as a multi-graph. A multi-graph does not consist of self-loops. There are two kinds of edges that can exist in a multi-graph. They are:

• Parallel Edges

Edges that run parallel, like two parallel roads going from one source to the same destination, are known as parallel edges.

• Loop

This is an edge whose source and destination vertices are the same.

6. Directed Graph

A graph is said to be directed if all the edges present between two nodes or vertices have a defined direction. A directed graph is also known as a digraph. We can determine the starting and ending node by looking at a directed graph. Remember, all the edges in a directed graph must be directed to be called a directed graph.

7. Non-Directed Graph

A graph is said to be a non-directed graph if it is hard to identify the starting and ending node by looking at its edges. Just like a directed graph, the edges have to be non-directed for it to be called a non-directed graph. 

8. Connected Graph

A connected graph is a graph where at least one path exists between all nodes. In simpler terms, if you start from a node in a connected graph, you should be able to visit every node present in the graph. Hence, there should be at least one path for every node. 

9. Disconnected Graph

In this type of graph, no edge exists between a pair of nodes or vertices. Thus, unlike connected graphs, reaching all the nodes from just any vertice is not possible.  If any pair of vertices do not have a path between them, it is called a disconnected graph.

10. Complete Graph

A graph is only considered complete when an edge exists between every node, meaning an edge will connect all the vertices in the graph. A complete graph on n vertices is denoted as Kn, and the number of edges in the graph is nC2.

11. Cyclic Graph

A graph should have at least one cyclic component to be considered a cyclic graph. On the contrary, if the graph does not contain any cycle, it is considered an acyclic graph.

12. Regular Graph

In a regular graph, all the vertices should have the same degree. The degree of a node can be defined as the number of nodes connected with it. Thus, in a regular graph, all the nodes should be connected to the same number of nodes.

13. Bipartite Graph 

For a graph to be bipartite, it should satisfy the following criteria.

• The graph should be divided into sets of vertices.
• Edges should only form between one group of nodes to the other side. This rule prevents the connection between two vertices of the same set of nodes.
• The two groups should not have any common vertices between them.

A graph following all the above rules should be considered a bipartite graph.

14. Labeled Graph

The edges in graphs can be weighted. A weight associated with an edge can be understood as the cost of traveling through that edge. These values can be based on a fixed parameter and can change between graphs. Now, if all the edges hold some weight associated with them, then that graph can be termed a labeled graph.

15. Directed Acyclic Graph

A directed acyclic graph is a combination of directed and acyclic graphs where the directed edges of the graph do not make any form of cycle. On the contrary, a directed cyclic graph is a graph with directed edges that forms a cycle.

Application of Graph in Data Structure

The most prominent application of a graph in computer science is the representation of the flow of computation. Some other famous used cases of graphs are:

1. Google Maps

In Google Maps, graph data structures define and compute the transport system. When a road is met with another road and forms a crossing, it is considered a node, and the road between two such nodes is treated as an edge. Hence,  Google Maps finds you the shortest and quickest way to your destination using the graph data structure. 

2. Facebook

Facebook uses undirected graphs to identify a user and the user’s friends. Every user is treated as the vertices, and the connections joining them as friends are the network’s edges. With algorithms based on graph data structure, Facebook suggests “people you may know” and shows “mutual friends.”

3. World wide web

The World Wide Web is an example of a directed graph. It is also the basic idea behind the Google ranking system. In the World Wide Web system, every website and web app is treated as a node or vertices, and the links from one website to another are considered the edge.

4. Operating System

The operating system is a popularly used case of Resource Allocation Graphs that uses every process and resource as nodes or vertices. Edges occur between resources to the allocated process or from requesting process to requested resources. Sometimes this cycle might form an infinite loop, initializing the deadlock.

5. Mapping System

Your GPS is a popularly used case of graphs to locate nearby restaurants, shops, and places you choose to search with the help of this technology.

6. Microsoft Excel

Directed Acyclic Graphs or DAG is used in Microsoft Excel.

7. The Dijkstra algorithm

The Dijkstra Algorithm uses graph data structure to identify the shortest path between two, or in some cases, more than two nodes.

8. Flight Networks:

Computing optimized flight networks is another real-life application of graph data structure. If you consider the airports as nodes and the routes as the edges, the data perfectly fit the criteria of graphs. That is why with the help of various enhanced algorithms, the best routes between two airports or nodes are determined.

These are the various applications of graphs in the data structure, used across the globe in various applications and systems to organize and maintain their smooth functioning, 

Get started on your journey as a data scientist

If you want to become a data scientist and handle data tactfully using the various graphs we learned, check out an extensive range of data science courses on upGrad. One of the most popular courses is the PG-IIITB course on Data Science, an excellent course for aspiring and budding data scientists to get started! 

Here’s what the course offers.

• 360-degree career support from industry experts and mentors
• Hands-on experience with Industry Projects and detailed case studies to gauge regular progress
• Networking with data science experts across all sectors, globally

You can also check all the other upGrad courses on Data Science.