A graph refers to a non-linear data structure with edges and vertices. The graphs in the data structure can be considered a cyclic tree with no parent-child relationship between the nodes. Instead, the nodes or vertices in a graph maintain a complex relationship between them.
You can define a graph in the data structure as an ordered set G (V, E). Here, V(G) refers to the vertices, and E(G) refers to the set of edges for connecting the vertices. Dive into this article to explore the different types of graphs in a data structure.
Table of Contents:
What is Graph Data Structure
A graph data structure is a collection of nodes (also called vertices) interconnected by edges. It is a fundamental data structure used to represent and analyze relationships between objects. Graphs are widely used in computer science and various domains, including social networks, transportation networks, computer networks, and more. Graphs in Data Structure have innumerable usage in real life and are used in multiple ways. Below you read the major types of graphs in data structures that we use on day to day basis.
Components of Graph in Data Structure
The different components of graph representation in the data structure are as follows:
- Vertices: They are the fundamental units of any graph. A vertex or node can be labeled or unlabelled.
- Edges: Edges are leveraged for connecting two nodes of a graph. The edges can also be an ordered node pair within a directed graph. Edges can connect two nodes in innumerable ways, and there are no rules regarding the connection. At times, the edges are also referred to as arcs. An edge can either be labeled or unlabeled.
Enroll: Full Stack Development course
Explanation of Directed and Undirected Graphs
A graph can either be directed or undirected. You will see the edges creating an ordered pair in a directed graph. Edges will represent a particular path from vertex A to vertex B. While node A will be the initial mode, node B will be the terminal node.
In an undirected graph representation in a data structure, edges don’t symbolize any direction. If an edge is found between vertex A and vertex B, it can be traversed from A to B as well as from B to A.
Types of Graphs in Data Structures
Now that you’ve learned about what are graphs in data structures, you will learn about their various types. Here is the list of different types of graphs in data structure:
Simple Graph
In a simple graph, every pair of nodes or vertices has a single edge. Therefore, only a single edge links two vertices and facilitates one-to-one interactions between two elements.
Infinite Graph
An infinite graph representation in data structure has an interminable number of edges and vertices.
Trivial Graph
Trivial graphs in data structure have only one vertex and no edges.
Multi Graph
These types of graphs in data structure contain numerous edges amidst a pair of vertices. A multigraph contains no self-loops.
Null Graph
A null graph representation in data structure comes with multiple vertices, but edges don’t connect them. A null graph can be described as a reworked trivial graph.
Complete Graph
All simple graphs are complete. The edges can help connect n number of vertices. They are also called full graphs because every vertex has a n-1 degree.
Regular Graph
Any simple graph with every vertex having the same degree can be called a regular graph. Therefore, every whole graph is a regular graph.
Pseudo Graph
A pseudo graph representation in data structure has a self-loop and various edges.
Acyclic Graph
These types of graphs in data structure contain no cycles.
Weighted Graph
A weighted or labeled graph representation in a data structure contains edges with a value indicating the traversal cost.
Directed Graph
A directed or digraph comes with a set of nodes linked by edges. Every node comes with a specific direction.
Undirected Graph
An undirected graph contains various nodes and links connecting them. The order of the connected vertices isn’t relevant and lacks direction. An undirected graph can contain a specific number of edges and vertices.
Check out: Data Warehousing and Data Mining
Terminologies of Graphs in Data Structures
The common terminologies associated with the representation of graph in the data structure:
- Adjacency: If an edge connects one vertex to another, they are known to be adjacent.
- Path: A sequence of edges that enables you to move from vertex A to B is referred to as the path.
- Cycle: It refers to the path with no repeated vertices or edges except for the first and last ones.
Internship Assurance
DevOps & Cloud Engineering
Graph Traversal Algorithms
Graph traversal, a subset of tree traversal, is the process of visiting or updating the vertex in a graph. The two techniques for graph traversal algorithms are as follows:
Depth-First Search
This search technique explores data structures like trees and graphs. It begins at the root node and continues with the examination as far as possible before backtracking. A stack is required to keep track of the child nodes that have been encountered but not inspected.
Breadth-First Search
This search technique begins at the graph root and examines all nodes at one depth level before moving on to the next depth level. A queue is required to keep track of the child nodes that have been encountered but not inspected.
Explore: Data Structures in Java
Operations on Graphs in Data Structures
The possible operations on graphs in data structures are as follows:
- Creating graphs
- Inserting vertex
- Deleting vertex
- Inserting edge
- Deleting edge
Graph Representation
The types of graphs in the data structure are used for representing relationships between objects. The most frequent graph representation in data structure follows the adjacency matrix and the adjacency list.
Adjacency Matrix
The adjacency matrix is a common data structure used to represent a graph in graph theory and computer science. It is a square matrix where the rows and columns represent the nodes (vertices) of the graph. The elements of the matrix indicate the presence or absence of edges between the nodes.
In an adjacency matrix, each row and column corresponds to a specific node in the graph. The value stored in the matrix at the intersection of row i and column j represents the relationship between node i and node j. It can be a boolean value (0 or 1) indicating the presence or absence of an edge, or it can be a weight value representing the strength or distance of the edge.
Suppose we have a graph with four nodes (A, B, C, and D) and the following edges:
A is connected to B and C
B is connected to A and D
C is connected to A and D
D is connected to B and C
The adjacency matrix representation of this graph would be:
A B C D
A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 1]
D [0, 1, 1, 0]
Adjacency List
The adjacency list is a common data structure used to represent a graph in graph theory and computer science. It provides a compact and efficient representation of a graph, especially for sparse graphs where the number of edges is relatively small compared to the number of nodes.
In the adjacency list representation, each node in the graph is associated with a list of its adjacent nodes. This list contains references or pointers to other nodes that are directly connected to the given node by an edge.
Suppose we have a graph with four nodes (A, B, C, and D) and the following edges:
A is connected to B and C
B is connected to A and D
C is connected to A and D
D is connected to B and C
The adjacency list representation of this graph would be:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
Application of Graphs in Data Structures
A few applications of graphs in data structures are as follows:
- Depicting the computational flow
- Friend suggestion system on Facebook
- Resource allocation graphs in operating systems
- Web pages on the world wide web
Conclusion
In this article we have covered all about the graphs in data structure. Hopefully, now you are familiar with the different types of graphs in the data structure. The primary methods of graph traversal include depth-first and breadth-first data structures. The different types of graphs in data structures are used for various real-life applications.
FAQs
A graph refers to a non-linear data structure with multiple edges and vertices. One of the most common examples of Python graph data structure is social media. Social media platforms utilize graphs to store information about users.
Shortest path algorithms are used for calculating the shortest path between two nodes. It is an informed search algorithm that applies the heuristic function to navigate the graph traversal. The shortest path algorithm supports weighted graphs with positive relationship weights.
The different types of graphs in data structure include simple graphs, trivial graphs, null graphs, pseudo graphs, regular graphs, multigraphs, complete graphs, acrylic graphs, directed graphs, undirected graphs, and more.
You will come across more than ten types of graphs in the data structure. The most common graph is the finite graph.
Graphs can be used to analyze structured as well as unstructured data.