20_MST.pdf
EECS 281: Data Structures & Algorithms
Lecture 20
Minimum Spanning Trees
Data Structures & Algorithms
Minimum Spanning Trees
3
The Minimum Spanning Tree Problem
Given: edge-weighted, undirected graph
G = (V, E)
Find: subgraph T = (V, E’), E’ Í E such that
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal
§ See a cycle in T?
§ Remove edge with highest weight
§ Therefore, T must be a tree (no cycles)
4
Connect All Data-Centers
https://cdn3.vox-cdn.com/assets/4537127/USdata.png
5
Create an MST
• Minimum Spanning Tree (MST) if:
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal
A
B
D
C
100
120
8040
20
60
Total Edge Weights:
20+40+60+100+120+80 = 420
6
Create an MST
• Minimum Spanning Tree (MST) if:
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal
A
B
D
C
100
8040
20
60
Total Edge Weights:
20+40+60+100+80 = 300
7
Create an MST
• Minimum Spanning Tree (MST) if:
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal
A
B
D
C
8040
20
60
Total Edge Weights:
20+40+60+80 = 200
8
Create an MST
• Minimum Spanning Tree (MST) if:
§ All vertices are pair-wise connected
§ The sum of all edge weights in T is minimal
A
B
D
C
8040
20Total Edge Weights:
20+40+80 = 140
9
MST Quiz
1. Prove that a unique shortest edge must
be included in every MST
2. Prove for second shortest edge
3. What about third shortest edge?
4. Show a graph with > 1 MST
5. Show a graph and its MST
which avoids some shortest edge
6. Show a graph where every longest edge
must be in every MST
Data Structures & Algorithms
Minimum Spanning Trees
Data Structures & Algorithms
Prim’s Algorithm
13
Prim’s Algorithm
• Find an MST on edge-weighted,
connected, undirected graphs
• Greedily select edges one by one
and add to a growing sub-graph
• Grows a tree from a single vertex
14
1. Initialize a tree with a single vertex,
chosen arbitrarily from the graph
2. Grow the tree by one edge: of the edges
that connect the tree to vertices not yet in
the tree, find the minimum-weight edge,
and add that vertex to the tree
3. Repeat step 2 (until all vertices are in the
tree)
Prim’s Algorithm
15
Prim’s Algorithm
• Given graph G = (V, E)
• Start with 2 sets of vertices: ‘innies’ & ‘outies’
– ‘Innies’ are visited nodes (initially empty)
– ‘Outies’ are not yet visited (initially V)
• Select first innie arbitrarily (root of MST)
• Repeat until no more outies
– Choose outie (v’) with smallest distance
from any innie
– Move v’ from outies to innies
• Implementation issue: use linear search or PQ?
16
Prim: Data structures
• Three vectors
– Better: a vector of classes or structures!
• For each vertex v, record:
– kv: Has v been visited?
(initially false for all v Î V)
– dv: What is the minimal edge weight to v?
(initially ¥ for all v Î V, except vr = 0)
– pv: What vertex precedes (is parent of) v?
(initially unknown for all v Î V)
17
Prim’s Algorithm
Set starting point dv to 0.
Loop v times (until every kv is true):
1. From the set of vertices for which kv is
false, select the vertex v having the
smallest tentative distance dv.
2. Set kv to true.
3. For each vertex w adjacent to v for
which kw is false, test whether dw is
greater than distance(v,w). If it is,
set dw to distance(v,w) and set pw to v.
18
Implementing Prim’s
• Implement in the order listed:
– 1: Loop over all vertices: find smallest false kv
– 2: Mark kv as true
– 3: Loop over all vertices: update false
neighbors of kv
• Common Mistake: Set the first vertex to
true outside the loop
• Reordering this can result in a simple
algorithm that simply doesn’t work
19
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a F 0 –
b F ¥
c F ¥
d F ¥
e F ¥
f F ¥
4
13
19
20
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a T 0 –
b F 13 a
c F 8 a
d F 1 a
e F ¥
f F ¥
4
13
20
21
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a T 0 –
b F 13 a
c F 5 d
d T 1 a
e F 4 d
f F 5 d
4
13
21
22
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a T 0 –
b F 13 a
c F 3 e
d T 1 a
e T 4 d
f F 2 e
4
13
22
23
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a T 0 –
b F 13 a
c F 3 e
d T 1 a
e T 4 d
f T 2 e
4
13
23
24
v kv dv pv
a T 0 –
b F 13 a
c T 3 e
d T 1 a
e T 4 d
f T 2 e
a
b c
f
d
e
15
8 1
2
53
5
4
13
24
25
a
b c
f
d
e
15
8 1
2
53
5
v kv dv pv
a T 0
b T 13 a
c T 3 e
d T 1 a
e T 4 d
f T 2 e
4
13
25
26
MST This! (Prim’s)
B
C D E
A
5
6 7
1
3
2
4
v kv dv pv
A
B
C
D
E
Using Prim’s; start at node A
29
Complexity – Linear Search
Repeat until every kv is true:
1. From the set of vertices for which kv is
false, select the vertex v having the
smallest tentative distance dv.
2. Set kv to true.
3. For each vertex w adjacent to v for which
kw is false, test whether dw is greater
than distance(v,w). If it is, set dw to
distance(v,w) and set pw to v.
|V| times
O(|V|)O(1)
Most at this vertex: O(|V|). Cost of each: O(1).
30
Prim’s (Heap) Algorithm
Algorithm Prims_Heaps(G, s0)
//Initialize
n = |V|
create_table(n) //stores k,d,p
create_pq() //empty heap
table[s0].d = 0
insert_pq(0, s0)
O(1)
O(V)
O(1)
O(1)
O(1)
31
Prim’s (Heap) Algorithm
O(E)
O(log E)
O(1)
O(1)
O(1 + E/V)
O(1)
O(1)
O(1)
O(1)
O(log E)
while (!pq.isempty)
v0 = getMin() //heap top() & pop()
if (!table[v0].k) //not known
table[v0].k = true
for each vi Î Adj[v0]
distance = weight(v0, vi)
if (distance < table[vi].d)
table[vi].d = distance
table[vi].p = v0
insert_pq(distance, vi)
32
Most at this vertex: O(|V|). Cost of each: O(log(|V|).
Note: Visits every edge once (over all iterations) = O(|E|).
Complexity – Heaps
Repeat until every kv is true:
1. From the set of vertices for which kv is
false, select the vertex v having the
smallest tentative distance dv.
2. Set kv to true.
3. For each vertex w adjacent to v for which
kw is false, test whether dw is greater
than distance(v,w). If it is, set dw to
distance(v,w) and set pw to v.
O(log |V|)O(1)
|V| times
33
Prim’s: Complexity Summary
• O(V2) for the simplest nested-loop
implementation
• O(E log E) with heaps
– Is this always faster?
– Think about the complexity of the PQ version
for dense versus sparse graphs
Data Structures & Algorithms
Prim’s Algorithm
Data Structures & Algorithms
Kruskal’s Algorithm
36
Kruskal’s Algorithm
• Find an MST on edge-weighted,
connected, undirected graphs
• Greedily select edges one by one
and add to a growing sub-graph
• Grows a forest of trees that eventually
merges into a single tree
37
Kruskal’s Algorithm
1. Presort all edges: O(E log E) ≈ O(E log V)
time
2. Try inserting in order of increasing weight
3. Some edges will be discarded so as not to
create cycles
• Initial edges may be disjoint
– Kruskal’s grows a forest (union of disjoint trees)
38
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
39
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
40
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
41
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
42
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
43
a
b c d
e f
15
8 1
2
53
5
4
13
Kruskal’s Algorithm
44
Kruskal: Complexity Analysis
• Sorting takes E log V
– Happens to be the bottleneck of entire algorithm
• Remaining work: a loop over E edges
– Discarding an edge is trivial O(1)
– Adding an edge is easy O(1)
– Most time spent testing for cycles O(?)
– Good news: takes less than log E ≈ log V
• Key idea: if vertices vi and vj are connected, then
a new edge would create a cycle
– Only need to maintain disjoint sets
45
Maintaining Disjoint Sets
• N locations with no connecting roads
• Roads are added one by one
– Distances are unimportant (for now)
– Connectivity is important
• Want to connect cities ASAP
– Redundant roads would slow us down
Q: For two cities k and j, would road (k, j)
be redundant?
A: Use a Union-Find data structure.
46
B
C D E
A
5
6 7
1
3
2
4
MST this! (Kruskal’s)
Weight Edge
1
2
3
4
5
6
7
Vertex A B C D E
Representative
Data Structures & Algorithms
Kruskal’s Algorithm
58
MST Summary
• MST is lowest-cost sub-graph that
– Includes all nodes in a graph
– Keeps all nodes connected
• Two algorithms to find MST
– Prim: iteratively adds closest node to current tree –
very similar to Dijkstra, O(V2) or O(E log V)
– Kruskal: iteratively builds forest by adding minimal
edges, O(E log V)
• For dense G, use the nested-loop Prim variant
• For sparse G, Kruskal is faster
– Relies on the efficiency of sorting algorithms
– Relies on the efficiency of union-find
59
Take-Home MST Quiz
• Prove that Kruskal always finds an MST
• Prove that Prim always finds an MST
• Prove that Prim can start at any vertex
• Hint: revisit in-class MST quiz