Spanning Trees
Bart Massey
Min-Heaps
Two operations: insert, extract-min
Both run in O(lg |H|) time on a given heap H using the same basic approach.
Extract-Min
To extract the minimum element of a min-heap H:
H[1] ←→ H[|H|]
e ← H[|H|]
shorten H by one
downheap(H)
return e
To downheap H:
p ← 1
while 2 p <= |H|
c ← p
if H[2 p] < H[c]
c ← 2 p
if 2 p + 1 <= |H| and H[2 p + 1] < H[c]
c ← 2 p + 1
if c = p
return
H[p] ←→ H[c]
p ← c
Insert
To insert an element e in a min-heap H:
lengthen H by one
H[|H|] ← e
upheap(H)
To upheap H:
c ← |H|
while c div 2 >= 1
p ← c div 2
if H[c] >= H[p]
return
H[p] ←→ H[c]
c ← p
Minimum-Weight Spanning Trees
A spanning tree of a connected undirected graph G = (V, E) is a subset T of E such that
- T is a tree (contains no cycles, is connected)
- vertices(T) = V
A spanning tree T on an edge-weighted graph G is minimum-weight if the sum of weights of edges of T is minimal over all possible spanning trees of G
Motivation: Minimum-cost road network. Given all possible routes between cities, pick a set that minimizes the total cost of connecting all the cities (with intersections only in cities)
- Minimizes build cost, not travel time, nor min travel time
MWST: Prim's Algorithm
Idea: Keep adding the cheapest frontier edge to a spanning subtree.
PRIM'S ALGORITHM To find a MWST for an edge-weighted connected graph G = (V, E) T ← empty set S ← empty set Q ← empty min-heap of edges with edge-weight priority insert some vertex v from V into S insert all edges impinging on v into Q while S is a proper subset of V extract min-weight edge e from Q if both vertices of e are in S continue insert e into T let v be the vertex of e not in S insert v into S insert all edges impinging on v into Q return TCorrectness: Algorithm must complete. When it completes, it is guaranteed that the output will be a spanning tree of G. Optimality is trickier: Imagine that some MWST T' for G would not have been output by the algorithm: instead some larger-weight spanning tree T is output. Now, stop the algorithm at the first point where the edge selection for T does not match the choice of T'. By assumption, T' is optimal, so the weight of the subtree covered so far is optimal, and the weight of the remaining subtree of T' is going to be optimal. This means that the algorithm needs to make a mistake at this point in connecting the two subtrees: but the algorithm chooses a smallest connector of the subtrees. Thus, T' cannot be smaller than T.
Cost: O(|E| lg |V|), since each processed edge involves an extraction and a bounded number of insertions from the heap.
Union-Find (Disjoint-Set)
Want to keep track of which vertices of a graph being built are connected.
Idea: Keep an "upside-down tree" as vertices are added. Make each added vertex point to its parent.
Now the root node of this tree is a "representative" of the whole collection of connected vertices. If two nodes point to the same root, they are in the same component.
Can "pull up" a tree during lookup to make the lookups really cheap.
MWST: Kruskal's Algorithm
Idea: Keep connecting disjoint subtrees with minimum-weight edges.
KRUSKAL'S ALGORITHM To find a MWST for an edge-weighted connected graph G = (V, E) T ← empty set for v in V init connected[v] to v for e in E in lightest to heaviest order if both vertices of e are in the same component continue insert e into T join components of vertices return TCorrectness: Makes exactly one pass, so terminates. Builds a spanning tree. Optimal by induction on tree size. Base case: builds smallest trees connecting individual vertices. Inductive case: assume the algorithm selects e to connect T1 and T2p producing T. T1 and T2 are optimal subtrees by assumption. e is the minimum-weight edge in the graph that can connect T1 and T2, so T is also optimal.
Cost: O(|E| lg |E2|) = O(|E| lg |V|) when union-find is faster than log time (it is).