Minimum spanning trees Input: A connected, undirected graph G=(V,E) with weight function w: E>R For simplicity assume that all edge weights are distinct (CLRS coVers the general case. Output: a spanning tree T-a tree that connects all vertices-of minimum weight W(7)= (l2y) (u,v)∈eT c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.5 Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weight function w : E → R. • For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ∑ ∈ = u v T w T w u v ( , ) ( ) ( , ). Output: A spanning tree T — a tree that connects all vertices — of minimum weight: