What is a Graph in Data Structures and its Types?

Graphs in Data Structures Examples

A Graph in Data Structures is a type of non-primitive and non-linear data structure. A graph is a basic and adaptable structure in data structures that is used to show relationships between pairs of elements. It is made up of directed and/or undirected edges joining nodes, also known as vertices. When solving real-world issues like social networks, network connection, and route optimization, graphs are crucial. They play a vital role in both theoretical and practical applications because they support a wide range of algorithms for tasks including searching, shortest path finding, and cycle recognition.

In this DSA tutorial, we will see a detailed starting of the graph in data structures i.e. its features, types, implementation, etc.

What is a Graph in Data Structures?

• A graph is a collection of nodes that consist of data and are connected to other nodes of the graph. Formally a Graph is composed of a set of vertices( V ) and a set of edges( E ).
• The graph is denoted by G(V, E).
• The most common real-life examples of graphs are social media, where a User, Photo, Album, Event, Group, Page, Comment, Story, Video, etc, represents a node.
• Every relationship is an edge from one node to another.
• Whenever you post a photo, join a group, like a page, etc., a new edge is created for that relationship.
• Thus, it can be said that a social media platform is a collection of nodes and edges.

Read More - Best Data Structure Interview Questions and Answers

Types of Graphs in Data Structures

1. Finite Graph

If the graph, G=(V, E) has a finite number of edges and vertices, it is a finite graph. In other words, both the number of vertices and the number of edges in a finite graph are limited and can be counted.

2. Infinite Graph

If the graph G=(V, E) has an infinite number of edges and vertices, it is an infinite graph.

3. Trivial Graph

If a finite graph G=(V, E) has just one vertex and no edges, it is referred to as trivial. It is also known as a singleton graph or a single vertex graph.

4. Simple Graph

A graph G=(V, E) is a simple one if each pair of nodes or vertices contains just one edge. In order to represent one-to-one interactions between two elements, there is only one edge connecting two vertices.

5. Multi Graph

A graph G=(V, E) is referred to as a multigraph if it has some parallel edges between two vertices but doesn't contain any self-loop. An edge of a graph that starts from a vertex and ends at the same vertex is called a loop or a self-loop.

6. Null Graph

It's a revised version of a trivial graph. A graph G=(V, E) is a null graph if it has many vertices, but none of them are connected by any edges. A null graph can also be referred to as an edgeless graph, an isolated graph, or a discrete graph.

7. Complete Graph

A simple graph G=(V, E) with n vertices is also called a complete graph if the degree of each vertex is n-1, i.e. one vertex is attached with n-1 edges or the rest of the vertices in the graph. A complete graph is also called a Full Graph.

8. Pseudo Graph

A pseudograph exists when a graph G= (V, E) contains some self-loop in addition to some multiple edges.

9. Regular Graph

10. Weighted Graph

A graph G=(V, E) in which edges have weights or costs associated with them is a weighted graph.

11. Directed Graph

A directed graph, also known as a digraph, is a collection of nodes connected by edges, each with a distinct direction.

12. Undirected Graph

A graph G=(V, E) in which edges have no direction, i.e., the edges do not have arrows indicating the direction of traversal is an undirected graph.

13. Connected Graph

A graph G = (V, E) is said to be connected if there exists at least one path between each and every pair of vertices in the graph.

14. Disconnected Graph

If in a graph G = (V, E), there does not exist any path between at least one pair of vertices, it is a disconnected graph. A null graph with n vertices is a disconnected graph.

15. Cyclic Graph

A graph is termed cyclic if it forms at least one cycle.

16. Acyclic Graph

A graph is said to be acyclic if it contains no cycles.

17. Directed Acyclic Graph

It is a graph with directed edges but no cycle.

18. Subgraph

A subgraph is a set of vertices and edges in one graph that are subsets of another.

Graph Terminologies in Data Structures

Graph terminology in data structure refers to the specific vocabulary and concepts used to describe and analyze graphs, which are mathematical structures composed of nodes (also called vertices) connected by edges.

1. Node/Vertex: A fundamental unit of a graph. It represents an entity or an element and is usually depicted as a point.
2. Edge/Arc: A connection between two nodes. It represents a relationship or a link between the corresponding entities. An edge can be directed (arc), indicating a one-way connection, or undirected, representing a two-way connection.
3. Adjacent Nodes: Two nodes that are directly connected by an edge. In an undirected graph, both nodes are considered adjacent to each other. In a directed graph, adjacency depends on the direction of the edge.
4. Degree: The degree of a node is the number of edges incident to it, i.e., the number of edges connected to that node. In a directed graph, the degree is divided into two categories: the in-degree (number of incoming edges) and the out-degree (number of outgoing edges).
5. Path: A path in a graph is a sequence of edges that connects a sequence of nodes. It can be a simple path (no repeated nodes) or a closed path/cycle (starts and ends at the same node).
6. Bipartite Graph: A graph whose nodes can be divided into two disjoint sets such that every edge connects a node from one set to a node from the other set. In other words, there are no edges between nodes within the same set.
7. Spanning Tree: A subgraph of a connected graph that includes all the nodes of the original graph and forms a tree (a connected acyclic graph) by eliminating some of the edges.
8. Cycle: A closed path in a graph, where the first and last nodes are the same. It consists of at least three edges.

Graph Representation in Data Structures

• Graph representation is a way of structuring and visualizing data using nodes (vertices) and edges. It is also a technique for storing graphs in a computer's memory.
• In a graph, nodes represent individual entities, while edges represent the relationships or connections between those entities. Depending on whether the edges have a specific direction, the connections can be directional or undirected.

There are two ways to represent a graph

1. Adjacency Matrix

An Adjacent Matrix is a 2D array of size V x V, where V is the number of nodes in a graph. It is used to represent a finite graph, with 0s and 1s. Since it's a V x V matrix, it is known as a square matrix. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph, i.e., whetherthere is any edge connecting a pair of nodes in the graph.

Representation of Undirected Graph

Representation of a Directed Graph

Weighted Undirected Graph Representation

A weighted graph representing these values in the matrix is indicated at the graph's edge.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

Weighted Undirected Graph Representation Using Linked-List

Weighted Undirected Graph Representation Using an Array

Operations on Graphs in Data Structures

The following common operations are performed on graphs in data structures:

1. Insert vertex

It is a simple addition of a vertex(node) in a graph. It need not be connected to any other vertex(node) through an edge.

2. Delete vertex

To delete a nod, we also have to remove all the edges associated with that vertex.

3. Insert Edge

It adds an edge between a pair of vertices.

4. Delete Edge

An edge can be deleted by severing the link between its vertices or nodes. If all the edges from a particular vertex(node) are removed, then that vertex(node) becomes an isolated vertex.

5. Graph Traversal

Graph traversal is the process of going through or updating each vertex in a graph. Such traversals are classified according to the order in which the algorithm visits the vertices. A subset of tree traversal is graph traversal.

There are two algorithms/ways to visit a graph:

1. Breadth-first search
2. Depth-first search

We will study all these two in the section Breadth First Traversal and Depth First Traversal

Application of Graphs

1. Maps GPS Systems can be represented using graphs and then can be used by computers to provide various services.
2. When various tasks depend on each other, it can be represented using a Directed Acyclic graph and we can find the order in which tasks can be performed using topological sort.
3. State Transition Diagram represents what can be the legal moves from current states.
4. Graphs can be used to represent the topology of computer networks, such as the connections between routers and switches.

Advantages of Graphs

1. Graphs can be used to represent a wide range of relationships and data structures.
2. They can be used to model and solve a wide range of problems, including pathfinding, data clustering, network analysis, and machine learning.
3. Graph algorithms are often very efficient and can be used to solve complex problems quickly and effectively.
4. They can be used to represent complex data structures simply and intuitively, making them easier to understand and analyze.

Disadvantages of Graphs

1. Graphs can be complex and difficult to understand, especially for people not familiar with graph theory or related algorithms.
2. Creating and manipulating graphs can be computationally expensive, especially very large or complex graphs.
3. Graph algorithms can be difficult to design and implement correctly and can be prone to bugs and errors.
4. Graphs can be difficult to visualize and analyze, especially for very large or complex graphs, which can make it challenging to extract meaningful insights from the data.

Summary

So, here we saw a detailed introduction to graphs in data structures. You might have got at least some idea regarding graphs and their applications. We will cover all its aspects one by one in the upcoming tutorials. To further enhance your understanding and application of graph concepts, consider enrolling in the DSA Certification Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.