Minimum Spanning Tree
Deliverables
Spanning sub graph
Prim’s Algorithm
Kruskal’s Algorithm
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 2
Spanning Forest
Spanning sub graph is Sub graph
of G containing all vertices of G
Spanning tree is Spanning sub
graph that is itself a tree
Minimum spanning tree is
Spanning tree of weighted graph
with minimum total edge weight
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 3
Minimum Spanning Tree
Given a connected graph G = (V, E) with real-valued edge weights, an MST is a
subset of the edges such that T is a spanning tree whose sum of edge weights is
minimized.
4 24 4
23 9 9
6 18 6
5 11 5 11
16
8 8
7 7
10 14
21
G = (V, E) T, eT ce = 50
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 4
Cut and Cut set
A cut is a subset of
nodes S. The
corresponding cutset D
is the subset of edges
with exactly one
endpoint in S
Cut S = { 4, 5, 8 }
Cutset D = 5-6, 5-7, 3-
4, 3-5, 7-8
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 5
Cycle and cutset relation
A cycle and a cutset intersect in
an even number of edges.
Cycle C = 1-2, 2-3, 3-4, 4-5, 5-6,
6-1
Cutset D = 3-4, 3-5, 5-6, 5-7, 7-8
Intersection = 3-4, 5-6
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 6
Prim Algorithm
Use a priority queue
Maintain set of explored nodes S.
For each unexplored node v, maintain the attachment
cost a[v] = cost of cheapest edge v to a node in S.
O(V2) with an array; O(E log V) with a binary heap
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 8
Prim Algorithm
Prim(G, c) {
for all (v V)
key[v]
Initialize an empty priority queue Q
for each (v V)
insert v onto Q
Initialize set of explored nodes S
while (Q is not empty) {
u delete min element from Q
S S {u}
foreach (edge e = (u, v) incident to u)
if ((v S) and (ce < a[v]))
decrease priority a[v] to ce
}
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 9
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 10
A[v] Priority Queue Q Set of explored
nodes S
∞∞∞∞∞∞∞∞∞ Empty Null
0∞∞∞∞∞∞∞∞ ab =4 ah=8 {a}
04∞∞∞∞∞∞∞ ah=8 bc=8 bh=11 {a,b}
048∞∞∞∞∞∞ ah=8 bh=11 cd=7 cf=4 ci=2 {a,b,c}
048∞∞∞∞∞2 ah=8 bh=11 cd=7 cf=4 ig=6 {a,b,c,i}
ih=7
048∞∞4∞∞2 ah=8 bh=11 cd=7 ig=6 ih=7 {a,b,c,i,f}
fd=14 fe=10 fg=2
048∞∞42∞2 ah=8 bh=11 cd=7 ig=6 ih=7 {a,b,c,i,f,g}
fd=14 fe=10 gh=1
048∞∞4212 ah=8 bh=11 cd=7 ig=6 ih=7 {a,b,c,f,g,h,i}
fd=14 fe=10
0487∞4212 ah=8(c) bh=11 fd=14 fe=10 {a,b,c,d,f,g,h,i}
de=9
048794212 bh=11(c) fd=14(c) fe=10 (c) {a,b,c,d,e,f,g,h,i}
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 11
Kruskal Algorithm
It finds a MST for a connected weighted graph.
This means it finds a subset of the edges that forms a tree
that includes every vertex, where the total weight of all the
edges in the tree is minimized.
If the graph is not connected, then it finds a minimum
spanning forest (a minimum spanning tree for
each connected component).
Kruskal's algorithm is an example of a greedy algorithm.
Complexity: O(E log V)
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 12
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 14
Kruskal Example
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 15
Questions, Comments and Suggestions
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 17
Question 1
Suppose we have computed a minimum spanning tree of
graph and its weight. If we make a new graph by
doubling the weight of every edge in the original graph,
we still need Ω(E) time to compute the cost of the new
MST of the new Graph.
A) True
B) False
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 18
Question 2
A maximum spanning tree (Spanning tree that maximize
the sum of the weights) can be constructed in O(ElgV)
time.
A) True
B) False
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 19
Question 3
In any MST, if we remove an edge then the remaining
two trees are MSTs on their own set of nodes and the
removed edge is a least cost edge crossing between these
two.
So we can propose an algorithm: Split the nodes into two
equal sized sets, and recursively find MST on these sets.
Then connect the two trees with a least cost edge.
Will you use this algorithm? Why or Why not.
11/24/2021 9:41 AM Copyright @ gdeepak.Com® 20
