CS计算机代考程序代写 Java algorithm Minimum Cost Spanning Trees

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: