Minimum Cost Spanning Trees
CSC263 Tutorial 10
Minimum cost spanning tree (MCST) • What is a minimum cost spanning tree?
– Tree
• No cycles; equivalently, for each pair of nodes u and v,
there is only one path from u to v – Spanning
• Contains every node in the graph – Minimum cost
• Smallest possible total weight of any spanning tree
Minimum cost spanning tree (MCST) • Let’s think about simple MCSTs on this graph:
a1b
5 24
c3d
Minimum cost spanning tree (MCST) • Black edges and nodes are in T
• Is T a minimum cost spanning tree? a1b
c3d • Not spanning; d is not in T.
5 24
Minimum cost spanning tree (MCST) • Black edges and nodes are in T
• Is T a minimum cost spanning tree? a1b
c3d • Not a tree; has a cycle.
5 24
Minimum cost spanning tree (MCST) • Black edges and nodes are in T
• Is T a minimum cost spanning tree? a1b
5 24
c3d
• Not minimum cost; can swap edges 4 and 2.
Minimum cost spanning tree (MCST) • Which edges form a MCST?
a1ba1b 33
4242
c3dc3d
Quick Quiz
• IfwebuildaMCSTfromagraphG=(V,E), how may edges does the MCST have?
• When can we find a MCST for a graph?
An application of MCSTs
• Electronic circuit designs (from Cormen et al.)
– Circuits often need to wire together the pins of several components to make them electrically equivalent.
– To connect n pins, we can use n – 1 wires, each connecting two pins.
– Want to use the minimum amount of wire.
– Model problem with a graph where each pin is a node, and every possible wire between a pair of pins is an edge.
A few other applications of MCSTs
• Planning how to lay network cable to connect several locations to the internet
• Planning how to efficiently bounce data from router to router to reach its internet destination
• Creating a 2D maze (to print on cereal boxes, etc.)
Building a MCST
• Prim’s algorithm takes a graph G = (V, E)
and builds an MCST T
• PrimMCST(V, E)
In the book’s terminology, we find a light edge crossing the cut (T, V-T)
– Pick an arbitrary node r from V
– Add r to T
– While T contains < |V| nodes
• Find a minimum weight edge (u, v)
The book proves that adding |V|-1 such edges will create a MCST
where ∈ and ∉ • AddnodevtoT
nodes ∉ • Black: in T
e 10
g 11
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
i 7
a 1 b
12 246
5
hj
c3d
8
14
nodes ∉ • Black: in T
e 10
g 11
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
i 7
a 1 b
12 246
5
h j
c3d
8
14
nodes ∉ • Black: in T
e 10
g 11
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
i 7
a 1 b
12 246
5
h j
c3d
8
14
nodes ∉ • Black: in T
e 10
g 11
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
i
a 1 b
7
12 246
5
h j
c3d
8
14
nodes ∉ • Black: in T
e 10
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
a 1 b
11
7
12 246
5
h j
c3d
8
14
nodes ∉ • Black: in T
e 10
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
a 1 b 5
11
7
12 246
c3d
8
14
h j
nodes ∉ • Black: in T
e 10
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
a 1 b 5
11
7
12 246
c3d
8
14
h j
nodes ∉ • Black: in T
e 10
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
a 1 b 5
11
7
12 246
c3d
8
14
h j
nodes ∉ • Black: in T
e 10
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
a 1 b 5
11
7
12 246
c3d
8
14
h j
nodes ∉ • Black: in T
e 10
a 1 b
g
i
Running Prim’s algorithm
• Start at an arbitrary node, say, h. • Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
12 246
5
h j
c3d
8
11
7
14
nodes ∉ • Black: in T
e 10
a 1 b
g
i
• Minimum Cost: 47
c3d
Running Prim’s algorithm
• Start at an arbitrary node, say, h.
• Blue: not visited yet
• Red: edges from 9 nodes ∈ to
f
9 679
12 246
5
h j
8
11
7
14
Implementing Prim’s Algorithm • Recall the high-level algorithm:
• PrimMCST(V, E)
– Pick an arbitrary node r from V
– Add r to T
– While T contains < |V| nodes
• Find a minimum weight edge (u, v)
How can we do this efficiently?
where ∈ and ∉ • AddnodevtoT
Finding lots of minimums? Use a priority queue!
Adding a priority queue
• What should we store in the priority queue?
– Edges
– From nodes in T
to nodes not in T
• What should we use as the key of an edge?
– Weight of the edge
Prim’s Algorithm with a priority queue
• PrimMCST(V, E, r)
– For each u in V: inTree[u] = false, parent[u] = nil
where r is any arbitrary starting node – Q := new priority queue
– inTree[r] = true, parent[r] = r
– Add every edge that touches r to Q
– While Q is not empty
• Do Q.Extract-Min to get edge e = (u, v) • If not inTree[v] then
– inTree[v] = true, parent[v] = u
– Add every edge that touches v to Q
Small optimization
• PrimMCST(V, E, r)
– Q := new priority queue
– For each u in V: inTree[u] = false, parent[u] = nil
– inTree[r] = true, parent[r] = r
– Add every edge that touches r to Q
– While Q is not empty
• Do Q.Extract-Min to get edge e = (u, v) • If not inTree[v] parent[v] = nil then
– inTree[v] = true, parent[v] = u
– Add every edge that touches v to Q
Θ(|E| log |E|)
Θ(log |E|) Θ(|adj(v)| log |E|)
Analysis of running time
Θ(|V|) Θ(|adj(r)| log |E|)
• O(|E| log |E|) = O(|E| log (|V|2)) • = O(|E| 2 log |V|)
• = O(|E| log |V|)
Java Implementation - 1
Java Implementation - 2
0 9
An example input
14 8
1293
10 6
7 41511 7
12 246
5
67
839
9
Java Implementation - 3
Java Implementation - 4 • Outputting the answer:
• The answer:
• What does this look like?
Recall: the root is its own parent.
Recall our earlier solution by hand:
Drawing the answer
10 6
9
14 8
0
1293
7 41511 7
12 246
5
67
839
9
Fun example: generating 2D mazes
• Prim’s algorithm maze building video
• How can we use Prim’s algorithm to do this?
1. Create a graph that is a regular m x n grid.
2. Set all edge weights to random values!
3. Run Prim’s algorithm starting from any node.
Fun example: generating 2D mazes • After Prim’s, we end up with something like: