APznzaZLM_MVouyxM4cxHPJR5BC-TAxTWqhQJ2EywQQuXStxJTDoGkHdsKEQGd4Vo7BS3Q1npCOMV0V74UXL-lBqKxDd_Fn_Bl1IAafiengGrex1nn4IL86BQsAz9cSXxnxEtInomw8hp - dmoAOJIxs59hSNWeW1JIG0Y3wzys-xz98dtB0bCspm5CRUgDmhMDo1t1C7D3dNRyEM6glz.pptx

DATA STRUCTURES AND
ALGORITHMS
(18CSC162J)

Data Structure - Minimum
spanning tree- Kruskal's
Algorithm, Prim’s Algorithm,
Shortest Path Algorithm:
Dijkstra’s Algorithm
UNIT IV

Topics to be covered (theory)
Session Topics
1 Minimum spanning tree- Prim’s Algorithm
2 Minimum spanning tree- Kruskal's Algorithm
3 Shortest Path Algorithm: Dijkstra’s Algorithm

Topics for lab session
Session Topics
1 Implementation of Minimal Spanning Tree
2 Implementation of Shortest path Algorithm

Learning Resources
• Fundamentals of Data Structures, E. Horowitz and S. Sahni, 1977.
• Data Structures and Algorithms, Alfred V. Aho, John E. Hopperoft,
Jeffrey D. UIlman.
• Mark Allen Weiss, Data Structures and Algorithm Analysis in C, 2nd
ed., Pearson Education, 2015
• Reema Thareja, Data Structures Using C, 1st ed., Oxford Higher
Education, 2011
• Thomas H Cormen, Charles E Leiserson, Ronald L Revest, Clifford
Stein, Introduction to Algorithms 3rd ed., The MIT Press Cambridge,
2014

Graph - Spanning Tree
A tree that contains every vertex of a connected graph is called spanning tree. It
is an undirected tree consisting of only those edges that are necessary to
connect all the vertices of the original graph G.
CHARACTERISTICS
1. It is a subgraph of a graph G that contain all the vertex of graph G.
2. For any pair of vertices, there exists only one path between them.
3. It is a connected graph with no cycles.
4. A graph may have many spanning tree.

Graph - Minimum Spanning Tree
•Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is
minimum is called minimum spanning tree. The cost of the spanning tree is
defined as the sum of the costs of the edges in that tree.

Minimum Spanning Tree
• A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges.
• A complete undirected graph can have maximum nn-2 number of spanning trees,
where n is number of nodes.

General properties of spanning tree
• A connected graph G can have more than one spanning tree.
• All possible spanning trees of graph G, have same number of edges and vertices.
• Spanning tree does not have any cycle (loops)
• Removing one edge from spanning tree will make the graph disconnected i.e.
spanning tree is minimally connected.
• Adding one edge to a spanning tree will create a cycle or loop i.e. spanning tree
is maximally acyclic.

Mathematical properties of spanning tree
• Spanning tree has n-1 edges, where n is number of nodes (vertices)
• From a complete graph, by removing maximum
e-n+1 edges, we can construct a spanning tree.
• A complete graph can have maximum nn-2 number of spanning trees.
• So we can conclude here that spanning trees are subset of a connected Graph G
and disconnected Graphs do not have spanning tree.

Application of Spanning Tree
•Spanning tree is basically used to find minimum paths to connect all
nodes in a graph.
• Civil Network Planning
• Computer Network Routing Protocol
• Cluster Analysis

Minimum Spanning Tree (MST)
• In a weighted graph, a minimum spanning tree is a spanning tree that has
minimum weight that all other spanning trees of the same graph.
MST Algorithm
• Kruskal’s Algorithm
• Prim’s Algorithm
Both are greedy algorithms.

A cable company want to connect five villages to their network which currently
extends to the market town of Avonford. What is the minimum length of cable
needed?
Avonford Fingley
Brinleigh Cornwell
Donster
Edan
2
7
4
5
8 6
4
5
3
8
Example

We model the situation as a network, then the problem is to find the minimum
connector for the network
A F
B C
D
E
2
7
4
5
8 6
4
5
3
8

A
E
F
B
C
D
2
7
4
5
8 6
4
5
3
8
List the edges in
order of size:
ED 2
AB 3
AE 4
CD 4
BC 5
EF 5
CF 6
AF 7
BF 8
CF 8
Kruskal’s Algorithm

Select the shortest
edge in the network
ED 2
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

Select the next shortest
edge which does not
create a cycle
ED 2
AB 3
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

edge which does not
create a cycle
ED 2
AB 3
CD 4 (or AE 4)
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

edge which does not
create a cycle
ED 2
AB 3
CD 4
AE 4
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

edge which does not
create a cycle
ED 2
AB 3
CD 4
AE 4
BC 5 – forms a cycle
EF 5
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

All vertices have been
connected.
The solution is
ED 2
AB 3
CD 4
AE 4
EF 5
Total weight of tree: 18
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

connected.
The solution is
ED 2
AB 3
CD 4
AE 4
EF 5
A
F
B
C
D
2
4
5
4
3
E

Kruskal Algorithm
Algorithm
• Remove all loops & Parallel Edges from the given graph
• Sort all the edges in non-decreasing order of their weight.
• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
cycle is not formed, include this edge. Else, discard it.
• Repeat step#2 until there are (V-1) edges in the spanning tree.

A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
Select any vertex
A
Select the shortest
edge connected to
that vertex
AB 3
Prim’s Algorithm
E

A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
Select the shortest
edge connected to
any vertex already
connected.
AE 4
Prim’s Algorithm
E

Select the shortest
edge connected to
any vertex already
connected.
ED 2
Prim’s Algorithm
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

Select the shortest
edge connected to
any vertex already
connected.
DC 4
Prim’s Algorithm
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

Select the shortest
edge connected to
any vertex already
connected.
EF 5
Prim’s Algorithm
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
E

Prim’s Algorithm
A
F
B
C
D
2
7
4
5
8 6
4
5
3
8
connected.
The solution is
AB 3
AE 4
ED 2
DC 4
EF 5
E

Prim’s Algorithm
A
F
B
C
D
2
4
5
4
3
connected.
The solution is
AB 3
AE 4
ED 2
DC 4
EF 5
E

Prim’s Algorithm
• Create a set mstSet that keeps track of vertices already included in MST.
• Assign a key value to all vertices in the input graph. Initialize all key
values as INFINITE. Assign key value as 0 for the first vertex so that it is
picked first.
• While mstSet doesn’t include all vertices
• Pick a vertex u which is not there in mstSet and has minimum key value.
• Include u to mstSet.
• Update key value of all adjacent vertices of u. To update the key values, iterate
through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less
than the previous key value of v, update the key value as weight of u-v

Minimum Spanning Tree Algorithms
2. Select the next shortest edge
which does not create a cycle
3. Repeat step 2 until all vertices
have been connected
Kruskal’s algorithm Prim’s algorithm
1. Select the shortest edge in a 1. Select any vertex
network
2. Select the shortest edge
connected to that vertex
3. Select the shortest edge
connected to any vertex already
connected
4. Repeat step 3 until all vertices
have been connected

Lets revise
•Identify the following and state which algorithm it follows

Prims Algorithm
Kruskal Algorithm

Find a MST using Kruskal and Prims Algorithm

Kruskal algorithm to create MST

Single-Source Shortest Path Problem
Single-Source Shortest Path Problem - The problem of finding
shortest paths from a source vertex v to all other vertices in the graph.

Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source shortest path
problem in graph theory.
Works on both directed and undirected graphs. However, all edges must
have nonnegative weights.
Input: Weighted graph G={E,V} and source vertex v∈V, such that all edge
weights are nonnegative
Output: Lengths of shortest paths (or the shortest paths themselves) from a
given source vertex v∈V to all other vertices

41
Approach
• The algorithm computes for each vertex u the distance to u from the start vertex
v, that is, the weight of a shortest path between v and u.
• the algorithm keeps track of the set of vertices for which the distance has been
computed, called the cloud C
• Every vertex has a label D associated with it. For any vertex u, D[u] stores an
approximation of the distance between v and u. The algorithm will update a D[u]
value when it finds a shorter path from v to u.
• When a vertex u is added to the cloud, its label D[u] is equal to the actual (final)
distance between the starting vertex v and vertex u.

42
Dijkstra pseudocode
Dijkstra(v1, v2):
for each vertex v: // Initialization
v's distance := infinity.
v's previous := none.
v1's distance := 0.
List := {all vertices}.
while List is not empty:
v := remove List vertex with minimum distance.
mark v as known.
for each unknown neighbor n of v:
dist := v's distance + edge (v, n)'s weight.
if dist is smaller than n's distance:
n's distance := dist.
n's previous := v.
reconstruct path from v2 back to v1,
following previous pointers.

A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 ∞
∞ ∞
∞
Pick vertex in List with minimum distance.
∞ ∞
Distance(source) = 0 Distance (all vertices
but source) = ∞
43
Example: Initialization

Example: Update neighbors' distance
A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
∞ ∞
1
∞ ∞
Distance(B) = 2
Distance(D) = 1
44

Example: Remove vertex with minimum
distance
Pick vertex in List with minimum distance, i.e., D
A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
∞ ∞
1
∞ ∞
45

Example: Update neighbors
A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
3 3
1
9 5
Distance(C) = 1 + 2 = 3
Distance(E) = 1 + 2 = 3
Distance(F) = 1 + 8 = 9
Distance(G) = 1 + 4 = 5
46

Example: Continued...
A
G
F
B
E
C D
4 1
2
10
3
4
2
2
8
5
1
0 2
3 3
1
Pick vertex in List with minimum distance (B) and update neighbors
6
Note : distance(D) not
updated since D is
already known and
distance(E) not updated
since it is larger than
previously computed
47
9 5

A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
3 3
1
9
48
5
No updating
Pick vertex List with minimum distance (E) and update neighbors

A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
3 3
1
8
49
5
Pick vertex List with minimum distance (C) and update neighbors
Distance(F) = 3 + 5 = 8

A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
3 3
1
6 5
Distance(F) = min (8, 5+1) = 6
Previous distance
Pick vertex List with minimum distance (G) and update neighbors
50

Example (end)
A
G
F
B
E
C D
4 1
2
10
3
6
4
2
2
8
5
1
0 2
3 3
1
Pick vertex not in S with lowest cost (F) and update neighbors
6
51
5

APznzaZLM_MVouyxM4cxHPJR5BC-TAxTWqhQJ2EywQQuXStxJTDoGkHdsKEQGd4Vo7BS3Q1npCOMV0V74UXL-lBqKxDd_Fn_Bl1IAafiengGrex1nn4IL86BQsAz9cSXxnxEtInomw8hp - dmoAOJIxs59hSNWeW1JIG0Y3wzys-xz98dtB0bCspm5CRUgDmhMDo1t1C7D3dNRyEM6glz.pptx

Recommended

Recommended

More Related Content

Similar to APznzaZLM_MVouyxM4cxHPJR5BC-TAxTWqhQJ2EywQQuXStxJTDoGkHdsKEQGd4Vo7BS3Q1npCOMV0V74UXL-lBqKxDd_Fn_Bl1IAafiengGrex1nn4IL86BQsAz9cSXxnxEtInomw8hp - dmoAOJIxs59hSNWeW1JIG0Y3wzys-xz98dtB0bCspm5CRUgDmhMDo1t1C7D3dNRyEM6glz.pptx

Similar to APznzaZLM_MVouyxM4cxHPJR5BC-TAxTWqhQJ2EywQQuXStxJTDoGkHdsKEQGd4Vo7BS3Q1npCOMV0V74UXL-lBqKxDd_Fn_Bl1IAafiengGrex1nn4IL86BQsAz9cSXxnxEtInomw8hp - dmoAOJIxs59hSNWeW1JIG0Y3wzys-xz98dtB0bCspm5CRUgDmhMDo1t1C7D3dNRyEM6glz.pptx (20)

Recently uploaded

Recently uploaded (20)

APznzaZLM_MVouyxM4cxHPJR5BC-TAxTWqhQJ2EywQQuXStxJTDoGkHdsKEQGd4Vo7BS3Q1npCOMV0V74UXL-lBqKxDd_Fn_Bl1IAafiengGrex1nn4IL86BQsAz9cSXxnxEtInomw8hp - dmoAOJIxs59hSNWeW1JIG0Y3wzys-xz98dtB0bCspm5CRUgDmhMDo1t1C7D3dNRyEM6glz.pptx