Review:

Graph G=(V,E)

Subgraph G'=(V',E'): V' V, E' E (note: graphs can be disconnected)

If G' contains no cycles then G'=T is a tree.

T= (V',E') is a spanning tree of G if V'= V

The right two are spanning trees of the graph on the left:

Minimum Cost Spanning Trees

The cost of a spanning tree is the sum of the costs (weights) of the edges in the spanning tree.

A minimum-cost spanning tree is a spanning tree of least cost.

Cost on edges C: E -> R⁺

^{(i.e., is a function from the edges to the real numbers)}

Spanning tree of minimum cost

Application: circuit equations, broadcasting

n nodes spanning tree must contain n-1 edges

Greedy Strategy

Edges included so far form a forest (Kruskal) (page 726)

Edges included so far form a tree (Prim) (page 731)

Kruskal

Before		After
Step 1	Step 2	Step 3	Step 4

See also Figure 18.11

Use Union and Find to convert a forest of n isolated nodes to a spanning tree

note: link between nodes in Union-Find data structure not necessarily same as edges in spanning tree. We want no cycles in this construction.

Procedure: Kruskal T <- {} Sort edges by nondecreasing cost Put in first edge ... while T contains less than n-1 edges do (v,w) <- next edge; delete (v,w) from edges; i <- Find(v); j <- Find(w) if i != j then { T <- T U (v,w) ; Union(i,j); } // parent of i becomes j // if i=j reject since would cause loop end end Kruskal

-> method Union (i,j) parent (i) <- j // i and j must be root nodes end Union -> method Find (i) // find root of tree containing i // j <- i while parent(j) != 0 do // go through loop until parent is root j<- parent (j) end return (j) end Find

Time: (page 730)

e= |E|, n= |V|

Sorting: eloge
Text notes that "not essential to sort...so long as the next edge can be determined easily" - suggest a heap (O(log e) for next to consider and O(e) to build the heap.)

The rest of the algorithm then takes at most 2e Finds and (n-1) Unions. ( time)
so this part of the algorithm is sightly more than 0(n + e)

Adding up all parts get O(n + eloge). If each node has even one edge then e > n. Hence bounded mostly by the sort -- O(eloge)

Theorem: Procedure Kruskal produces a minimum cost spanning tree.

Proof: (page 729 also) Uses transformation and contradiction

Proof:

Let T be tree constructed by algorithm
Let T' be a min cost spanning tree

If T=T' than Done ... we will transform to make it so


Let e be an edge of min. cost in T - T'.      (ones Kruscal used but they didn't)
Let T_<e denote the edges in T of cost < c(e)      (anybody smaller not used?)
If all edges in T_<e contained in T' then T' U {e} creates a unique cycle.

Let e' be an edge on this cycle such that e' T' - T

visual
Claim: c(e') > c(e)
Proof: suppose c(e') < c (e)

then, at some stage in the construction of T, Kruskal must have considered e' for inclusion (i.e., T_<e U e' or not)

e' must have been rejected because it caused a cycle with edges in T_<e.
but T_<e T'
therefore T' contains a cycle

Contradiction of theirs being minimum.       Done .

Consider T'' = T' U {e} - {e'}

c(T'') < c(T')

by repeated transformation, T' can be converted to T without increasing cost.
REALLY DONE. Hence T is a minimum cost spanning tree.

Before			After

See also Figure 18.14

Procedure Prim (k,l) = minimum Cost edge T = (k,l) for i =1 to n-2 do (k,l) = edge of minimum cost over all edges, one of whose end points lies in T and the other does not T = T U (k,l) end end Prim

Prim 0(n²)

Again, note that if # of e is close to n² -- almost complete graph

Kruskal O(e log e)

e<< n² or e ~= n - a sparse graph

note: if a lot of edges Kruscal's looks like n² log n²

This, or even, n² log n is worse than just n²

If # edges << n² (i.e. sparse)

use Kruskal 0(e log e)

otherwise use Prim's 0(n²)

Use Figure 18.17 to try things.

And check out java demos for Prim and Kruscal
(A (6,10) graph means 6 vertices and 10 edges)