Graphs in Data Structure: Types, Representation, Operations

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.

Explore: Data Structures and Algorithms Courses

Table of Content

• Overview of Graphs in Data Structure
• Graph Terminologies in Data Structure
• Types of Graphs in Data Structure
• Graph Representation in Data Structure
• Operations on Graph in Data Structure
• Graph Traversal in Data Structure
• Application of Graph in Data Structure

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:

1. Adjacency Matrix

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.

2. Adjacency List

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

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.
• Used in social networks such as Facebook and Linkedin.
• 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.