Introduction
Ch.23. Minimum spanning tree
Read the entire chapter, but omit proof of Theorem 23.1
2
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
3
23.1 Growing a minimum spanning tree
What is a safe edge?
1. One that has the smallest cost among edges not yet in the MST
2. One that won’t create a cycle
This is an example of a Greedy Algorithm:
algorithms that solve a problem in stages, with the best possible partial
solution computed or chosen at each stage.
4
23.2 The algorithms of Kruskal and Prim
Kruskal’s Algorithm
Uses the Disjoint Set data structure to store nodes
and Find & Union operations
Prim’s Algorithm
Uses a Min-Priority-Queue
and Extract-Min operation
5
23.2 The algorithm of Kruskal
Reading Assignment: Read and understand this complexity calculation from text p. 633
Complexity O(E log V)
6
7
Continue ……
8
9
10
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
11
Omit proof of theorem 23.1 and corollary 23.2
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
12
Prim’s algorithm
Complexity:
O(V log V + E log V), or
O(E log V)
MST-PRIM(G,w,r)
For each u € G.V
u.key = ∞
u.π = NIL
r.Key = 0
Q = G.V
While Q ≠ Ǿ
u = EXTRACT-Min(Q)
for each v € G.Adj[u]
if v € Q and w(u,v) < v.key
then v.π = u
v.key = w(u,v)
Reading Assignment: Read and understand this complexity calculation from text p. 636
13
14
Let G=(V,E) be a connected, undirected graph. For each edge
Evu ),(
, we have a weight w(u,v) specifying the cost to connect
u and v. We wish to find an acyclic subset
ET
that connects
all of the vertices and whose to tal weight
Tvu
vuwTw
),(
),()(
is
minimized. Since T is acyclic and connects all of the vertices, it
must form a tree, which we call a spanning tree. We call the
problem of determine
the tree T the
minimum spanning
tree problem.
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
E
v
u
Î
)
,
(
a
c
i
g
f
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
E
T
Í
å
Î
=
T
v
u
v
u
w
T
w
)
,
(
)
,
(
)
(
a
c
i
g
f
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
Let G=(V,E) be a connected, undirected graph. For each edge
, we have a weight w(u,v) specifying the cost to connect u and v. We wish to find an acyclic subset
that connects all of the vertices and whose total weight
is minimized. Since T is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree. We call the problem of determine the tree T the minimum spanning tree problem.
� EMBED Visio.Drawing.6 ���
_1060219755.unknown
_1060219841.unknown
_1064224826.vsd
_1060219649.unknown
GENERIC -MST(G, w)
1
A
2 while A does not form a spanning tree
3 find an edge (u, v) that is safe for A
4
)},{(vuAA
5 return A
f
=
A
)}
,
{(
v
u
A
A
È
=
GENERIC-MST(G, w)
1
2
while A does not form a spanning tree
3
find an edge (u, v) that is safe for A
4
5
return A
_1413265968.unknown
_1413265969.unknown
MST_KRUSKAL( G, w)
1
A
2 for each vertex
VGv.
3 MAKE-SET(v)
4 sort the edges G.E by nondecreasing weight w
5 for each edge
EGvu .),(
, in order by nondecreasing weight
6 if FIND_SET(u)FIND_SET(v)
7 then
)},{(vuAA
8 UNION(u, v)
9 return A
f
=
A
V
G
v
.
Î
E
G
v
u
.
)
,
(
Î
)}
,
{(
v
u
A
A
È
=
MST_KRUSKAL(G, w)
1
2
for each vertex
3
MAKE-SET(v)
4
sort the edges G.E by nondecreasing weight w
5
for each edge
, in order by nondecreasing weight
6
if FIND_SET(u)(FIND_SET(v)
7
then
8
UNION(u, v)
9
return A
_1413266074.unknown
_1413266463.unknown
_1413266464.unknown
_1413266073.unknown
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
A cut (S,V-S) of an undirected graph G = (V,E) is a partition of V. We
say that an edge
Evu ),(
crosses the cut (S,V-S) if one of its
endpoints is in S and the other is in V -S. We say a cut respects the set
A of edges if no edge in A cros ses the cut. An edge is a light edge
crossing a cut if its weight is the minimum of any edge crossing the cut.
Note that there can be more than one light edge crossing a cut in case
of ties.
E
v
u
Î
)
,
(
A cut (S,V-S) of an undirected graph G = (V,E) is a partition of V. We say that an edge
crosses the cut (S,V-S) if one of its endpoints is in S and the other is in V-S. We say a cut respects the set A of edges if no edge in A crosses the cut. An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. Note that there can be more than one light edge crossing a cut in case of ties.
_1060219649.unknown
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
S
V-S
a
c
i
g
f
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
S
V-S
Theorem 23.1. Let G = (V, E) be a
connected undirected graph with a
real-valued weight function w defined on
E. Let A be a subset of E that is
included in some minimum spanning tree
for G, let (S, V-S) be any cut of G that
respects A, and let (u, v) be a light edge
crossing (S, V-S). Then, edge ( u, v) is
safe for A.
x
y
v
u
P
x
y
v
u
P
x
y
v
u
P
Theorem 23.1. Let G = (V, E) be a connected undirected graph with a real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, let (S, V-S) be any cut of G that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, edge (u, v) is safe for A.
� EMBED Visio.Drawing.6 ���
_1066568769.vsd
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
a
c
i
gf
e
d
h
b
8
4
8
11
7
1
14
10
9
2
6
7
2
4
/docProps/thumbnail.jpeg