GRAPHS

Definition
A graph G is defined as an ordered set (V, E), where V(G) represents the set of vertices and E(G)
represents the edges that connect these vertices.

Figure shows a graph with V(G) = {A, B, C, D and E} and E(G) = {(A, B), (B, C), (A, D), (B,
D), (D, E), (C, E)}. Note that there are five vertices or nodes and six edges in the graph.

Graph Terminology
Vertex − Each node of the graph is represented as a vertex. In the following example, the
labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an
array as shown in the following image. Here A can be identified by index 0. B can be identified
using index 1 and so on.
Edge − Edge represents a path between two vertices or a line between two vertices. In the
following example, the lines from A to B, B to C, and so on represents edges. We can use a two-
dimensional array to represent an array as shown in the following image. Here AB can be
represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other
combinations as 0.
Adjacency − Two node or vertices are adjacent if they are connected to each other through an
edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
Path − Path represents a sequence of edges between the two vertices. In the following example,
ABCD represents a path from A to D.

DATA STRUCTURES - UNIT-V [R19] Page 1

Regular graph:-
It is a graph where each vertex has the same number of neighbors. That is, every node has the
same degree. A regular graph with vertices of degree k is called a k–regular graph or a regular
graph of degree k. Figure shows regular graphs.

Cycle:-
A path in which the first and the last vertices are same. A simple cycle has no repeated edges or
vertices (except the first and last vertices).

Connected graph:-
A graph is said to be connected if for any two vertices (u, v) in V there is a path from u to v.
That is to say that there are no isolated nodes in a connected graph. A connected graph that does
not have any cycle is called a tree. Therefore, a tree is treated as a special graph.

Complete graph:-
A graph G is said to be complete if all its nodes are fully connected. That is, there is a path from
one node to every other node in the graph.

Labelled graph or weighted graph:-

A graph is said to be labelled if every edge in the graph is assigned some data. In a weighted
graph, the edges of the graph are assigned some weight or length. The weight of an edge denoted
by w(e) is a positive value which indicates the cost of traversing the edge. Figure shows a
weighted graph.

DATA STRUCTURES - UNIT-V [R19] Page 2

Multi-graph A graph with multiple edges and/or loops is called a multi-graph. Figure shows a
multi-graph.

Size of a graph The size of a graph is the total number of edges in it.

TYPES OF GRAPES
Graphs are two types
i. Directed graph
ii. Un directed graph

i. Directed Graphs

A directed graph G, also known as a digraph, is a graph in which every edge has a direction
assigned to it. An edge of a directed graph is given as an ordered pair (u, v) of nodes in G.
For an edge (u, v),
a. The edge begins at u and terminates at v.
b. u is known as the origin or initial point of e. Correspondingly, v is known as the
destination or terminal point of e.
c. u is the predecessor of v. Correspondingly, v is the successor of u.
d. Nodes u and v are adjacent to each other.

Terminology of a Directed Graph

Out-degree of a node - The out-degree of a node u, written as outdeg(u), is the number of edges
that originate at u.

In-degree of a node - The in-degree of a node u, written as indeg(u), is the number of edges that
terminate at u.

DATA STRUCTURES - UNIT-V [R19] Page 3

Degree of a node - The degree of a node, written as deg(u), is equal to the sum of in-degree and
out-degree of that node. Therefore, deg(u) = indeg(u) + outdeg(u).

Isolated vertex - A vertex with degree zero. Such a vertex is not an end-point of any edge.

Pendant vertex - (also known as leaf vertex) A vertex with degree one.

Cut vertex - A vertex which when deleted would disconnect the remaining graph.

Source A node u is known as a source if it has a positive out-degree but a zero in-degree.

Sink A node u is known as a sink if it has a positive in-degree but a zero out-degree.

Reachability A node v is said to be reachable from node u, if and only if there exists a (directed)
path from node u to node v. you will observe that node D is reachable from node A.

Strongly connected directed graph A digraph is said to be strongly connected if and only if there
exists a path between every pair of nodes in G. That is, if there is a path from node u to v, then
there must be a path from node v to u.

ii. Un directed Graph

An undirected graph is a graph in which all the edges are bi-directional i.e. the edges do not
point in any specific direction.

DATA STRUCTURES - UNIT-V [R19] Page 4

Difference between graphs and trees

Graphs Trees

Graph is a non-linear data

Tree is a non-linear data structure.
1 structure.

It is a collection of
It is a collection of nodes and edges.
2 vertices/nodes and edges.

General trees consist of the nodes having any number

Each node can have any
of child nodes. But in case of binary trees every node
number of edges.
3 can have at the most two child nodes.

There is no unique node called

There is a unique node called root in trees.
4 root in graph.

5 A cycle can be formed. There will not be any cycle.

Applications: For finding

Applications: For game trees, decision trees, the tree is
shortest path in networking
used.
6 graph is used.

REPRESENTATION OF GRAPHS
There are three common ways of storing graphs in the computer’s memory. They are:
i. Sequential representation by using an adjacency matrix.
ii. Linked representation by using an adjacency list that stores the neighbors of a node using
a linked list.

Adjacency Matrix Representation

An adjacency matrix is used to represent which nodes are adjacent to one another. By definition,
two nodes are said to be adjacent if there is an edge connecting them. In a directed graph G, if
node v is adjacent to node u, then there is definitely an edge from u to v. That is, if v is adjacent
to u, we can get from u to v by traversing one edge. For any graph G having n nodes, the
adjacency matrix will have the dimension of nX n.

DATA STRUCTURES - UNIT-V [R19] Page 5

In an adjacency matrix, the rows and columns are labeled by graph vertices. An entry aij in the
adjacency matrix will contain 1, if vertices vi and vj are adjacent to each other. However, if the
nodes are not adjacent, a ij will be set to zero. Since an adjacency matrix contains only 0s and 1s,
it is called a bit matrix or a Boolean matrix. The entries in the matrix depend on the ordering of
the nodes in G. Therefore, a change in the order of nodes will result in a different adjacency
matrix. Figure shows some graphs and their corresponding adjacency matrices.

Adjacency List Representation

An adjacency list is another way in which graphs can be represented in the computer’s memory.
This structure consists of a list of all nodes in G. Furthermore, every node is in turn linked to its
own list that contains the names of all other nodes that are adjacent to it.
The key advantages of using an adjacency list are:
a. It is easy to follow and clearly shows the adjacent nodes of a particular node.
b. It is often used for storing graphs that have a small-to-moderate number of edges. That
is, an adjacency list is preferred for representing sparse graphs in the computer’s
memory; otherwise, an adjacency matrix is a good choice.
c. Adding new nodes in G is easy and straightforward when G is represented using an
adjacency list. Adding new nodes in an adjacency matrix is a difficult task, as the size of
the matrix needs to be changed and existing nodes may have to be reordered.

Consider the graph given in Fig., and see how its adjacency list is stored in the memory. For a
directed graph, the sum of the lengths of all adjacency lists is equal to the number of edges in G.
However, for an undirected graph, the sum of the lengths of all adjacency lists is equal to twice
the number of edges in G because an edge (u, v) means an edge from node u to v as well as an

DATA STRUCTURES - UNIT-V [R19] Page 6

edge from v to u. Adjacency lists can also be modified to store weighted graphs. Let us now see
an adjacency list for an undirected graph as well as a weighted graph.

GRAPH TRAVERSAL ALGORITHMS

In this section, we will discuss how to traverse graphs. By traversing a graph, we mean the
method of examining the nodes and edges of the graph. There are two standard methods of graph
traversal which we will discuss in this section. These two methods are:
1. Breadth-first search
2. Depth-first search

DATA STRUCTURES - UNIT-V [R19] Page 7

Breadth-First Search Algorithm

Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores
all the neighboring nodes. Then for each of those nearest nodes, explores their unexplored
neighbor nodes, and so on, until it finds the goal. That is, we start examining the node A and then
all the neighbors of A are examined. In the next step, we examine the neighbors of neighbors of
A, so on and so forth. This means that we need to track the neighbors of the node and guarantee
that every node in the graph is processed and no node is processed more than once. This is
accomplished by using a queue that will hold the nodes that are waiting for further processing
and a variable STATUS to represent the current state of the node.

Example :-

DATA STRUCTURES - UNIT-V [R19] Page 8

DATA STRUCTURES - UNIT-V [R19] Page 9
DATA STRUCTURES - UNIT-V [R19] Page 10
Depth-first Search Algorithm(DFS)

The depth-first search algorithm progresses by expanding the starting node of G and then going
deeper and deeper until the goal node is found, or until a node that has no children is
encountered. When a dead-end is reached, the algorithm backtracks, returning to the most recent
node that has not been completely explored.

In other words, depth-first search begins at a starting node A which becomes the current node.
Then, it examines each node N along a path P which begins at A. That is, we process a neighbor
of A, then a neighbour of neighbour of A, and so on. During the execution of the algorithm, if we
reach a path that has a node N that has already been processed, then we backtrack to the current
node. Otherwise, the unvisited (unprocessed) node becomes the current node. Depth-first search
are implemented by using stack.

DATA STRUCTURES - UNIT-V [R19] Page 11

Example:-

DATA STRUCTURES - UNIT-V [R19] Page 12

DATA STRUCTURES - UNIT-V [R19] Page 13
DATA STRUCTURES - UNIT-V [R19] Page 14
DATA STRUCTURES - UNIT-V [R19] Page 15
DATA STRUCTURES - UNIT-V [R19] Page 16
Algorithm for depth-first search

SHORTEST PATH ALGORITHMS

we will discuss three different algorithms to calculate the shortest path between the vertices of a
graph G. These algorithms include:
1. Minimum spanning tree
2. Dijkstra’s algorithm
3. Warshall’s algorithm
While the first two use an adjacency list to find the shortest path, Warshall’s algorithm uses an
adjacency matrix to do the same.

DATA STRUCTURES - UNIT-V [R19] Page 17

Minimum Spanning Trees

A spanning tree of a connected, undirected graph G is a sub-graph of G which is a tree that

connects all the vertices together. A graph G can have many different spanning trees. We can
assign weights to each edge (which is a number that represents how unfavorable the edge is), and
use it to assign a weight to a spanning tree by calculating the sum of the weights of the edges in
that spanning tree. A minimum spanning tree (MST) is defined as a spanning tree with weight
less than or equal to the weight of every other spanning tree. In other words, a minimum
spanning tree is a spanning tree that has weights associated with its edges, and the total weight of
the tree (the sum of the weights of its edges) is at a minimum.

Applications of Minimum Spanning Trees

1. MSTs are widely used for designing networks. For instance, people separated by varying
distances wish to be connected together through a telephone network. A minimum spanning tree
is used to determine the least costly paths with no cycles in this network, thereby providing a
connection that has the minimum cost involved.
2. MSTs are used to find airline routes. While the vertices in the graph denote cities, edges
represent the routes between these cities. No doubt, more the distance between the cities, higher
will be the amount charged. Therefore, MSTs are used to optimize airline routes by finding the
least costly path with no cycles.
3. MSTs are also used to find the cheapest way to connect terminals, such as cities, electronic
components or computers via roads, airlines, railways, wires or telephone lines.
4. MSTs are applied in routing algorithms for finding the most efficient path.

Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that is used to form a minimum spanning tree for a
connected weighted undirected graph. In other words, the algorithm builds a tree that includes
every vertex and a subset of the edges in such a way that the total weight of all the edges in the
tree is minimized. For this, the algorithm maintains three sets of vertices which can be given as
below:
Tree vertices - Vertices that are a part of the minimum spanning tree T.
Fringe vertices - Vertices that are currently not a part of T, but are adjacent to some tree vertex.
Unseen vertices - Vertices that are neither tree vertices nor fringe vertices fall under this
category.
Choose a starting vertex. Branch out from the starting vertex and during each iteration, select a
new vertex and an edge. Basically, during the each iteration of the algorithm, we have to select a
vertex from the fringe vertices in such a way that the edge connecting the tree vertex and the new
vertex has the minimum weight assigned to it. The running time of Prim’s algorithm can be
given as O(E log V) where E is the number of edges and V is the number of vertices in the graph .

DATA STRUCTURES - UNIT-V [R19] Page 18

Example:-
Construct a minimum spanning tree of the graph given in Fig.

Step 1 - Remove all loops and parallel edges

Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the
one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily
chosen, so any node can be the root node. One may wonder why any video can be a root node.
So the answer is, in the spanning tree all the nodes of a graph are included and because it is
connected then there must be at least one edge, which will join it to the rest of the tree.
Step 3 - Check outgoing edges and select the one with less cost
After choosing the root node S, we see that S, A and S, C are two edges with weight 7 and 8,
respectively. We choose the edge S,A as it is lesser than the other.

DATA STRUCTURES - UNIT-V [R19] Page 19

Now, the tree S-7-A is treated as one node and we check for all edges going out from it. We
select the one which has the lowest cost and include it in the tree.

After this step, S-7-A-3-C tree is formed. Now we'll again treat it as a node and will check all
the edges again. However, we will choose only the least cost edge. In this case, C-3-D is the
new edge, which is less than other edges' cost 8, 6, 4, etc.

After adding node D to the spanning tree, we now have two edges going out of it having the
same cost, i.e. D-2-T and D-2-B. Thus, we can add either one. But the next step will again yield
edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included.

DATA STRUCTURES - UNIT-V [R19] Page 20

We may find that the output spanning tree of the same graph using two different algorithms is
same.

Kruskal’s Algorithm

Kruskal’s algorithm is used to find the minimum spanning tree for a connected weighted graph.
The algorithm aims to find a subset of the edges that forms a tree that includes every vertex. The
total weight of all the edges in the tree is minimized. However, if the graph is not connected,
then it finds a minimum spanning forest. Note that a forest is a collection of trees. Similarly, a
minimum spanning forest is a collection of minimum spanning trees. Kruskal’s algorithm is an
example of a greedy algorithm, as it makes the locally optimal choice at each stage with the hope
of finding the global optimum.

DATA STRUCTURES - UNIT-V [R19] Page 21

To understand Kruskal's algorithm let us consider the following example –

Step 1 - Remove all loops and Parallel Edges

Remove all loops and parallel edges from the given graph.

In case of parallel edges, keep the one which has the least cost associated and remove all others.

DATA STRUCTURES - UNIT-V [R19] Page 22

Step 2 - Arrange all edges in their increasing order of weight
The next step is to create a set of edges and weight, and arrange them in an ascending order of
weightage (cost).

Step 3 - Add the edge which has the least weight age
Now we start adding edges to the graph beginning from the one which has the least weight.
Throughout, we shall keep checking that the spanning properties remain intact. In case, by
adding one edge, the spanning tree property does not hold then we shall consider not to include
the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them. Adding them does not
violate spanning tree properties, so we continue to our next edge selection.
Next cost is 3, and associated edges are A,C and C,D. We add them again −

DATA STRUCTURES - UNIT-V [R19] Page 23

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. −

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7
and 8, we shall add the edge with cost 7.

By adding edge S,A we have included all the nodes of the graph and we now have minimum
cost spanning tree.

DATA STRUCTURES - UNIT-V [R19] Page 24

Kruskal’s algorithm

Dijkstra’s Algorithm

Dijkstra’s algorithm, given by a Dutch scientist Edsger Dijkstra in 1959, is used to find the
shortest path tree. Given a graph G and a source node A, the algorithm is used to find the
shortest path (one having the lowest cost) between A (source node) and every other node.
Moreover, Dijkstra’s algorithm is also used for finding the costs of the shortest paths from a
source node to a destination node.

For example, if we draw a graph in which nodes represent the cities and weighted edges
represent the driving distances between pairs of cities connected by a direct road, then Dijkstra’s
algorithm when applied gives the shortest route between one city and all other cities.
Algorithm
Dijkstra’s algorithm is used to find the length of an optimal path between two nodes in a graph.
The term optimal can mean anything, shortest, cheapest, or fastest. If we start the algorithm with
an initial node, then the distance of a node Y can be given as the distance from the initial node to
that node.
Dijkstra’s algorithm labels every node in the graph where the labels represent the distance (cost)
from the source node to that node. There are two kinds of labels: temporary and permanent.
Temporary labels are assigned to nodes that have not been reached, while permanent labels are
given to nodes that have been reached and their distance (cost) to the source node is known. A
node must be a permanent label or a temporary label, but not both.

DATA STRUCTURES - UNIT-V [R19] Page 25

The execution of this algorithm will produce either of the following two results:
1. If the destination node is labelled, then the label will in turn represent the distance from the
source node to the destination node.
2. If the destination node is not labelled, then there is no path from the source to the destination
node.

Example
Consider the graph G given in Fig.

Taking D as the initial node, execute the Dijkstra’s algorithm on it.

Step 1: Set the label of D = 0 and N = {D}.
Step 2: Label of D = 0, B = 15, G = 23, and F = 5. Therefore, N = {D, F}.
Step 3: Label of D = 0, B = 15, G has been re-labelled 18 because minimum (5 + 13, 23) = 18, C
has been re-labelled 14 (5 + 9). Therefore, N = {D,F, C}.
Step 4: Label of D = 0, B = 15, G = 18. Therefore, N = {D, F, C, B}.
Step 5: Label of D = 0, B = 15, G = 18 and A = 19 (15 + 4). Therefore, N ={D, F, C, B, G}.
Step 6: Label of D = 0 and A = 19. Therefore, N = {D, F, C, B, G, A}
Note that we have no labels for node E; this means that E is not reachable from D. Only the
nodes that are in N are reachable from B. The running time of Dijkstra’s algorithm can be given
as O(|V|2+|E|)=O(|V|2) where V is the set of vertices and E in the graph.

DATA STRUCTURES - UNIT-V [R19] Page 26

Dijkstra’s algorithm

Warshall’s Algorithm

If a graph G is given as G=(V, E), where V is the set of vertices and E is the set of edges, the
path matrix of G can be found as, P = A + A2 + A3 + ... + An. This is a lengthy process, so
Warshall has given a very efficient algorithm to calculate the path matrix. Warshall’s algorithm
defines matrices P0, P1, P2, - - -, Pn as given in Fig.

This means that if P0[i][j] = 1, then there exists an edge from node vi to vj. If P1[i][j] = 1, then
there exists an edge from vi to vj that does not use any other vertex except v1. If P2[i][j] = 1, then
there exists an edge from vi to vj that does not use any other vertex except v1 and v2.
Note that P0 is equal to the adjacency matrix of G. If G contains n nodes, then Pn = P which is
the path matrix of the graph G. From the above discussion, we can conclude that Pk[i][j] is equal
to 1 only when either of the two following cases occur:
Rule 1:- If an element in row i and column j is 1 in R(k-1) , it remains 1 in R(k)
Rule 2:- If an element in row i and column j is 0 in R(k-1) , it has to be changed to 1 in R(k) it has
to be changed to 1 in R if and only if (k) if and only if the element in its row i and column k and
the element in its column j and row k are both 1’s in R(k-1)

DATA STRUCTURES - UNIT-V [R19] Page 27

Hence, the path matrix Pn can be calculated with the formula given as:

Pk[i][j] = Pk–1[i][j] V (Pk–1[i][k] L Pk–1[k][j])

Where V indicates logical OR operation and L indicates logical AND operation.

Warshall’s algorithm

DATA STRUCTURES - UNIT-V [R19] Page 28

Example: - Consider the graph

Solution:-

The adjacency matrix for the above graph is

Step 1 :- Calculate T1 by using To

At k = 1, i = 1,j = 1

T111 =T011 V [ T011 ^ T011]

= 0 V [0 ^0 ] =0

At k = 1, I = 1, j = 2

T112 =T012 V [ T011 ^ T012]

= 1 V [0 ^1 ] = 1

At k = 1, i = 1, j = 3

T113 =T013 V [ T011 ^ T013]

=0V[0^0] =0

DATA STRUCTURES - UNIT-V [R19] Page 29

At k = 1, i = 2, j = 1

T121 =T021 V [ T021 ^ T011]

= 0 V [0 ^ 0 ] = 0

At k = 1, i = 2, j = 2

T122 =T022 V [ T021 ^ T012]

= 0 V [0 ^1 ] = 0

At k = 1, i = 2, j = 3

T123 =T023 V [ T021 ^ T013]

=1V[0^0] =1

At k = 1, i = 3, j = 1

T131 =T031 V [ T031 ^ T011]

= 1 V [1 ^0 ] = 1

At k = 1, i = 3, j = 2

T132 =T032 V [ T031 ^ T012]

= 0 V [1 ^1 ] = 1

At k = 1, i = 3, j = 3

T133 =T033 V [ T031 ^ T013]

=0V[1^0] =0

DATA STRUCTURES - UNIT-V [R19] Page 30

Step 2 :- Calculate T2 by using T1

At k = 2, i = 1, j = 1

T211 =T111 V [ T112 ^ T121]

= 0 V [1 ^0 ] = 0

At k = 2, i = 1, j = 2

T212 =T112 V [ T112 ^ T122]

=1V[1^0]=1

At k = 2, i = 1,j = 3

T213 =T113 V [ T112 ^ T123]

=0V[1^1]=1

At k = 2, i = 2, j = 1

T221 =T121 V [ T122 ^ T121]

=0V[0^0]=0

At k = 2, i = 2, j = 2

T222 =T122 V [ T122 ^ T122]

=0V[0^0]=0

At k = 2, i = 2, j = 3

T223 =T123 V [ T122 ^ T123]

=1V[0^1]=1

At k = 2, i = 3, j = 1

T231 =T131 V [ T132 ^ T121]

= 1 V [ 1 ^0 ] = 1

At k = 2, i = 3, j = 2

T232 =T132 V [ T132 ^ T122]

=1V[1^0]=1

DATA STRUCTURES - UNIT-V [R19] Page 31

At k = 2, i = 3, j = 3

T233 =T133 V [ T132 ^ T123]

=0V[1^1]=1

Step 3 :- Calculate T3 by using T2

At k = 3, i = 1, j = 1

T311 =T211 V [ T213 ^ T231]

= 1 V [ 1 ^1 ] = 1

At k = 3, i = 1, j = 2

T312 =T212 V [ T213 ^ T232]

= 1 V [ 1 ^1 ] = 1

At k = 3, I = 1, j = 3

T313 =T213 V [ T213 ^ T233]

=1V[1^1]=1

At k = 3, i = 2, j = 1

T321 =T221 V [ T223 ^ T231]

= 0 V [ 1 ^1 ] = 1

DATA STRUCTURES - UNIT-V [R19] Page 32

At k = 3, i = 2, j = 2

T322 =T222 V [ T223 ^ T232]

= 0 V [ 1 ^1 ] = 1

At k = 3, i = 2, j = 3

T323 =T223 V [ T223 ^ T233]

=1V[1^1] =1

At k = 3, i = 3, j = 1

T331 =T231 V [ T233 ^ T231]

= 1 V [ 1 ^1 ] = 1

At k = 1, i = 3, j = 2

T332 =T232 V [ T333 ^ T232]

= 1 V [ 1 ^1 ] = 1

At k = 3, i = 3, j = 3

T333 =T233 V [ T233 ^ T233]

=1V[1^1] =1

DATA STRUCTURES - UNIT-V [R19] Page 33