Data Structure (KCS-301)

Unit 4
Prepared By
N. U. Khan
Computer Science And Engineering Department
IMS Engineering College, Ghaziabad

N U Khan 1
 Reference Books
• 1.Horowitz and Sahani, “Fundamentals of Data
Structures”, Galgotia Publications Pvt Ltd Delhi
India.
• 2. Lipschutz, “Data Structures” Schaum’s Outline
Series, Tata McGraw-hill Education (India) Pvt.
Ltd.
• 3. Thareja, “Data Structure Using C” Oxford
Higher Education.
• 4. AK Sharma, “Data Structure Using C”, Pearson
Education India.
N U Khan 2
 Topics covered in Unit-1
• Graphs: Terminology used with Graph, Data
Structure for Graph Representations:
Adjacency Matrices, Adjacency List, Adjacency.
Graph Traversal: Depth First Search and
Breadth First Search, Connected Component,
Spanning Trees, Minimum Cost Spanning Trees:
Prims and Kruskal algorithm. Transitive Closure
and Shortest Path algorithm: Warshal
Algorithm and Dijikstra Algorithm.
N U Khan 3
 Graph
• A graph is a set of nodes ( vertices) connected by edges
• A graph ‘G’ consists of two sets ‘V’ and ‘E’
1. ‘V’ is a finite non empty set of vertices
2. ‘E’ is a set of pairs of vertices, these pairs are called edges.
e3 v2
e4
v1 e2
e1 e5
v3
v5
e6
e7 v4
We can write any graph G=(V, E)
1. V(G) represent set of vertices of graph ‘G’ [ V(G) = { v1, v2, v3, v4, v5 } ]
2. E(G) represent set of edges of graph ‘G’ [ E(G) = { e1, e2, e3, e4, e5, e6, e7 } ]
4
N U Khan
 Adjacency List representation of Graph
An array of lists is used. The size of the array is equal to the number of
vertices.
Let the array is A[]. An entry array A[i] represents the list of vertices
adjacent to the ith vertex.

A[0] v1 V3 V4

A[1] v2 V1 V4 V3 v1 v2

A[2] V3 V4
v4 v3
A[3] v4

This representation can also be used to represent a weighted graph.

The weights of edges can be represented as lists of pairs of weight &
vertices.
N U Khan 5
 Dijkstra’s Algorithm
• It is single source shortest path algorithm.
• It is start from source node ‘v’,
• Expend the tree from source node ‘v’ (root) by adding the lightest edge
• it grows a tree that ultimately spans all vertices reachable from ‘v’.
• These vertices are added to spanning tree in order of distance (i.e. first
starting vertex ‘v’, then the vertex closest to ‘v’, then next closest and so on)
• During spanning if vertices have smallest value then do nothing otherwise
update the parent of that node (join smallest edge and leaving largest one)
v2 v2
5 5
v1 1 6 v1 1 6
7 7
v3 v4 v3 v4
3 9 3 9
2 2
v6 7 v6 7
2 v5 2 v5
• Because it always chooses the “cheapest" vertex to insert into a growing tree
‘T’, it is called as the greedy strategy.
N U Khan 6
 Dijkstra’s Algorithm
Dijkstra's Algorithm (G, w, s)
• Step 1: INITIALIZE - SINGLE - SOURCE (G, s)
– Initialize the given graph G=(V, E). Initialize the infinite cost of all nodes
except the source node ‘s’ which has 0 cost
• Step 2: S←∅
– S will contains vertices of final shortest path weights from ‘s’
• Step 3: Q←V [G]
– Initialize priority queue ‘Q’ with cost of all vertices
• Step 4: while Q ≠ ∅ do t
– While priority queue ‘Q’ is not empty then follow step 5, 6 & 7
0
• Step 5: u ← EXTRACT_MIN (Q)
– Chose the node which is closest to the source node 3 5
7
• Step 6: S ← S ∪ {u}
– Add closest node ‘u’ to set S 2 1
∞
3 75
∞ ∞
5
• Step 7: for each vertex v ∈ Adj [u] do step 8
– For all neighbors of ‘u’ do the following step
u v x
• Step 8: RELAX (u, v, w) d[v]=min(d[v],
d[x]=min(d[x], d[t]+w(t,v))
d[u]+w(u,v))
d[v]+w(v,x))
– Relax all neighbors of ‘u’ i.e. update their cost in priority queue and change
predecessor for all neighbors if they have low cost.
N U Khan 7
 Dijkstra’s Algorithm
Dijkstra's Algorithm (G, w, s)
• Step 1: INITIALIZE - SINGLE - SOURCE (G, s)
– Initialize the given graph G=(V, E). Initialize the infinite cost of all nodes
except the source node ‘s’ which has 0 cost
• Step 2: S←∅
– S will contains vertices of final shortest path weights from ‘s’
• Step 3: Q←V [G]
– Initialize priority queue ‘Q’ with cost of all vertices
• Step 4: while Q ≠ ∅ do
– While priority queue ‘Q’ is not empty then follow step 5, 6 & 7
• Step 5: u ← EXTRACT_MIN (Q)
– Chose the node which is closest to the source node
• Step 6: S ← S ∪ {u}
– Add closest node ‘u’ to set S
• Step 7: for each vertex v ∈ Adj [u] do step 8
– Select all neighbors of ‘u’
• Step 8: RELAX (u, v, w)
– Relax all neighbors i.e. update their cost in priority queue and change
predecessor for all neighbors if they have low cost.
N U Khan 8
 Dijkstra’s Algorithm
Dijkstra's Algorithm (G, w, s)

INITIALIZE - SINGLE - SOURCE (G, s)

S←∅
Q←V [G]
while ( Q ≠ ∅ ) do
{
u ← EXTRACT_MIN (Q)
S ← S ∪ {u}
for each vertex v ∈ Adj [u] do
{
RELAX (u, v, w)
}
}
– Relax all neighbors i.e. update their cost in priority queue and
change predecessor for all neighbors if they have low cost.
N U Khan 9
 Dijkstra’s Algorithm
Q: Find the shortest path in the below graph from the source vertex ‘s’ to all
other vertices by using Dijkstra’s algorithm

1
u v
10
2 3
9 4 6
s
7
5
x 2
y

Step 1: In the given graph G=(V, E), initialize the infinite ‘∞’ cost of all vertices
except the source node ‘s’ which has zero ‘0’ cost
u v
i.e. d[s]=0, d[u]=∞, d[v]=∞, d[x]=∞, d[y]=∞
1 v
u
∞ ∞
Set of Vertices S = { } 10
2
3 9 4 6
Initialize Priority queue Q = V[G] s 0s
7
s u v x y 5
x
∞ y
∞
0 ∞ ∞ ∞ ∞ 2
N U Khan x y 10
 Dijkstra’s Algorithm
Set of Vertices S = { } u v
1
Initialize Priority queue Q = V[G] ∞ ∞
10
s u v x y 2
s 0 3 9 4 6
0 ∞ ∞ ∞ ∞ 7
u=EXTRACT_MIN(Q) = s 5
∞ 2
∞
S=S∪{s} ={s} y
x
Step 2: For all neighbours of ‘s’ perform RELAX function
d[u]=min(d[u], d[s]+w)
d[u]=min(∞, 0+10)
u v
1
∞
10 ∞
10
2
3 4 6
s 0 9
7
5 5
∞ 2
∞
s u v x y x y
d[x]=min(d[x], d[s]+w)
∞ ∞ ∞
10 5 ∞ N U Khan d[x]=min(∞, 0+5) 11
 Dijkstra’s Algorithm u v
1
s u v x y 10 ∞
10
10 ∞ 5 ∞ 2
s 0 3 9 4 6
u=EXTRACT_MIN(Q) =x
7
S = S ∪ { x } = { s, x } 5
5 2
∞
Step 3: For all neighbours of ‘x’ perform RELAX x y
function d[u]=min(d[u], d[x]+w)
d[u]=min(10, 5+3)
u v
1 14
10
8 ∞
10
2
s 0 3 9 4 6

7
5
5 2
7
∞
x y
d[y]=min(d[y], d[x]+w)
s u v x y
d[y]=min(∞, 5+2)
8 14
10 ∞ 7
∞ N U Khan 12
 Dijkstra’s Algorithm u v
1 14
s u v x y 8
10
8 14 7 2
s 0 3 9 4 6
u=EXTRACT_MIN(Q) =y
7
S = S ∪ { y } = { s, x, y } 5
5 2
7
Step 3: For all neighbours of ‘y’ perform RELAX x y
function
d[v]=min(d[v], d[y]+w)
d[v]=min(14, 7+6)
d[s]=min(d[s], d[y]+w) u v
d[s]=min(0, 7+7) 1 13
14
10
8
2
s 0 3 9 4 6
7
5
5 2
7
x y
s u v x y
13
8 14 N U Khan 13
 Dijkstra’s Algorithm u v
1 13
s u v x y 10
8
8 13 2
s 0 3 9 4 6
u=EXTRACT_MIN(Q) =u
7
S = S ∪ { u } = { s, x, y, u } 5
5 2
7
Step 3: For all neighbours of ‘u’ perform RELAX x y
function
d[v]=min(d[v], d[u]+w)
d[v]=min(13, 8+1)
u v
1 9
13
10
8
2
s 0 3 9 4 6
7
5
5 2
7
x y
s u v x y d[x]=min(d[x], d[u]+w)
d[x]=min(5, 8+2)
13
9 N U Khan 14
 Dijkstra’s Algorithm u v
1 9
s u v x y 10
8
9 2
s 0 3 9 4 6
u=EXTRACT_MIN(Q) =v
7
S = S ∪ { v } = { s, x, y, u, v } 5
5 2
7
Step 3: For all neighbours of ‘v’ perform RELAX x y
function

u v
1 9
10
8
2
s 0 3 9 4 6
7
5
5 2
7
x y
s u v x y d[y]=min(d[y], d[v]+w)
d[y]=min(7, 9+4)
N U Khan 15
 Dijkstra’s Algorithm
u v
1 9
10
8
2
s 0 3 9 4 6
7
5
5 2
7
x y
Shortest path from source node ‘s’
Source Destination Total
Path
node node Weight
s v s→x→u→v 9
s u s→x→u 8
s y s→x→y 7
s x s→x 5
N U Khan 16