Graphs in Data Structure: Types, Representation, Operations

# Graphs in Data Structure: Types, Representation, Operations

clickHere
Anshuman Singh
Senior Executive - Content
Updated on Feb 14, 2024 11:13 IST

In data structures, graphs are a collection of nodes or vertices connected by edges. They are used to represent relationships and connections between different elements, allowing for efficient modelling and analysis of complex systems. Graphs provide a powerful framework for solving problems in various domains, such as network analysis, social media analysis, and route planning. Let's understand more!

Graphs are powerful data structures that represent real-life relationships between entities. Graphs are used everywhere, from social networks, Google Maps, and the World Wide Web to blockchains and neural networks. Due to their ability to provide abstractions to real life, they are used in various practical problems. This article will dive deep into graphs in the data structure, their types, terminologies, operations, representation, and applications.

## Overview of Graphs in Data Structure

Let us understand what is a graph in the data structure. Graphs are non-linear data structures comprising a set of nodes (or vertices), connected by edges (or arcs). Nodes are entities where the data is stored, and their relationships are expressed using edges. Edges may be directed or undirected. Graphs easily demonstrate complicated relationships and are used to solve many real-life problems.

For example, Facebook uses a graph data structure comprising a group of entities and their relationships. On Facebook, every user, photo, post, page, place, etc., that has data is represented with a node. Every edge from one node to another represents their relationships, friendships, ownerships, tags, etc. Whenever a user posts a photo, comments on a post, etc., a new edge is created for that relationship. Both nodes and edges have meta-data associated with them.

Explore popular courses on Shiksha Online:

Also read: 8 Most Important Data Structures Every Programmer Must Know

## Graph Terminologies in Data Structure

The following are some of the commonly used terms in graph data structure:

## Types of Graphs in Data Structure

The most common types of graphs in the data structure are below:

1. Undirected: A graph in which all the edges are bi-directional. The edges do not point in a specific direction.

2. Directed: A graph in which all the edges are uni-directional. The edges point in a single direction.

3. Weighted Graph: A graph with a value associated with every edge. The values corresponding to the edges are called weights. A value in a weighted graph can represent quantities such as cost, distance, and time, depending on the graph. We typically use weighted graphs in modelling computer networks.

An edge in a weighted graph is represented as (u, v, w), where:

• u is the source vertex
• v is the destination vertex
• w represents the weight associated with going from u to v

4. Unweighted Graph: A graph with no value or weight associated with the edge. All the graphs are unweighted by default unless there is a value associated.

An edge of an unweighted graph is represented as (u, v), where:

• u represents the source vertex
• v is the destination vertex

Also Read: Decision Trees in Data Mining

## Graph Representation in Data Structure

Below are the two most common ways of representing graphs in data structure:

An Adjacency Matrix is the simplest way to represent a graph. It is a 2D array of V x V vertices, with each row and column representing a vertex. The matrix consists of “0” or “1”. 0 depicts that there is no path, while 1 represents that there is a path.

It represents a graph as an array (A) of linked lists. The vertices are stored as an index of the one-dimensional array, and the edges are stored as a list. It means that each element of the array Ai is a list. It contains all the vertices adjacent to vertex i.

## Operations on Graph in Data Structure

Following are the basic graph operations in data structure:

• Add/Remove Vertex – Add or remove a vertex in a graph.
• Add/Remove Edge – Add or remove an edge between two vertices.
• Check if the graph contains a given value.
• Find the path from one vertex to another vertex.

## Graph Traversal in Data Structure

Graph traversal is visiting or updating each vertex in a graph. The order in which they visit the vertices classifies the traversals. There are two ways to implement a graph traversal:

1. Breadth-First Search (BFS) – It is a traversal operation that horizontally traverses the graph. It traverses all the nodes at a single level before moving to the next level. It begins at the graph’s root and traverses all the nodes at a single depth level before moving on to the next level.
2. Depth-First Search (DFS): This is another traversal operation that traverses the graph vertically. It starts with the root node of the graph and investigates each branch as far as feasible before backtracking.

Also Read: Top Online Courses for IT Professionals

Space Complexity in Data Structures
The space complexity helps to determine the efficiency and scalability of a solution, and it is an important factor to consider when choosing a data structure or designing an algorithm.
B Tree in Data Structure
A B-tree is a self-balancing data structure ideal for managing large data volumes. It ensures fast search, insert, and delete operations by keeping elements sorted and tree height minimal. B-trees...read more
Tree Traversal in Data Structure
Tree traversal is the process of systematically visiting each node in a tree data structure. It involves exploring the nodes in a specific order, such as inorder, preorder, or postorder,...read more

## Applications of Graphs in Data Structure

Graph data structures have a variety of applications. Some of the most popular applications are:

• It helps to define the flow of computation of software programs.
• Used in Google Maps for building transportation systems. In Google Maps, the intersection of two or more roads represents the node while the road connecting two nodes represents an edge. Google Maps algorithm uses graphs to calculate the shortest distance between two vertices.
• Operating Systems use a Resource Allocation Graph where every process and resource acts as a node. While we draw edges from resources to the allocated process.
• Used in the World Wide Web where the web pages represent the nodes.
• Blockchains also use graphs. The nodes store many transactions while the edges connect subsequent blocks.
• Used in modelling data.

Also read: How does Blockchain Work?

Some other applications of graphs include:

• Knowledge graphs
• Biological networks
• Neural networks
• Product recommendation graphs

Must Read: Top Data Structure Interview Questions [DS and Algorthims]

## Conclusion

Knowledge of graph operations in the data structure can help you understand programming concepts better and crack your coding interview. We hope this article gave you a fair understanding of what a graph is in the data structure, the terminology of the graph in the data structure, its types, graph operations in the data structure, representation, and applications. Check out our articles on Tree and Queue data structures to learn about other data structures.

## FAQs

Where are graph data structures used in real life?

Some of the real-life applications of graph data structure include Social Graphs, Knowledge Graphs, Path Optimization Algorithms, Recommendation Engines, and Scientific Computations.

What are the different types of graphs in data structure?

The different types of graphs based on the position of nodes and vertices are Directed Graph, Non-directed Graph, Null Graph, Simple Graph, Trivial Graph, Complete Graph, Cycle Graph, Cyclic Graph, Acyclic Graph, Connected Graph, Disconnected Graph, Regular Graph, Finite Graph, Infinite Graph, Pseudo Graph, Bipartite Graph, Planar Graph, Multi Graph, and Euler Graph.

What is a complete graph in data structure?

In a complete graph or fully connected graph in the data structure, every vertex has an edge to all other vertices. A graph is called a complete graph if there is a path from every vertex to every other vertex. A complete graph with n vertices is denoted Kn.

What is a directed acyclic graph?

A directed acyclic graph (DAG) is a graph that has directed edges and has no cycles connecting the other edges. The edges of a directed acyclic graph are represented with an ordered pair of vertices as it directs the vertices and stores some data.