CSE 103 - Unit V- Graph

UNIT – 5

GRAPH

Graph is another important non-linear data structure. In tree Structure, there is a

hierarchical relationship between, parent and children that is one-to-many relationship.
In Graph, relationship is less restricted. Here, relationship is many-to-many

Application of Graph Structure in real world:-

™ Airlines
™ Source – destination network
™ Transportation problem

Graph Terminologies:

A graph has a set of vertices V, often labeled V1, V2 . . . etc and a set of edges E,
labeled e1, e2… Each edge is a pair (U,V) of vertices. In general, Graph G = (V, E) for
the graph with vertex set V and edge set E.
In applications, where pair (u, v) is distinct from pair (v, u) the graph is directed.
Otherwise the graph is undirected.

Prepared By M. Raja, CSE,KLU 1 

 CSE 103 - Unit V- Graph
Digraph:

A digraph is also called as directed graph. It is a graph G, Such that G=<V,E>,

where V is the set of ordered pair of elements from V.

V = {V1, V2, V3, V4}

E={(V1, V2),(V1, V3),(V2, V3),(V3, V4),(V4, V1)}

Here if an ordered pair (vi, vj) in E, then there is an

edge directed from vi to vj.

Undirected Graph:

The pair (Vi,Vj) is unordered, that is

(Vi,Vj) and (Vj,Vi) are the same edges.

Weighted Graph:

A graph (or digraph) is termed weighted graph if all the edges in it are labeled
with some weights

Prepared By M. Raja, CSE,KLU 2 

 CSE 103 - Unit V- Graph

Adjacent vertices:

A vertex Vi is adjacent to another vertex Vj if there is an edge from Vi to Vj.

Here, V2 is adjacent to V3 and V4.

Self loop:
If there is an edge, Whose starting and end vertices are the same, that is (Vi,Vi) is
an edge, then it is called a self loop.

Prepared By M. Raja, CSE,KLU 3 

 CSE 103 - Unit V- Graph

Parallel edges:-

If there is more than one edge between the same pair of vertices, then they are
known as parallel edges.

E.g.:- In above graph, V1 to V2 has Two parallel edges.

A graph which has either self loop or parallel edges or both is called multigraph.

Simple graph:

A graph (digraph) if it does not have any self loop or parallel edges is called
simple graph.

Complete graph:

A graph G is said to be complete if each vertex Vi is adjacent to every other are

edges from any vertex to all other vertices.

Prepared By M. Raja, CSE,KLU 4 

 CSE 103 - Unit V- Graph

Acyclic graph:

If there is a path containing one or more edges which starts from a vertex vi and
terminates into the same vertex then the path is known as a cycle.

If a graph does not have any cycle, then it is called acyclic graph.

Isolated vertex:

A vertex is isolated if there is no edge connected from any other vertex to the vertex

Prepared By M. Raja, CSE,KLU 5 

 CSE 103 - Unit V- Graph

Degree of vertex:

The number of edges connected with vertex vi is called the degree of vertex vi and

is denoted by degree (Vi).

For digraph, there are two degrees:

degree (Vi) = 3.
In degree of Vi = number of edges incident to Vi.
Out degree of Vi = number of edges emanating from Vi.

indegree (V1) = 1
Prepared By M. Raja, CSE,KLU 6 
 CSE 103 - Unit V- Graph

outdegree (V1) = 2
Representation of Graphs:-

1. Set representation
2. Linked representation
3. Matrix representation

Set representation:

V = {V1, V2, V3, V4, V5, V6, V7}

E = { (V1,V2),(V1,V3), (V2,V4), (V3,V4),(V2,V5), (V5,V7),
(V4,V7),(V6,V7),(V3,V6) }

Topological sorting:-

Topological sorting is an ordering of the vertices of a graph, Such that if there is a

path from U to V in the graph then U appears before V in the ordering. A simple

Prepared By M. Raja, CSE,KLU 7 

 CSE 103 - Unit V- Graph

algorithm to find a topological ordering is to find out any vertex with in degree zero, that
is, a vertex without any predecessor. We can then add this vertex in an ordering set
(initially which is empty) and remove it along with its edges from the graph. Then we
repeat the same strategy on the remaining graph until it is empty.

Example:
Given a graph G:
Visited vertices: V1, V2, V5, V7, V6, V4, V3.

Here V1has no incoming edges. Visit V1 first and remove all the edges connected to it.

Prepared By M. Raja, CSE,KLU 8 

 CSE 103 - Unit V- Graph

Here V2 has no in degree. Visit V2 next and remove all edged connected to V2.

Here V5 has no in degree. Visit V5 next.

Here V7 has no in degree. Visit V7 next

Prepared By M. Raja, CSE,KLU 9 

 CSE 103 - Unit V- Graph

Here V6 has no in degree. Visit V6 next.

V4 has no in degree. Visit V4 next.

V3 is visited finally.
Visited vertices: V1, V2, V5, V7, V6, V4, V3.

Minimum Spanning Tree:

It is related to weighted graph, where we find a spanning tree so that the sum of all
the weights of all the edges in the tree is minimum.

A Spanning Tree:

A Spanning Tree of a connected graph is its connected acyclic sub graph that
contains all the vertices of the graph
A Minimum Spanning Tree of a weighted connected graph is its spanning tree of
the smallest weight, where the weight of a tree is defined as the sum of the weights on all
its edges.
The minimum spanning tree problem is the problem of finding a minimum
spanning tree for a given weighted connected graph.
Consider a graph:
Prepared By M. Raja, CSE,KLU 10 
 CSE 103 - Unit V- Graph

The spanning Tree is:

Here T1 is the minimum spanning tree.

Drawback of Exhaustive Search Approach:-

1. The number of spanning trees grows exponentially with the graph size.
2. Generating all spanning trees for a given graph is not easy.
To overcome this drawback, we make use of some efficient algorithms such as

™ Prim’s algorithm
™ Kruskal’s algorithm
Prim’s Algorithm:

Consider the graph.

Prepared By M. Raja, CSE,KLU 11 

 CSE 103 - Unit V- Graph

Tree Remaining Vertices Illustration

Vertices

a(_,_) b(a , 3) , c( _ , ∞),

d( _ , ∞ ) , e(a , 6),
f(a,5)

b(a,3) c(b,1),d(_,∞)
e(a,6), f(b ,4)

Prepared By M. Raja, CSE,KLU 12 

 CSE 103 - Unit V- Graph

c(b,1) d ( c , 6 ) , e ( a , 6 ),
f(b,4)

f(b,4) d(f,5),e(f,2)

e(f,2)

Prepared By M. Raja, CSE,KLU 13 

 CSE 103 - Unit V- Graph

Minimum spanning tree:

According to prim’s algorithm, a minimum spanning tree grows in successive

stages: At any stage in the algorithm, we can see that we have a set of vertices that have
already been included in the tree, the test of the vertices have not.
The prim’s algorithm then finds a new vertex to add it to the tree by choosing the
edge <Vi,Vj>, the smallest among all edges, where Vi is in the tree and Vj is yet to be
included in the tree.
The algorithm starts by selecting vertex arbitrarily, and then in each stage, we add
an edge (by adding an associated vertex) to the tree.
Prim’s algorithm:-

//Input : A weighted connected graph G = (V,E)

//Output: ET, the set of edges composing a minimum spanning tree of G.
VT Å {V0}
ET Å
For iÅ1 to |V| -1 do
Find a minimum-weight edge e* = (v*, u*) among all the edges (v,u), such that v is in VT
and u is in V-VT.
Prepared By M. Raja, CSE,KLU 14 
 CSE 103 - Unit V- Graph

VT Å VT {u*}
ET Å ET {e*}
return ET

Example 2:

Kruskals algorithm:-

To obtain a minimum spanning tree of a graph, a novel approach was devised, by

J. B. Kruskal known as kruskals algorithm.
1. List all the edges of the graph G in the increasing order of weights.
2. Select the smallest edge from the list and add it into the spanning tree (initially it is
empty) if the inclusion of this edge does not make a cycle.
3. If the selected edge with smallest weight forms a cycle, remove it from the list.
4. Repeat steps 2-3 until the tree contains n-1 edges of list are empty.
5. If the tree T contains less than n-1 edges and the list is empty, no spanning tree is
possible for the graph, else return the minimum spanning tree T.

Consider the graph:

Prepared By M. Raja, CSE,KLU 15 

 CSE 103 - Unit V- Graph

Edge weight Action

(V1,V4) 1 Accepted
(V6,V7) 1 Accepted
(V1,V2) 2 Accepted
(V3,V4) 2 Accepted
(V2,V4) 3 Rejected
(V1,V3) 4 Rejected
(V4,V7) 4 Accepted
(V3,V6) 5 Rejected
(V5,V7) 6 Accepted
Minimum spanning tree is:

Prepared By M. Raja, CSE,KLU 16 

 CSE 103 - Unit V- Graph

Shortest path problem:-

This problem of a graph is about finding a path between two vertices in such a way
that this path will satisfy some criteria of optimization.

E.g. For non-weighted graph, the number of edges will be minimum and for a weighted
graph, the sum of weights on all its edges in the path will be minimum.

™ Dijkstra’s algorithm
™ Warshalls algorithm.
™ Floyd’s algorithm

Dijkstra’s Algorithm:- (Single source shortest path problem)

Here, there is a distinct vertex, called the source vertex and it requires to find the
shortest path from this source vertex to all other vertices.

It is a single- source shortest path problem: for a given vertex called the source in
a weighted connected graph, find shortest path to all its other vertices. The best-known
algorithm for the single – source shortest path problem called Dijkstra’s algorithm.

Prepared By M. Raja, CSE,KLU 17 

 CSE 103 - Unit V- Graph

Dijkstra’s algorithm finds shortest path to a graph’s vertices in order of their

distance from a given source. First, it finds the shortest path from the source to a vertex
nearest to it, then to a second nearest and so on. Dijkstra’s algorithm compares path
length and therefore must add edge weights.

Routine for Dijkstra’s algorithm:-

Void Dijkstra’s (Table T)
{
Vertex v,w;
for(i i)
{
V= smallest unknown distance vertex;
if(v==not a vertex)
break;
T[V].Known = True;
for each w adjacent to V
if(!T[w].known)
if(t[v].Dist + vw<T[w].Dist)
{
/* Update w*/
Decrease ( T[w].Dist to T[v].Dist + (vw);
T[w].path = v;
}
}
}

Prepared By M. Raja, CSE,KLU 18 

 CSE 103 - Unit V- Graph

Example 1:
Consider the graph:

Tree Remaining Illustration

vertices vertices

V1(- ,- ) V2 (V1, 2),

V3 ( - , - ),
V4 (V1, 1 ),
V5( - , ∞),
V6( - , ∞ ) ,
V7( - , ∞).

 
 

Prepared By M. Raja, CSE,KLU 19 

 CSE 103 - Unit V- Graph

V4(V1 , 1 ) V2( V1 , 2 ),
V3 ( V4 ,2+1 ),
V5(V4 , 2+1 ) ,
V6( V4 ,8+1)
V7(V4 , 1+4)

V2(V1 ,2) V3 (V4 ,2+1 ),

V5(V4 , 2+1 ),
V6( V4 ,8+1)
V7(V4 , 1+4)

 
 

V3(V4 , 3) V5(V4, 2+1)

V6(V3, 1+2+5)
V7(V4, 1+4)

 
 

Prepared By M. Raja, CSE,KLU 20 

 CSE 103 - Unit V- Graph

V5(V4 , 3) V6( V3, 1+2+5),  

 
V7(V4, 1+4)

V7(V4,5) V6(V7, 1+4+1)

V6(V7,6)

//…

Prepared By M. Raja, CSE,KLU 21 

 CSE 103 - Unit V- Graph

Operation on Graph:
Insertion:

a) To insert a vertex and hence establish connectivity with other vertices in the
existing graph.
b) To insert an edge between two vertices in the graph.

Deletion:

a) To delete a vertex from the graph.

b) To delete an edge from the graph.

Merging:

To merge two graphs G1 and G2 into a single graph.

Traversal:

To visit all the vertices in the graph.

The implementation of the above operation depends on the way a graph is being
represented. We will consider only the linked representation and matrix representation of
the graph.

Warshall’s algorithm:

This is a classical algorithm by which we can determine whether these is a path

from any vertex Vi to another vertex Vj either directly or through one or more
intermediate vertices. In other words, we can test the reach ability of all pairs of vertices
in a graph.
We can determine whether there is a path from any vertex vi to another vertex vj
either directly or through one or more intermediate vertices. First, we find the adjacency
matrix from the digraph. Then we compute path matrix.
Prepared By M. Raja, CSE,KLU 22 
 CSE 103 - Unit V- Graph

Consider the unweighted graph: Find its reach ability of all pair of vertices.

Solution:
First find its adjacency matrix.

Algorithm:

Warshall (A[1…….N,1……N])
R(0)Å A
for kÅ1 to n do
for iÅ1 to n do
for jÅ1 to n do

R(k)[i,j]Å R(k-1)[i,j] or R(k-1)[i,j] and R(k-1)[i,j]

return R(n)
Taking AND operation

R(0) =

Prepared By M. Raja, CSE,KLU 23 

 CSE 103 - Unit V- Graph

R(1) =

R(2) =

R(3) =

R(4) =

R(5) =
Prepared By M. Raja, CSE,KLU 24 
 CSE 103 - Unit V- Graph

R(6) =

Example 2:

0 1 0 0
0 0 0 1
Adjacency matrix =
0 0 0 0
1 0 1 0

0 1 0 0
0 0 0 1
R(0) =
0 0 0 0
1 0 1 0

Prepared By M. Raja, CSE,KLU 25 

 CSE 103 - Unit V- Graph

0 1 0 0
0 0 0 1
R(1) =
0 0 0 0
1 1 0

0 1 0
0 0 0 1
R(2) =
0 0 0 0
1 1 1

0 1 0 1
0 0 0 1
R(3) =
0 0 0 0
1 1 1 1

1 1 1 1
1 1 1 1
R(4) =
0 0 0 0
1 1 1 1

Floyd’s algorithm: - (All-pair shortest path problem)

• The path matrix obtained using warshall’s algorithm shows the presence or
absence of any path between a pair of vertices. It does not take into account, the
weights of edges.
• If weights are to be taken into account and if we are interested in the length of the
shortest path between any pair of vertices, then Floyd’s algorithm is used.
• The goal is to find the distances from each vertex to all other vertices.
• A Distance matrix D is a n-by-n matrix indicating the length of the shortest path in
a graph.
• The element dij in the ith row and the jth column of this matrix indicates the length
of the shortest path in a graph, from the ith vertex to the jth vertex.

Prepared By M. Raja, CSE,KLU 26 

 CSE 103 - Unit V- Graph

• Distance matrix can be computed using an algorithm called Floyd’s algorithm,

which is applicable to both undirected and directed weighted graphs provided that
they do not contain a cycle of a negative length.
Condition:

dij(k) = min{ dij(k-1), dik(k-1) + dkj(k-1)} for k≥1, dij(0) = wij

dij(0) = 0 for i=j.
ALGORITHM: Floyd (w [1….n, 1….n])
// Implements Floyd’s algorithm for the all-pairs shortest path problems.
// Input: The weight matrix of the shortest path’s length.
//output: The distance matrix of the shortes path’s length.

DÅW
for KÅ 1 to n do
for iÅ 1 to n do
for jÅ 1 to n do
D[i , j] Åmin {D[ i,j ] , D[ i,k ], D[ k,j ]}
return D
Example:

2
a  b

3  7
6 

c d
1

0 3
2 0
Distance matrix D =
7 0 1
6 0

Prepared By M. Raja, CSE,KLU 27 

 CSE 103 - Unit V- Graph

Perform ADD operation on row and column values to change the α Æ some
distance values. Moreover if possible change the values to small values.

0 3
2 0
D(0) =
7 0 1
6 0

0 3
2 0
D(1) =
7 0 1
6 0

0 3
2 0
D(2) =
7 0 1
6 0

0 3
2 0
D(3) =
7 0 1
6 0

In the below matrix the value 9 in row 3 is changed to 7 because there is a

path which has the distance 7

Prepared By M. Raja, CSE,KLU 28 

 CSE 103 - Unit V- Graph
0 3
2 0
D(4) =
7 0 1
6 0

Graph Traversal:

Traversing a graph means visiting all the vertices in the graph exactly once.
Several methods are known to traverse a graph systematically, out of them two methods
are accepted as standard. They are:

™ Depth first search (DFS)

™ Breach first search (BFS)

• Depth- first search traversal is similar to the in order traversal of a binary tree.
• Starting from a given node, this traversal visits all the nodes up to the deepest level
and so on.
• Another Standard graph traversal method is BFS. This traversal is very similar to the
level –by-level traversal of a tree. Here, any vertex in the level I will be visited only
after the visit of all the vertices in its preceding level, that is, at i-1. It is roughly
analogous to the preorder traversal of the tree.

Algorithm: DFS (V)

1. Push the starting vertex, V into the stack.

2. Repeat until the stack becomes empty:
a. Pop a vertex from the stack
b. Visit the popped vertex.

Prepared By M. Raja, CSE,KLU 29 

 CSE 103 - Unit V- Graph

c. Push all the unvisited vertices adjacent to the popped vertex into the
stack.

Prepared By M. Raja, CSE,KLU 30 

 CSE 103 - Unit V- Graph

Consider the graph:

• Push the starting vertexV1 into the stack

• Pop a vertex from stack
• Visit v1

• Push all unvisited vertices adjacent to V1 into the stack.

• Pop a vertex, V2 from the stack
• Visit V2

Prepared By M. Raja, CSE,KLU 31 

 CSE 103 - Unit V- Graph

• Push all unvisited vertices adjacent to V2 into all stacks.

• Pop a vertex, V6 from the stack.

• Visit V6
• Push all unvisited vertices adjacent to v6 into the stack.
• There are no unvisited vertices adjacent to V6
• Pop a vertex, V3 from the stack.

• Visit V3
• Push all unvisited vertices adjacent to V3 into the stack.
• Pop a vertex, V5 from the stack.

• Visit V5
• Push all unvisited vertices adjacent to V5 into the stack.
• There are no unvisited vertices adjacent to V5.
• Pop a vertex, V4 from the stack

Prepared By M. Raja, CSE,KLU 32 

 CSE 103 - Unit V- Graph

• Visit V4
• Push all unvisited vertices adjacent to V4 into the stack.
• There are no unvisited vertices adjacent toV4.
• The stack is now empty.
• Therefore traversal is complete and visited vertices are:
V1, V2, V6, V3, V5, V4.

Alogorithm:- BFS (V)

1. Visit the starting vertex, V and insert it into a queue.

2. Repeat step3 until the queue becomes empty.
3. Delete the front vertex from the queue, visit all its unvisited adjacent vertices, and
insert them into the queue.

Example:

Prepared By M. Raja, CSE,KLU 33 

 CSE 103 - Unit V- Graph

Visit V1:-
• Insert V1 into the queue.

• Remove a vertex V1 from the queue.

• Visit all unvisited vertices adjacent to V1 and insert them in queue.

• Remove a vertex V2 from the queue.

• Visit all unvisited vertices adjacent to V2 and insert them in the queue.

• Remove a vertex V4 from the queue.

Prepared By M. Raja, CSE,KLU 34 

 CSE 103 - Unit V- Graph

• Visit all unvisited vertices adjacent to V4 and insert them in the queue.

• Remove a vertex V3 from the queue.

• Visit all unvisited vertices adjacent to V3 and insert them in queue.

• But V3 does not have any unvisited adjacent vertices.
• Remove a vertex V6 from queue.

• Visit all unvisited vertices adjacent to V6 and insert them in the queue.V6 does not
have any unvisited adjacent vertices.
• Remove a vertex V5 from the queue.

• Visit all unvisited vertices adjacent to V5 and insert them in the queue.
• V5 does not have any unvisited adjacent vertices.

The queue is now empty. Therefore traversal is complete.

Visited vertices are:-
V1, V2, V4, V3, V6, V5.

Application of Depth-first search(DFS):

DFS is a generalization of preorder traversal. Starting at some vertex, V we
process V and then recursively traverse all vertices adjacent to V.
Template:
Void DFS(vertex V)
{
Prepared By M. Raja, CSE,KLU 35 
 CSE 103 - Unit V- Graph

Visited[v]=true;
For each w adjacent to V
If (| visited[w])
DFS(w):
}
If we perform this process we need to be careful to avoid cycles. To do this, when
we visit each node mark it as “visited” and recursively call DFS an all adjacent vertices
that are not already marked.
This DFS algorithm continues the procedure until there is no unmarked node found.
Undirected graph:

An undirected graph is connected if and only if a DFS starting from any node visits every
node.

Biconnectivity:

™ A connected undirected graph is biconnected if there are no vertices whose

removal disconnects the rest of the graph.
™ If the computer system is biconnected, user always have an alternate route for
some terminal is disrupted.
™ If a graph is not biconnected, the vertices whose removal would disconnect the
graph are known as articulation points.

Introduction to NP- Completeness:

™ Euler circuit problem, which finds a path that touches every edge exactly one, is
solvable in linear time.
™ Hamilton cycle problem ask for a simple cycle that contain every vertex. No linear
algorithm for this problem.
™ The single source unweighted problem for directed graph is also solvable in linear
time. No linear time algorithm for corresponding longest simple path problem.

Prepared By M. Raja, CSE,KLU 36 

 CSE 103 - Unit V- Graph

™ But there are no known algorithm that are guaranteed to run polynomial time
™ Some important problems that are roughly equivalent in complexity.
™ These problems form a class called NP – Complete problems.
™ NP stands for non deterministic polynomial time.
NP completes problems:

™ Among all the problems known to be in NP, there is a subset known as NP-
complete problems which contain hardest.
™ NP-complete problem has some property that any problem in NP can be
polynomially reduced to it.
Examples:

™ A problem P1 can be transformed to an instance of P2 as follows.

™ Provide mapping so that instance of P1 can be transformed into instance of P2
™ Solve P2 then map answer back to original.
Examples 2:
The number entered into packet calculation is decimal. These decimal no is
converted to binary to perform operation. Final result converted back to decimal for
display.

*******

Prepared By M. Raja, CSE,KLU 37