What is a Graph?

A graph is an abstract data type (ADT) which consists of a set of objects that are connected to
each other via links. The interconnected objects are represented by points termed as vertices, and
the links that connect the vertices are called edges.

Or

Graphs in data structures are non-linear data structures made up of a finite number of nodes or
vertices and the edges that connect them. Graphs in data structures are used to address real-
world problems in which it represents the problem area as a network like telephone networks,
circuit networks, and social networks. For example, it can represent a single user as nodes or
vertices in a telephone network, while the link between them via telephone represents edges.

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the
pairs of vertices. Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

What Are Graphs in Data Structure?

A graph is a non-linear kind of data structure made up of nodes or vertices and

edges. The edges connect any two nodes in the graph, and the nodes are also
known as vertices.
This graph has a set of vertices V= { 1,2,3,4,5} and a set of edges E= {
(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,50 }.

Now that you’ve learned about the definition of graphs in data structures, you will
learn about their various types.

Types of Graphs in Data Structures

There are different types of graphs in data structures, each of which is detailed
below.

1. Finite Graph

The graph G=(V, E) is called a finite graph if the number of vertices and edges in the
graph is limited in number
2. Infinite Graph

The graph G=(V, E) is called a finite graph if the number of vertices and edges in the
graph is interminable.

3. Trivial Graph

A graph G= (V, E) is trivial if it contains only a single vertex and no edges.

4. Simple Graph

If each pair of nodes or vertices in a graph G=(V, E) has only one edge, it is a
simple graph. As a result, there is just one edge linking two vertices, depicting one-
to-one interactions between two elements.
5. Multi Graph

If there are numerous edges between a pair of vertices in a graph G= (V, E), the
graph is referred to as a multigraph. There are no self-loops in a Multigraph.

6. Null Graph

It's a reworked version of a trivial graph. If several vertices but no edges connect
them, a graph G= (V, E) is a null graph.

7. Complete Graph

If a graph G= (V, E) is also a simple graph, it is complete. Using the edges, with n
number of vertices must be connected. It's also known as a full graph because each
vertex's degree must be n-1.
8. Pseudo Graph

If a graph G= (V, E) contains a self-loop besides other edges, it is a pseudograph.

9. Regular Graph

If a graph G= (V, E) is a simple graph with the same degree at each vertex, it is a
regular graph. As a result, every whole graph is a regular graph.

10. Weighted Graph

A graph G= (V, E) is called a labeled or weighted graph because each edge has a
value or weight representing the cost of traversing that edge.
11. Directed Graph

A directed graph also referred to as a digraph, is a set of nodes connected by

edges, each with a direction.

12. Undirected Graph

An undirected graph comprises a set of nodes and links connecting them. The order
of the two connected vertices is irrelevant and has no direction. You can form an
undirected graph with a finite number of vertices and edges.

13. Connected Graph

If there is a path between one vertex of a graph data structure and any other vertex,
the graph is connected.
14. Disconnected Graph

When there is no edge linking the vertices, you refer to the null graph as a
disconnected graph.

15. Cyclic Graph

If a graph contains at least one graph cycle, it is considered to be cyclic.

16. Acyclic Graph

When there are no cycles in a graph, it is called an acyclic graph.

17. Directed Acyclic Graph

It's also known as a directed acyclic graph (DAG), and it's a graph with directed
edges but no cycle. It represents the edges using an ordered pair of vertices since it
directs the vertices and stores some data.

18. Subgraph

The vertices and edges of a graph that are subsets of another graph are known as a
subgraph.

After you learn about the many types of graphs in graphs in data structures, you will
move on to graph terminologies.

Terminologies of Graphs in Data Structures

Following are the basic terminologies of graphs in data structures:

 An edge is one of the two primary units used to form graphs. Each edge has two
ends, which are vertices to which it is attached.

 If two vertices are endpoints of the same edge, they are adjacent.

 A vertex's outgoing edges are directed edges that point to the origin.
 A vertex's incoming edges are directed edges that point to the vertex's
destination.

 The total number of edges occurring to a vertex in a graph is its degree.

 The out-degree of a vertex in a directed graph is the total number of outgoing

edges, whereas the in-degree is the total number of incoming edges.

 A vertex with an in-degree of zero is referred to as a source vertex, while one

with an out-degree of zero is known as sink vertex.

 An isolated vertex is a zero-degree vertex that is not an edge's endpoint.

 A path is a set of alternating vertices and edges, with each vertex connected by
an edge.

 The path that starts and finishes at the same vertex is known as a cycle.

 A path with unique vertices is called a simple path.

 For each pair of vertices x, y, a graph is strongly connected if it contains a

directed path from x to y and a directed path from y to x.

 A directed graph is weakly connected if all of its directed edges are replaced with
undirected edges, resulting in a connected graph. A weakly linked graph's
vertices have at least one out-degree or in-degree.

 A tree is a connected forest. The primary form of the tree is called a rooted tree,
which is a free tree.

 A spanning subgraph that is also a tree is known as a spanning tree.

 A connected component is the unconnected graph's most connected subgraph.

 A bridge, which is an edge of removal, would sever the graph.

 Forest is a graph without a cycle.

Following that, you will look at the graph representation in this data structures
tutorial.

Representation of Graphs in Data Structures

Graphs in data structures are used to represent the relationships between objects.
Every graph consists of a set of points known as vertices or nodes connected by
lines known as edges. The vertices in a network represent entities.

The most frequent graph representations are the two that follow:

 Adjacency matrix
 Adjacency list

You’ll look at these two representations of graphs in data structures in more detail:

Adjacency Matrix

 A sequential representation is an adjacency matrix.

 It's used to show which nodes are next to one another. I.e., is there any
connection between nodes in a graph?

 You create an MXM matrix G for this representation. If an edge exists between
vertex a and vertex b, the corresponding element of G, gi,j = 1, otherwise gi,j = 0.

 If there is a weighted graph, you can record the edge's weight instead of 1s and
0s.

Undirected Graph Representation

Directed Graph Representation

Weighted Undirected Graph Representation

Weight or cost is indicated at the graph's edge, a weighted graph representing these

values in the matrix.

Adjacency List

 A linked representation is an adjacency list.

 You keep a list of neighbors for each vertex in the graph in this representation. It
means that each vertex in the graph has a list of its neighboring vertices.

 You have an arra of vertices indexed by the vertex number, and the
corresponding array member for each vertex x points to a singly linked list of x's
neighbors.
Weighted Undirected Graph Representation Using Linked-List

Weighted Undirected Graph Representation Using an Array

You will now see which all operations are conducted in graphs data structure after
understanding the representation of graphs in the data structure.

Operations on Graphs in Data Structures

The operations you perform on the graphs in data structures are listed below:

 Creating graphs

 Insert vertex

 Delete vertex

 Insert edge
 Delete edge

Insert Vertex

When you add a vertex that after introducing one or more vertices or nodes, the
graph's size grows by one, increasing the matrix's size by one at the row and
column levels.

Delete Vertex

 Deleting a vertex refers to removing a specific node or vertex from a graph that
has been saved.

 If a removed node appears in the graph, the matrix returns that node. If a deleted
node does not appear in the graph, the matrix returns the node not available.
Insert Edge

Connecting two provided vertices can be used to add an edge to a graph.

Delete Edge

The connection between the vertices or nodes can be removed to delete an edge.

The types of graph traversal algorithms will be discussed next in the graphs in this
data structures tutorial.

Graph Traversal Algorithm

The process of visiting or updating each vertex in a graph is known as graph
traversal. The sequence in which they visit the vertices is used to classify such
traversals. Graph traversal is a subset of tree traversal.

There are two techniques to implement a graph traversal algorithm:

 Breadth-first search
 Depth-first search

Breadth-First Search or BFS

BFS is a search technique for finding a node in a graph data structure that meets a
set of criteria.

 It begins at the root of the graph and investigates all nodes at the current depth
level before moving on to nodes at the next depth level.

 To maintain track of the child nodes that have been encountered but not yet
inspected, more memory, generally you require a queue.

Algorithm of breadth-first search

Step 1: Consider the graph you want to navigate.

Step 2: Select any vertex in your graph, say v1, from which you want to traverse the
graph.

Step 3: Examine any two data structures for traversing the graph.

 Visited array (size of the graph)

 Queue data structure

Step 4: Starting from the vertex, you will add to the visited array, and afterward, you
will v1's adjacent vertices to the queue data structure.

Step 5: Now, using the FIFO concept, you must remove the element from the
queue, put it into the visited array, and then return to the queue to add the adjacent
vertices of the removed element.
Step 6: Repeat step 5 until the queue is not empty and no vertex is left to be visited.

Depth-First Search or DFS

DFS is a search technique for finding a node in a graph data structure that meets a
set of criteria.

 The depth-first search (DFS) algorithm traverses or explores data structures such
as trees and graphs. The DFS algorithm begins at the root node and examines
each branch as far as feasible before backtracking.

 To maintain track of the child nodes that have been encountered but not yet
inspected, more memory, generally a stack, is required.

Algorithm of depth-first search

Step 1: Consider the graph you want to navigate.

Step 2: Select any vertex in our graph, say v1, from which you want to begin
traversing the graph.

Step 3: Examine any two data structures for traversing the graph.

 Visited array (size of the graph)

 Stack data structure

Step 4: Insert v1 into the array's first block and push all the adjacent nodes or
vertices of vertex v1 into the stack.

Step 5: Now, using the FIFO principle, pop the topmost element and put it into the
visited array, pushing all of the popped element's nearby nodes into it.

Step 6: If the topmost element of the stack is already present in the array, discard it
instead of inserting it into the visited array.

Step 7: Repeat step 6 until the stack data structure isn't empty.

You will now look at applications of graph data structures after understanding the
graph traversal algorithm in this tutorial.

Application of Graphs in Data Structures

Following are some applications of graphs in data structures:

 Graphs are used in computer science to depict the flow of computation.

 Users on Facebook are referred to as vertices, and if they are friends, there is an
edge connecting them. The Friend Suggestion system on Facebook is based on
graph theory.

 You come across the Resource Allocation Graph in the Operating System, where
each process and resource are regarded vertically. Edges are drawn from
resources to assigned functions or from the requesting process to the desired
resource. A stalemate will develop if this results in the establishment of a cycle.
 Web pages are referred to as vertices on the World Wide Web. Suppose there is
a link from page A to page B that can represent an edge. This application is an
illustration of a directed graph.

 Graph transformation systems manipulate graphs in memory using rules. Graph

databases store and query graph-structured data in a transaction-safe,
permanent manner.

Finally, in this tutorial, you’ll look at the code for the graphs in data structures

Spanning tree
In this article, we will discuss the spanning tree and the minimum spanning tree. But
before moving directly towards the spanning tree, let's first see a brief description of the
graph and its types.

Graph
A graph can be defined as a group of vertices and edges to connect these vertices. The
types of graphs are given as follows -

o Undirected graph: An undirected graph is a graph in which all the edges do

not point to any particular direction, i.e., they are not unidirectional; they are
bidirectional. It can also be defined as a graph with a set of V vertices and a
set of E edges, each edge connecting two different vertices.
o Connected graph: A connected graph is a graph in which a path always
exists from a vertex to any other vertex. A graph is connected if we can reach
any vertex from any other vertex by following edges in either direction.
o Directed graph: Directed graphs are also known as digraphs. A graph is a
directed graph (or digraph) if all the edges present between any vertices or
nodes of the graph are directed or have a defined direction.
Now, let's move towards the topic spanning tree.

What is a spanning tree?

A spanning tree can be defined as the subgraph of an undirected connected graph. It
includes all the vertices along with the least possible number of edges. If any vertex is
missed, it is not a spanning tree. A spanning tree is a subset of the graph that does not
have cycles, and it also cannot be disconnected.

A spanning tree consists of (n-1) edges, where 'n' is the number of vertices (or nodes).
Edges of the spanning tree may or may not have weights assigned to them. All the
possible spanning trees created from the given graph G would have the same number of
vertices, but the number of edges in the spanning tree would be equal to the number of
vertices in the given graph minus 1.
A complete undirected graph can have nn-2 number of spanning trees where n is the
number of vertices in the graph. Suppose, if n = 5, the number of maximum possible
spanning trees would be 55-2 = 125.

Applications of the spanning tree

Basically, a spanning tree is used to find a minimum path to connect all nodes of the
graph. Some of the common applications of the spanning tree are listed as follows -

o Cluster Analysis
o Civil network planning
o Computer network routing protocol
Now, let's understand the spanning tree with the help of an example.

Example of Spanning tree

Suppose the graph be -

As discussed above, a spanning tree contains the same number of vertices as the graph,
the number of vertices in the above graph is 5; therefore, the spanning tree will contain 5
vertices. The edges in the spanning tree will be equal to the number of vertices in the
graph minus 1. So, there will be 4 edges in the spanning tree.

Some of the possible spanning trees that will be created from the above graph are given
as follows -
Properties of spanning-tree
Some of the properties of the spanning tree are given as follows -

o There can be more than one spanning tree of a connected graph G.

o A spanning tree does not have any cycles or loop.
o A spanning tree is minimally connected, so removing one edge from the tree
will make the graph disconnected.
o A spanning tree is maximally acyclic, so adding one edge to the tree will
create a loop.
o There can be a maximum nn-2 number of spanning trees that can be created
from a complete graph.
o A spanning tree has n-1 edges, where 'n' is the number of nodes.
o If the graph is a complete graph, then the spanning tree can be constructed by
removing maximum (e-n+1) edges, where 'e' is the number of edges and 'n' is
the number of vertices.
So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a
disconnected graph.

Minimum Spanning tree

A minimum spanning tree can be defined as the spanning tree in which the sum of the
weights of the edge is minimum. The weight of the spanning tree is the sum of the weights
given to the edges of the spanning tree. In the real world, this weight can be considered
as the distance, traffic load, congestion, or any random value.

Example of minimum spanning tree

Let's understand the minimum spanning tree with the help of an example.

The sum of the edges of the above graph is 16. Now, some of the possible spanning trees
created from the above graph are -
So, the minimum spanning tree that is selected from the above spanning trees for the
given weighted graph is -

Applications of minimum spanning tree

The applications of the minimum spanning tree are given as follows -

o Minimum spanning tree can be used to design water-supply networks,

telecommunication networks, and electrical grids.
o It can be used to find paths in the map.

Algorithms for Minimum spanning tree

A minimum spanning tree can be found from a weighted graph by using the algorithms
given below -

o Prim's Algorithm
o Kruskal's Algorithm
Let's see a brief description of both of the algorithms listed above.

Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It is
used to find the minimum spanning tree from the graph. This algorithm finds the subset of
edges that includes every vertex of the graph such that the sum of the weights of the
edges can be minimized.
Kruskal's algorithm - This algorithm is also used to find the minimum spanning tree for a
connected weighted graph. Kruskal's algorithm also follows greedy approach, which finds
an optimum solution at every stage instead of focusing on a global optimum.

Prim's Algorithm
In this article, we will discuss the prim's algorithm. Along with the algorithm, we will also
see the complexity, working, example, and implementation of prim's algorithm.

Before starting the main topic, we should discuss the basic and important terms such as
spanning tree and minimum spanning tree.

Spanning tree - A spanning tree is the subgraph of an undirected connected graph.

Minimum Spanning tree - Minimum spanning tree can be defined as the spanning tree in
which the sum of the weights of the edge is minimum. The weight of the spanning tree is
the sum of the weights given to the edges of the spanning tree.

Now, let's start the main topic.

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree
from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the
graph such that the sum of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in
the graph got selected.

How does the prim's algorithm work?

Prim's algorithm is a greedy algorithm that starts from one vertex and continue to add the
edges with the smallest weight until the goal is reached. The steps to implement the prim's
algorithm are given as follows -

o First, we have to initialize an MST with the randomly chosen vertex.

o Now, we have to find all the edges that connect the tree in the above step with
the new vertices. From the edges found, select the minimum edge and add it
to the tree.
o Repeat step 2 until the minimum spanning tree is formed.
The applications of prim's algorithm are -

o Prim's algorithm can be used in network designing.

o It can be used to make network cycles.
o It can also be used to lay down electrical wiring cables.
Example of prim's algorithm
Now, let's see the working of prim's algorithm using an example. It will be easier to
understand the prim's algorithm using an example.

Suppose, a weighted graph is -

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two
edges from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among
the edges, the edge BD has the minimum weight. So, add it to the MST.

Step 3 - Now, again, choose the edge with the minimum weight among all the other
edges. In this case, the edges DE and CD are such edges. Add them to MST and explore
the adjacent of C, i.e., E and A. So, select the edge DE and add it to the MST.
Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would
create a cycle to the graph. So, choose the edge CA and add it to the MST.

So, the graph produced in step 5 is the minimum spanning tree of the given graph. The
cost of the MST is given below -

Cost of MST = 4 + 2 + 1 + 3 = 10 units

Kruskal's Algorithm
In this article, we will discuss Kruskal's algorithm. Here, we will also see the complexity,
working, example, and implementation of the Kruskal's algorithm.

But before moving directly towards the algorithm, we should first understand the basic
terms such as spanning tree and minimum spanning tree.

Spanning tree - A spanning tree is the subgraph of an undirected connected graph.

Minimum Spanning tree - Minimum spanning tree can be defined as the spanning tree in
which the sum of the weights of the edge is minimum. The weight of the spanning tree is
the sum of the weights given to the edges of the spanning tree.

Now, let's start with the main topic.

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted
graph. The main target of the algorithm is to find the subset of edges by using which we
can traverse every vertex of the graph. It follows the greedy approach that finds an
optimum solution at every stage instead of focusing on a global optimum.
How does Kruskal's algorithm work?
In Kruskal's algorithm, we start from edges with the lowest weight and keep adding the
edges until the goal is reached. The steps to implement Kruskal's algorithm are listed as
follows -

o First, sort all the edges from low weight to high.

o Now, take the edge with the lowest weight and add it to the spanning tree. If
the edge to be added creates a cycle, then reject the edge.
o Continue to add the edges until we reach all vertices, and a minimum spanning
tree is created.
The applications of Kruskal's algorithm are -

o Kruskal's algorithm can be used to layout electrical wiring among cities.

o It can be used to lay down LAN connections.

Example of Kruskal's algorithm

Now, let's see the working of Kruskal's algorithm using an example. It will be easier to
understand Kruskal's algorithm using an example.

Suppose a weighted graph is -

The weight of the edges of the above graph is given in the below table -

Edge AB AC AD AE BC CD DE
Weight 1 7 10 5 3 4 2

Now, sort the edges given above in the ascending order of their weights.

Edge AB DE BC CD AE AC AD

Weight 1 2 3 4 5 7 10

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.
Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the
cycle, so discard it.

Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so
discard it.

Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so
discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using
Kruskal's algorithm is -

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Now, the number of edges in the above tree equals the number of vertices minus 1. So,
the algorithm stops here.