Courses

# 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]
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]
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
4
20
b c
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]
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
4
20
b c
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]
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]
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
4
20
b c
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]
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
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]
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
4
20
b c
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]
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
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
Prove Prim’s algorithm computes
an MST
• Show an edge e is in the MST when it is
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
Prove Kruskal’s algorithm
computes an MST
• Show an edge e is in the MST when it is