Minimum Spanning Trees

 MST Generic Algorithm

 Kruskal’s algorithm
 Prim’s algorithm
 Definition
 Given a connected graph G = (V, E), with weight
function
w : E --> R
 Min-weight connected subgraph
 Spanning tree T:
 A tree that includes all nodes from V
 T = (V, E’), where E’  E
 Weight of T: W( T ) =  w(e)
 Minimum spanning tree (MST):
 A tree with minimum weight among all spanning trees
Example
 MST
 MST for given G may not be unique

 Since MST is a spanning tree:

 # edges : |V| - 1

 If the graph is unweighted:

 All spanning trees have same weight
 Cycle Property
f 8
Cycle Property: 4
 Let T be a minimum C 9
spanning tree of a weighted 2 6
graph G 3 e
 Let e be an edge of G that is 8 7
not in T and let C be the
cycle formed by e with T 7
 For every edge f of C, Replacing f with e yields
weight(f)  weight(e) a better spanning tree
Proof:
 By contradiction f 8
 If weight(f) > weight(e) we 4
can get a spanning tree of C 9
smaller weight by replacing 2 6
3 e
e with f 7
8
7
Minimum Spanning 5
 Cut Property
U V
f 7
Cut Property: 4
 Consider a partition of the vertices of G 9
into subsets U and V 2 5
8
 Let e be an edge of minimum weight
across the partition 8 e 3
 There is a minimum spanning tree of G 7
containing edge e
Proof: Replacing f with e yields
 Let T be an MST of G another MST
 If T does not contain e, consider the U V
cycle C formed by e with T and let f be f 7
an edge of C across the partition 4
 By the cycle property, 9
weight(f)  weight(e) 2 5
8
 Thus, weight(f) = weight(e)
8 e 3
 We obtain another MST by replacing f
with e 7
Minimum Spanning 6
 Generic Algorithm
 Framework for G = (V, E) :
 Goal: build a set of edges A  E
 Start with A empty
 Add edge into A one by one
 At any moment, A is a subset of some MST for G

An edge is safe if adding it to A still maintains that

A is a subset of a MST
 Finding Safe Edges
 When A is empty, example of safe edges?
 The edge with smallest weight
 Intuition:
 Suppose S  V, --- a cut (S, V-S)
 S and V-S should be connected
 By the crossing edge with the smallest weight !
 That edge also called a light edge crossing the cut (S, V-S)
 A cut (S, V-S) respects edge set A
 If no edges from A crosses the cut (S, V-S)
 Safe-Edge Theorem
 Theorem:
 Let A be a subset of some MST, (S, V-S) be a cut that
respects A, and (u, v) be a light edge crossing (S, V-S) .
Then (u, v) is safe for A.
 Proof: let T be an MST, A ⊆ T, A ≠ T. Assume T does not contain
the light edge (u, v). If it does, we are done. If not, we construct
another MST T’ that contains both A and (u, v).
T {(u, v)} must contain a cycle, with edges on a simple path p
from u to v in T. u and v are on opposite sides of the cut
(S, V –S), and at least one edge in T lies on p and crosses the cut.
 Proof: ( Contd)
Let (x, y) be any such edge – it cannot be in A, because the cut respects A. Since (x, y) is
on the unique simple path from u to v in T, removing (x, y) breaks T into two
components. Adding (u, v) reconnects them to form a new
spanning tree T’ = (T – {(x, y)}) {(u, v)}. But T’ is also an MST: since (u, v) is a light
edge crossing (S, V – S) and (x, y) also crosses the cut, w(u, v) ≤ w(x, y) and w(T’) =
w(T) – w(x, y) + w(u,v) ≤ w(T). The minimality of T implies w(T) ≤ w(T’), so T’ must be
minimal, also.

Is (u, v) safe? Since A ⊆ T and (x, y) ∉ A, we have A ⊆ T’. Thus A  {(u, v)} ⊆ T’.
Since T’ is an MST, (u, v) is safe for A.
 Safe-Edge Theorem
 Corollary:
 Let (u, v) be a light edge crossing (V’, V-V’), where
graph G’ = (V’, E’) is a connected component of the
graph (forest) G’’ = (V, A), then (u, v) is safe for A.

Greedy Approach:
Based on the generic algorithm and the corollary,
to compute MST we only need a way to find
a safe edge at each moment.
Corollary: 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 C = (V_C, E_C) be a connected
component (tree) in the forest G_A = (V, A). If (u, v) is a
light edge connecting C to some other component in G_A,
then (u, v) is safe for A.
 Proof: the cut (V_C, V – V_C) respects A, and (u, v) is a

light edge for this cut. Therefore (u, v) is safe for A.

 Kruskal’s Algorithm
 Start with A empty, and each vertex being its own
connected component
 Repeatedly merge two components by connecting
them with a light edge crossing them
 Two issues:
 Maintain sets of components

 Choose light edges Disjoint set data structure

Scan edges from low to high weight

Pseudo-code
Example
 Analysis
 Time complexity:
 #make-set, find-set and union operations: O(|V| + |E|)
 O( (|V| + |E|)  (|V| + |E|))
 Sorting:
 O(|E| log |E|) = O(|E| log |V|)
 Total:
 O(|E| log |V|)
 Prim’s Algorithm
 Start with an arbitrary node from V
 Instead of maintaining a forest, grow a MST
 At any time, maintain a MST for V’  V
 At any moment, find a light edge connecting V’
with (V-V’) i.e., the edge with smallest weight
connecting some vertex in V’ with some vertex in
V-V’ !
 Prim’s Algorithm cont.
 Again two issues:
 Maintain the tree already build at any moment
 Easy: simply a tree rooted at r : the starting node

 Find the next light edge efficiently

 For v  V - V’, define key(v) = the min distance between v and
some node from V’
 At any moment, find the node with min key.

Use a priority queue !

Pseudo-code
Example
 Analysis
 Time complexity
 # insert: Using Fibonacci heap:
O(|V|)

Decrease-Key:
 # Decrease-Key: O(1) amortized time
 O( |E|) =>
 # Extract-Min total time complexity
 O( |V| ) O(|E| + |V| log |V|)
 Using heap for priority queue:
 Each operation is O ( log |V| )
 Total time complexity: O (|E| log |V|)
 Applications
 Clustering

 Euclidean traveling salesman problem