Graphs in Data Structure: Types, Representation, Operations

Graphs in Data Structure: Types, Representation, Operations

7 mins read66.8K Views Comment
clickHere
Anshuman
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!

2021_09_Graphs-in-Data-Structure-1.jpg

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.

Table of Content

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.

2021_09_Graph-Data-Structure.jpg

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:

Popular Big Data Courses Top Cloud Technologies Courses
Popular Programming Courses Top Databases Courses

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:

Term Description
Vertex Every individual data element is called a vertex or a node. In the above image, the vertices are A, B, C, D & E.
Edge (Arc) It is a connecting link between two nodes or vertices. Each edge has two ends and is represented as (startingVertex, and endingVertex).
Undirected Edge It is a bidirectional edge.
Directed Edge It is a unidirectional edge.
Weighted Edge An edge with value (cost) on it.
Degree The total number of edges connected to a vertex in a graph.
Indegree The total number of incoming edges connected to a vertex.
Outdegree The total number of outgoing edges connected to a vertex.
Self-loop An edge is called a self-loop if its two endpoints coincide.
Adjacency Vertices are said to be adjacent if an edge is connected.

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.

2021_09_Undirected-Graphs.jpg
 

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

2021_09_Directed-Graphs.jpg

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
2021_09_Weighted-Graph.jpg

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

Space Complexity in Data Structures
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
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 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.
  • 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.

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.

About the Author
author-image
Anshuman Singh
Senior Executive - Content

Anshuman Singh is an accomplished content writer with over three years of experience specializing in cybersecurity, cloud computing, networking, and software testing. Known for his clear, concise, and informative wr... Read Full Bio