UNIT: IV GRAPHS

Graph: A graph G is a defined as a set of objects called nodes and edges.

G= (V, E) , Where V is a finite and non empty set at vertices.
E is a set of pairs of vertices called edges. Each edge ‘e’ in E is identified with a unique
pair (a, b) of nodes in V, denoted by e = [a, b].
Example:

Consider the above graph ‘G’. Then the vertex V and edge E can be represented as:

Vertex V = {v1, v2, v3, v4, v5, v6}

E = {e1, e2, e3, e4, e5, e6}
E = {(v1, v2) (v2, v3) (v1, v3) (v3, v4), (v3, v5) (v5, v6)}.
There are six edges and vertex in the graph
Node: A node is a data element of the graph.
Edge: An edge is a path between two nodes.

TYPES OF GRAPH

There are two types of graph. They are

1. Undirected graph
2. Directed graph
Undirected graph: An undirected graph is a graph in which the edges are not directionally
oriented towards a node.
Directed graph: A Directed graph or a Digraph is a graph in which the edges are directionally
oriented towards any node.
Weighted and Unweighted
Graphs can be classified by whether or not their edges have weights.
Weighted graph: Edges have a weight
 Weight typically shows cost of traversing.
 Example: weights are distances between cities
Unweighted graph: Edges have no weight
 Edges simply show connections

Example:

Distance between 1 and 4 is 5.

Distance between 3 and 5 is 34
BASIC TERMINOLOGIES
Arc: The directed edge in a directed graph is called an arc.

Strongly connected graph: A directed graph is called strongly connected if there is a directed
path from any vertex to any other vertex
Example:

In the above graph we have path from any vertex to any other vertex
Weakly connected graph: A Directed graph is called a weakly connected graph if for any two
nodes I and J, there is a directed path from I to J or from J to I.
Example:

Out degree: The number of arcs exiting from the node is called out degree of that node.
In degree: The number of arcs entering the node is called in degree of that node.
Example:

Nodes Indegree OutDegree

A 0 3
B 1 1
C 1 1
D 3 0
Source node: A node where the indegree is 0 but has a positive value for outdegree is called a
source node. That is there are only outgoing arcs to the node and no incoming arcs to the node.

Example:

Node ‘A’ is the source node.

Sink node: A node where the outdegree is 0 and has a positive value for indegree is called the
sink node. That is there is only incoming arcs to the node and no outgoing arcs the node.

Example:

Node ‘D’ is the Sink node.

Cycle: A cycle in a directed graph is a directed path that originates and terminates at the same
node ie some number of vertices connected in a closed chain.

Example:

This graph contains three cycles 0->2->0, 0->1->2->0 and 3->3,

Degree of a node: In an undirected graph, the degree of a node is the number of edges
connected directly to the node.

Length of the path: The length of the path between node I and K is the number of edges
between them in a path from I to K.

Degree: The degree of the node B in the undirected graph shown above is 3.

REPRESENTATION OF GRAPHS

There are two possible ways by which the graph can be represented.

1. Matrix representation (Array Representation)

2. Linked representation
The graphs can be represented using Adjacency matrix or otherwise called the
incidence matrix. Since the matrix is so sparse it is also called as sparse matrix.
 The adjacency matrix is a N X N matrix where N is the number of nodes in the graph.
Each entry (I, J) in the matrix has either 1 or 0. An entry 1 indicates that there is a direct
connection from I to J. An entry 0 indicates that there is no direct connection from I to J.

If an adjacency matrix is written for the above directed graph as shown:

Adjacency Matrix Representation

Since the matrix is so sparse in nature the second method of representation will be
preferred if the number of edges is very less compared to the number of vertices.
Adjacency List:
An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be
array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This
representation can also be used to represent a weighted graph. The weights of edges can be
stored in nodes of linked lists. Following is adjacency list representation of the above graph.

Adjacency List Representation of the above Graph

GRAPH TRAVERSALS
There are two methods for traversing through the nodes of the graph. They are:
(1) Breadth First Search Traversal (BFS)
(2) Depth First Search Traversal (DFS)
Breadth First Search Traversal (BFS)
As the name implies, this method traverses the nodes of the graph by searching through
the nodes breadth-wise. Initially let the first node of the graph be visited. This node is now
considered as node u. Now find out all the nodes which are adjacent to this node. Let all the
adjacent nodes be called as w. Add the node u to a queue. Now every time an adjacent node w is
visited, it is added to the queue. One by one all the adjacent nodes w are visited and added to the
queue. When all the unvisited adjacent nodes are visited, then the node u is deleted from the
queue and hence the next element in the queue now becomes the new node u. The process is
repeated on this new node u. This is continued till all the nodes are visited.
The Breadth First Traversal (BFT) algorithm calls the BFS algorithm on all the nodes.
Algorithm
BFT(G, n)
Repeat for i = 1 to n
Visited[i] = 0
End Repeat
Repeat for i = 1 to n
If visited[i] = 0
BFS(i)
End if
End Repeat

BFS(v)
u=v
visited[v] = 1
Repeat while(true)
Repeat for all vertices w adjacent to u
If visited[w] = 0
Add w to queue
Visited[w] = 1
End if
End Repeat
If queue is empty
Return
End if
Delete u from queue
End while
End BFS
Now the following diagrams illustrate the BFS on a directed graph.
Depth First Search Traversal (DFS)
In the Depth First Search Traversal, as the name implies the nodes of the graph are
traversed by searching through all the nodes by first going to the depth of the graph. The first
node is visited first. Let this be node u. Find out all the adjacent nodes of u. Let that be w.
Apply the DFS on the first adjacent node recursively. Since a recursive approach is followed,
the nodes are traversed by going to the depth of the graph first. The DFT algorithm calls the
DFS algorithm repeatedly for all the nodes in the graph.
Algorithm

DFT(G, n)
Repeat for i = 1 to n
Visited[i] = 0
End Repeat
Repeat for i = 1 to n
If visited[i] = 0
DFS(i)
End if
End Repeat

DFS(v)
Visited[v] = 1
Repeat for each vertex w adjacent from v
If visited[w] = 0
DFS(w)
End if
End for
Now the following diagrams illustrate the DFS on a directed graph.
Applications of depth First Traversal
Depth-first search (DFS) is an algorithm (or technique) for traversing a graph.
1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all
pair shortest path tree.
2) Detecting cycle in a graph : A graph has cycle if and only if we see a back edge during DFS. So
we can run DFS for the graph and check for back edges.
3) Path Finding:
We can specialize the DFS algorithm to find a path between two given vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack
4) Topological Sorting
Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In
computer science, applications of this type arise in instruction scheduling, ordering of formula cell
evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order
of compilation tasks to perform in make files, data serialization, and resolving symbol dependencies
in linkers .
5) Finding Strongly Connected Components of a graph A directed graph is called strongly
connected if there is a path from each vertex in the graph to every other vertex.
6) Solving puzzles with only one solution, such as mazes. DFS can be adapted to find all solutions
to a maze by only including nodes on the current path in the visited set.
Applications of Breadth First Traversal
1) Shortest Path and Minimum Spanning Tree for unweighted graph In unweighted graph, the
shortest path is the path with least number of edges. With Breadth First, we always reach a vertex
from given source using minimum number of edges. Also, in case of unweighted graphs, any
spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for
finding a spanning tree.
2) Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth First Search is used to
find all neighbor nodes.
3) Crawlers in Search Engines: Crawlers build index using Breadth First. The idea is to start from
source page and follow all links from source and keep doing same. Depth First Traversal can also be
used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of built tree
can be limited.
4) Social Networking Websites: In social networks, we can find people within a given distance ‘k’
from a person using Breadth First Search till ‘k’ levels.
5) GPS Navigation systems: Breadth First Search is used to find all neighboring locations.
MINIMUM SPANNING TREES

Weight of an edge: Weight of an edge is just of the value of the edge or the cost of the edge.
For example, a graph representing cities, has the distance between two cites as the edge cost or
its weight.
Network: A graph with weighted edges is called a network.
Spanning Tree: Any tree consisting of edges in the graph G and including all vertices in G is
called a spanning tree.
Given a network, we should try to connect all the nodes in the nodes in the graph with
minimum number of edges, such that the total weight is minimized. To solve this problem, we
shall devise an algorithm that converts a network into to tree structures called the minimum
spanning tree of the network.
Given a network, the edges for the minimum spanning tree are chosen in such a way that:
(1) Every node in the network must be included in the spanning tree.
(2) The overall edge weight of the spanning tree is the minimum possible that will allow
the existence of a path between any 2 nodes in the tree.
The two algorithms which are used for finding the minimum spanning tree for a graph are:
1. Kruskal’s Algorithm
2. Prim’s Algorithm
3. Sollin’s Algorithm

KRUSKAL’S ALGORITHM

The Kruskal’s algorithm follows greedy approach. At every stage of the solution, it takes
that edge which has the minimum cost and builds the minimum spanning tree.
Example:

Consider the above graph. Now let us apply the Kruskal’s

algorithm to construct a minimum spanning tree.
Step 1:
Construct a queue with the cost of edges, such that the edges are placed in the queue in
the ascending order of the cost as shown.
Queue of edge costs
10 12 14 16 18 22 24 26 28
Step 2:
Create N sets each consisting one node. N is the number of nodes in the graph. Then for
the above problem, the sets which will be created are
S1 = {1}
S2 = {2}
S3 = {3}
S4 = {4}
S5 = {5}
S6 = {6}
S7 = {7}
Step 3:
Delete a cost from the queue. Let the nodes associated with that edge be (u,v). Now, 10
is deleted first from the queue. The nodes associated with 10 is (u,v) = (1,6). Check if u and v
belong to the same set or different set. If they belong to the different set then enter that into the
output matrix as shown. Since 1 belongs to S1 and 6 belong to S6, they can be entered into the T
matrix. If the nodes belong to the same set, then entering them into the matrix will give an
output which may form a cycle. Hence that is avoided. The T matrix has n-1 rows and 2
columns.
T matrix
u v
1 1 6
2
3
4
5
6

After entering them in the T matrix, the sets S1 and S6 are merged.
S8 = {1, 6}

The above process in step 3 is repeated till the queue becomes empty. The solution is derived as
shown.
Queue of edge costs
 12 14 16 18 22 24 26 28
Delete 12 from the queue. The nodes associated with 12 are (u,v) = (3,4). The node 3
belongs to S3 and node 4 belongs to S4. As they are in different sets, they are entered in the T
matrix.
T matrix
u v
1 1 6
2 3 4
3
4
5
6
The sets S3 and S4 are merged.
S9 = {3, 4}
Queue of edge costs

14 16 18 22 24 26 28
Delete 14 from the queue. The (u,v) = (2,7). 2 belong to S2 and 7 belong to S7. As they belong
to different sets, they are entered into the T matrix and the sets S2 and S7 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4
5
6
S10 = {2, 7}
Queue of edge costs
16 18 22 24 26 28

Delete 16 from the queue. The (u,v) = (2,3). 2 belong to S10 and 3 belong to S9. As they are
from different sets, they are entered into the T matrix. The sets S9 and S10 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5
6
S11 = {2, 3, 4, 7}
Queue of edge costs
18 22 24 26 28
Delete 18. The (u, v) = (4, 7). 4 and 7 belong to same set S11. Hence they are not entered into
the T matrix.
Queue of edge costs
22 24 26 28
Delete 22. The (u,v) = (4, 5). 4 belong to S11 and 5 belong to S5. As they belong to different
set, they are entered into the T matrix. The sets S11 and S5 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5 4 5
6
S12 = {2, 3, 4, 5, 7}
Queue of edge costs
24 26 28
Delete 24. (u, v) = (5, 7). Both 5 and 7 belong to S12. Hence they are not entered into the T
matrix.
26 28
Delete 26. (u, v) = (5, 6). 5 belong to S12 and 6 belong to S8. As they are from different set,
they are entered into the T matrix.

T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5 4 5
 6 5 6
S13 = {1, 2, 3, 4, 5, 6, 7}
As all T matrix is completely filled, the algorithm comes to an end.
Step 4:
Using the edges in the T matrix connect the nodes of the graph. The resulting tree is the
required minimum spanning tree.

Algorithm
KRUSKAL(E, cost, n, t)
Construct a queue with edge costs such that they are in ascending order
 i = 0, mincost = 0
while i < n – 1 and queue is not empty
Delete minimum cost edge (u, v) from queue
j = Find(u), k = Find(v)
If j ≠ k
i=i+1
t[i, 1] = u, t[i, 2] = v
mincost = mincost + cost[u, v]
Union(j, k)
End if
End while
If i ≠ n – 1
Print “No spanning tree”
Else
Return mincost
End if
End KRUSKAL

PRIM’S ALGORITHM
The other popular algorithm used for constructing the minimum spanning tree is the
Prim’s algorithm, which also follows the greedy approach. We can consider the same example
as above and solve it using Prim’s algorithm.
Example:

Cost Matrix is
1 2 3 4 5 6 7
1 0 28 ∞ ∞ ∞ 10 ∞
2 28 0 16 ∞ ∞ ∞ 14
3 ∞ 16 0 12 ∞ ∞ ∞
4 ∞ ∞ 12 0 22 ∞ 18
5 ∞ ∞ ∞ 22 0 26 24
6 10 26 ∞ ∞ ∞ 0 ∞
7 ∞ 14 ∞ 18 24 ∞ 0

Step 1:
Select the least cost edge from the graph and enter into the T matrix. The least cost edge
is (1, 6) with cost 10.
T matrix
u v
1 1 6
2
3
4
5
6
Let us consider an array NEAR[ ], which is filled as follows:
If cost[i, l] < cost[i, k]
Near[i] = l
Else
Near[i] = k

In the first iteration i = 1 and (k, l) = (1, 6). Using the above condition the NEAR array is filled
as follows.
NEAR

1 1
2 1
3 1
4 1
5 6
6 6
7 1

Step 2:
 Make the entries in the NEAR array corresponding to 1 and 6 as 0. For all non-zero
entries in the near array, find out the cost[j][near[j]]. Select the minimum among these costs and
enter the corresponding nodes into the T matrix.
NEAR

1 0
2 1 28
3 1 ∞
4 1 ∞
5 6 26
6 0
7 1 ∞
Among the costs, 26 is minimum. Hence (5, 6) is entered into the T matrix. The corresponding
entry into the NEAR array is made 0.
T matrix
u v
1 1 6
2 5 6
3
4
5
6

Step 3:
Now in every iteration the NEAR array is updated using the following condition and
procedure in step 2 is followed to fill up the T matrix. The solution is as follows:
If Near[k] ≠ 0 and cost[k, Near[k]] > cost[k, j]
Near[k] = j
Updated NEAR

1 0
2 1 28
3 1 ∞
4 5 22
J= 0
56 0
7 5 24
 Among the cost computed, 22 is minimum and hence (4,5) is selected as the minimum edge.
T matrix
u v
1 1 6
2 5 6
3 4 5
4
5
6
Updated NEAR

1 0
2 1 28
3 4 12
J= 0
45 0
6 0
7 4 18
Among the cost computed, 12 is minimum and hence (3, 4) is selected as the minimum edge.
T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5
6
Updated NEAR

1 0
2 3 16
J= 0
34 0
5 0
6 0
7 4 18

Among the cost computed, 16 is minimum and hence (2, 3) is selected as the minimum edge.
 T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5 2 3
6

Updated NEAR

1 0
J=2 3 0
4 0
5 0
6 0
7 0 14
2
The last edge (7, 2) is selected and entered into the T matrix.
T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5 2 3
6 7 2

Step 4:
Now using the edges in the T matrix connect the nodes in the graph. The resulting tree is
the minimum spanning tree.
Algorithm

PRIM(E, cost, n, t)
Let (k, L) be an edge of minimum cost in E
mincost = cost[k, L]
t[1, 1] = k, t[1, 2] =L
For i = 1 to n
If cost[i, L] < cost[i, k]
Near[i] = L
Else
Near[i] = k
End if
End for
Near[k] = Near[L] = 0
For i = 2 to n -1
Let j be an index such that near[j] ≠ 0 and cost[j, near[j]] is minimum
T[i, 1] = j, t[i, 2] = Near[j]
 mincost = mincost + cost[j, near[j]]
Near[j] = 0
For k = 1 to n
If Near[k] ≠ 0 and cost[k, Near[k]] > cost[k, j]
Near[k] = j
End if
End for
Return mincost
End PRIM

SHORTEST PATH USING DJIKSTRA’S ALGORITHM

The Djikstra’s algorithm finds out the shortest path between the single source and every
other node in the graph. For example consider the following graph. Let the node 5 be the
source. Let solve this using Djiksta’s algorithm to find the shortest paths between 5 and every
other node in the graph.

A Distance array Dist[] is initially filled with infinity. The entry corresponding to the source
node 5 alone is made 0. Now find out the adjacent nodes of 5 and update their values using the
cost matrix. In the next iteration the node with minimum distance is the vertex selected and
again the above process is repeated. The Column S shows the set of vertices already selected. In
every iteration the node with minimum distance and which is not yet selected is taken as the new
vertex.
The solution is obtained as follows.

Iteration S Vertex Dist[ ]

Selected 1 2 3 4 5 6 7 8
 Initial - - ∞ ∞ ∞ 1500 0 250 ∞ ∞
5 6 ∞ ∞ ∞ 1250 0 250 1150 1650
5,6 7 ∞ ∞ ∞ 1250 0 250 1150 1650
5,6,7 4 ∞ ∞ 2450 1250 0 250 1150 1650
5,6,7,4 8 3350 ∞ 2450 1250 0 250 1150 1650
5,6,7,4,8 3 3350 3250 2450 1250 0 250 1150 1650
5,6,7,4,8,3 2 3350 3250 2450 1250 0 250 1150 1650
Now we can see that the values in the last row, gives the distance of the shortest path between
the source node 5 and every other node in the graph.

The shortest paths corresponding to this can also be generated. The paths are represented using
linked lists. Whenever a value in the distance array is updated, the shortest path linked lists are
also adjusted.
The shortest paths are represented using linked lists as shown.

Algorithm

DJIKSTRA(v, cost, dist, n)

For i = 1 to n
S[i] = false
Dist[i] = ∞
End for
S[v] = true
 Dist[v] = 0
Create n lists each beginning with v
For num = 1 to n – 1
Choose u from among those vertices not in S such that dis[u] is minimum
S[u] = true
For each w adjacent to u with s[w] = false
If Dist[w] > Dist[u] + cost[u, w]
Dist[w] = Dist[u] + cost [u, w]
List[w] = List[u] + w
End if
End for
End for

THE BELLMAN-FORD SHORTEST PATH ALGORITHM

Given a weighted graph G and a source vertex s, Bellman-Ford algorithm finds the
shortest (minimum cost) path from s to every other vertex in G. The weighted path length (cost)
is the sum of the weights of all links on the path.

.
 Initialisation After Pass1

After Pass 2 After Pass3

 After Pass 4

The order of edges examined in each pass:

(t, x), (t, z), (x, t), (y, x), (y, t), (y, z), (z, x), (z, s), (s, t), (s, y)

Algorithm

Bellman-Ford(G, w, s)
1. Initialize-Single-Source(G, s)
2. for i := 1 to |V| - 1 do
3. for each edge (u, v)  E do
4. Relax(u, v, w)
5. for each vertex v  u.adj do
6. if d[v] > d[u] + w(u,
7. v) // there is a negative cycle
8. then return False
return True
Relax(u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] := d[u] + w(u, v)
parent[v] := u

Difference between Djikstra’s and Bellman Ford Algorithm

Sl.No Djikstra’s Algorithm Bellman Ford Algorithm
1 It doesn’t work for Negative Link It works for Negative Link weight
weight
 2 It cann’t be implemented in a It can be easily implemented in a distributed
distributed way way
3 It has less time complexity It has higher time complexity

FLOYD WARSHALL ALGORITHM

The All pairs shortest path algorithm is used to find the shortest path between every pair of nodes
in the graph. Consider the following example.

We will use the following condition solve the problem

A[i, j] = min(A[i, j], A[i, k] + A[k, j])

Solution is derived as follows using the above condition.

Cost Matrix

1 2 3 4 5
1 0 20 ∞ 5 5
2 20 0 10 ∞ 10
3 ∞ 10 0 15 10
4 5 ∞ 15 0 5
5 5 10 10 5 0

Iteration 1 Iteration 2

1 2 3 4 5
1 0 20 ∞ 5 5
2 20 0 10 ∞ 10
3 ∞ 10 0 15 10
4 5 25 15 0 5
5 5 10 10 5 0
 1 2 3 4 5
1 0 20 30 5 5
2 20 0 10 ∞ 10
3 30 10 0 15 10
4 5 25 15 0 5
5 5 10 10 5 0
Iteration 3 Iteration 4

1 2 3 4 5 1 2 3 4 5
1 0 20 30 5 5 1 0 20 20 5 5
2 20 0 10 25 10 2 20 0 10 25 10
3 30 10 0 15 10 3 20 10 0 15 10
4 5 25 15 0 5 4 5 25 15 0 5
5 5 10 10 5 0
5 5 10 10 5 0

Iteration 5 Final Output matrix

1 2 3 4 5 1 2 3 4 5
1 0 15 15 5 5 1 0 15 15 5 5
2 15 0 10 15 10 2 15 0 10 15 10
3 15 10 0 15 10 3 15 10 0 15 10
4 5 15 15 0 5 4 5 15 15 0 5
5 5 10 10 5 0 5 5 10 10 5 0
 The output matrix gives the shortest path distance between all pairs of nodes.

Algorithm

ALLPAIRSHORTESTPATH(cost, A, n)
For i = 1 to n
For j = 1 to n
A[i, j] = cost[i, j]
End for
For k = 1 to n
For i = 1 to n
For j = 1 to n
A[i, j] = min(A[i, j], A[i, k] + A[k, j])
End for
End for
End for