Minimum Spanning Trees - PowerPoint Presentation, Algorithms Notes | EduRev

: Minimum Spanning Trees - PowerPoint Presentation, Algorithms Notes | EduRev

 Page 1


1
CSE 421
Algorithms g
Richard Anderson
Lecture 10-11
Minimum Spanning Trees
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman Ford algorithm finds shortest • Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Compute the bottleneck shortest 
paths
a
e
d
4
6
6
5
4
4
a
e
d
b
c
s
e
g
f
2
-3
-2
3
7
5
3
7
b
c
s
e
g
f
Dijkstra’s Algorithm
for Bottleneck Shortest Paths
S = {};    d[s] = negative infinity;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], max(d[v], c(v, w)))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
Page 2


1
CSE 421
Algorithms g
Richard Anderson
Lecture 10-11
Minimum Spanning Trees
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman Ford algorithm finds shortest • Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Compute the bottleneck shortest 
paths
a
e
d
4
6
6
5
4
4
a
e
d
b
c
s
e
g
f
2
-3
-2
3
7
5
3
7
b
c
s
e
g
f
Dijkstra’s Algorithm
for Bottleneck Shortest Paths
S = {};    d[s] = negative infinity;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], max(d[v], c(v, w)))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
2
Minimum Spanning Tree
• Introduce Problem
• Demonstrate three different greedy 
algorithms
Pid fthtthl ith k • Provide proofs that the algorithms work
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
• Extend a tree by 
including the 
cheapest out going 
edge
• Add the cheapest
4
20
b c
• Add the cheapest 
edge that joins 
disjoint components
• Delete the most 
expensive edge that 
does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Prim’s 
algorithm starting 
from vertex a
Label the edges in 
order of insertion
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Kruskal’s 
algorithm
Label the edges in 
order of insertion
Greedy Algorithm 3
Reverse-Delete Algorithm
• Delete the most expensive edge that does 
not disconnect the graph
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with the reverse-
delete algorithm
Label the edges in 
order of removal
Page 3


1
CSE 421
Algorithms g
Richard Anderson
Lecture 10-11
Minimum Spanning Trees
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman Ford algorithm finds shortest • Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Compute the bottleneck shortest 
paths
a
e
d
4
6
6
5
4
4
a
e
d
b
c
s
e
g
f
2
-3
-2
3
7
5
3
7
b
c
s
e
g
f
Dijkstra’s Algorithm
for Bottleneck Shortest Paths
S = {};    d[s] = negative infinity;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], max(d[v], c(v, w)))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
2
Minimum Spanning Tree
• Introduce Problem
• Demonstrate three different greedy 
algorithms
Pid fthtthl ith k • Provide proofs that the algorithms work
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
• Extend a tree by 
including the 
cheapest out going 
edge
• Add the cheapest
4
20
b c
• Add the cheapest 
edge that joins 
disjoint components
• Delete the most 
expensive edge that 
does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Prim’s 
algorithm starting 
from vertex a
Label the edges in 
order of insertion
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Kruskal’s 
algorithm
Label the edges in 
order of insertion
Greedy Algorithm 3
Reverse-Delete Algorithm
• Delete the most expensive edge that does 
not disconnect the graph
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with the reverse-
delete algorithm
Label the edges in 
order of removal
3
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
• Let S be a subset of V, and suppose e = 
(u v) is the minimum cost edge of E with (u, v) is the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree
Proof 
• Suppose T is a spanning tree that does not 
contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) 
with u
1
in S and v
1
in V-S with u
1
in S and v
1
in V S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower 
cost
• Hence, T is not a minimum spanning tree
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
Reverse-Delete Algorithm
• Lemma:  The most expensive edge on a 
cycle is never in a minimum spanning tree
Dealing with the assumption of no 
equal weight edges
• Force the edge weights to be distinct
– Add small quantities to the weights 
– Give a tie breaking rule for equal weight 
edges edges 
Dijkstra’s Algorithm
for Minimum Spanning Trees
S = {};    d[s] = 0;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], c(v, w))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
Page 4


1
CSE 421
Algorithms g
Richard Anderson
Lecture 10-11
Minimum Spanning Trees
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman Ford algorithm finds shortest • Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Compute the bottleneck shortest 
paths
a
e
d
4
6
6
5
4
4
a
e
d
b
c
s
e
g
f
2
-3
-2
3
7
5
3
7
b
c
s
e
g
f
Dijkstra’s Algorithm
for Bottleneck Shortest Paths
S = {};    d[s] = negative infinity;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], max(d[v], c(v, w)))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
2
Minimum Spanning Tree
• Introduce Problem
• Demonstrate three different greedy 
algorithms
Pid fthtthl ith k • Provide proofs that the algorithms work
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
• Extend a tree by 
including the 
cheapest out going 
edge
• Add the cheapest
4
20
b c
• Add the cheapest 
edge that joins 
disjoint components
• Delete the most 
expensive edge that 
does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Prim’s 
algorithm starting 
from vertex a
Label the edges in 
order of insertion
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Kruskal’s 
algorithm
Label the edges in 
order of insertion
Greedy Algorithm 3
Reverse-Delete Algorithm
• Delete the most expensive edge that does 
not disconnect the graph
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with the reverse-
delete algorithm
Label the edges in 
order of removal
3
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
• Let S be a subset of V, and suppose e = 
(u v) is the minimum cost edge of E with (u, v) is the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree
Proof 
• Suppose T is a spanning tree that does not 
contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) 
with u
1
in S and v
1
in V-S with u
1
in S and v
1
in V S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower 
cost
• Hence, T is not a minimum spanning tree
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
Reverse-Delete Algorithm
• Lemma:  The most expensive edge on a 
cycle is never in a minimum spanning tree
Dealing with the assumption of no 
equal weight edges
• Force the edge weights to be distinct
– Add small quantities to the weights 
– Give a tie breaking rule for equal weight 
edges edges 
Dijkstra’s Algorithm
for Minimum Spanning Trees
S = {};    d[s] = 0;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], c(v, w))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
4
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
Undirected Graph 
G=(V,E) with edge 
weights
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
•[Prim] Extend a tree by 
including the cheapest 
out going edge
• [Kruskal] Add the 
cheapest edge that joins
4
20
b c
cheapest edge that joins 
disjoint components
• [ReverseDelete] Delete 
the most expensive edge 
that does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
Edge inclusion lemma
• Let S be a subset of V, and suppose e = 
(u, v) is the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree of G • e is in every minimum spanning tree of G
– Or equivalently, if e is not in T, then T is not a 
minimum spanning tree
SV - S
e
Proof 
• Suppose T is a spanning tree that does not contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) with u
1
in S 
and v
1
in V-S
e is the minimum cost edge 
between S and V-S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower cost
• Hence, T is not a minimum spanning tree
SV - S
e
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
• Show that when an edge is added to the 
MST by Prim or Kruskal, the edge is the 
minimum cost edge between S and V-S 
for some set S.
Page 5


1
CSE 421
Algorithms g
Richard Anderson
Lecture 10-11
Minimum Spanning Trees
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman Ford algorithm finds shortest • Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Compute the bottleneck shortest 
paths
a
e
d
4
6
6
5
4
4
a
e
d
b
c
s
e
g
f
2
-3
-2
3
7
5
3
7
b
c
s
e
g
f
Dijkstra’s Algorithm
for Bottleneck Shortest Paths
S = {};    d[s] = negative infinity;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], max(d[v], c(v, w)))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
2
Minimum Spanning Tree
• Introduce Problem
• Demonstrate three different greedy 
algorithms
Pid fthtthl ith k • Provide proofs that the algorithms work
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
• Extend a tree by 
including the 
cheapest out going 
edge
• Add the cheapest
4
20
b c
• Add the cheapest 
edge that joins 
disjoint components
• Delete the most 
expensive edge that 
does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Prim’s 
algorithm starting 
from vertex a
Label the edges in 
order of insertion
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with Kruskal’s 
algorithm
Label the edges in 
order of insertion
Greedy Algorithm 3
Reverse-Delete Algorithm
• Delete the most expensive edge that does 
not disconnect the graph
6
15
t
a
9
2
13
4
11
5
7
20
14
10
1
8
12
16
22
17
3
e
c
g
f
b
s
u
v
Construct the MST 
with the reverse-
delete algorithm
Label the edges in 
order of removal
3
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
• Let S be a subset of V, and suppose e = 
(u v) is the minimum cost edge of E with (u, v) is the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree
Proof 
• Suppose T is a spanning tree that does not 
contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) 
with u
1
in S and v
1
in V-S with u
1
in S and v
1
in V S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower 
cost
• Hence, T is not a minimum spanning tree
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
Reverse-Delete Algorithm
• Lemma:  The most expensive edge on a 
cycle is never in a minimum spanning tree
Dealing with the assumption of no 
equal weight edges
• Force the edge weights to be distinct
– Add small quantities to the weights 
– Give a tie breaking rule for equal weight 
edges edges 
Dijkstra’s Algorithm
for Minimum Spanning Trees
S = {};    d[s] = 0;     d[v] = infinity for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], c(v, w))
s
u
v
z
y
x
a
b
4
1
1
1
2
2
3
3
3
4
4
5
4
Minimum Spanning Tree
a
e
9
6
4
14
t
15
3
Undirected Graph 
G=(V,E) with edge 
weights
b
c
s
e
g
f
2
13
11
5
7
20
u
v
10
1
8
12
16
22
17
Greedy Algorithms for Minimum 
Spanning Tree
•[Prim] Extend a tree by 
including the cheapest 
out going edge
• [Kruskal] Add the 
cheapest edge that joins
4
20
b c
cheapest edge that joins 
disjoint components
• [ReverseDelete] Delete 
the most expensive edge 
that does not disconnect 
the graph
11 5
7
20
8
22
a
d
e
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
Edge inclusion lemma
• Let S be a subset of V, and suppose e = 
(u, v) is the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree of G • e is in every minimum spanning tree of G
– Or equivalently, if e is not in T, then T is not a 
minimum spanning tree
SV - S
e
Proof 
• Suppose T is a spanning tree that does not contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) with u
1
in S 
and v
1
in V-S
e is the minimum cost edge 
between S and V-S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower cost
• Hence, T is not a minimum spanning tree
SV - S
e
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
• Show that when an edge is added to the 
MST by Prim or Kruskal, the edge is the 
minimum cost edge between S and V-S 
for some set S.
5
Prim’s Algorithm
S = { };    T = { };
while S != V
choose the minimum cost edge                    
() ith i S d i V S e = (u,v), with u in S, and v in V-S
add e to T
add v to S
Prove Prim’s algorithm computes 
an MST 
• Show an edge e is in the MST when it is 
added to T
Kruskal’s Algorithm
Let C = {{v
1
}, {v
2
}, . . ., {v
n
}};  T = { }
while |C| > 1
Let e = (u, v) with u in C
i
and v in C
j
be the 
j
minimum cost edge joining distinct sets in C
Replace C
i
and C
j
by C
i
U C
j
Add e to T
Prove Kruskal’s algorithm 
computes an MST 
• Show an edge e is in the MST when it is 
added to T
Reverse-Delete Algorithm
• Lemma:  The most expensive edge on a 
cycle is never in a minimum spanning tree
Dealing with the assumption of no 
equal weight edges
• Force the edge weights to be distinct
– Add small quantities to the weights 
– Give a tie breaking rule for equal weight 
edges edges 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!