# 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.

## 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:*

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.

**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:

**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.**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.

## 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**

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