Minimum Spanning Trees (18)
Michael L. Littman
November 5th, 1998
MINIMUM SPANNING TREES
Types of Graphs
Water For Everyone
Mathematical Abstraction
Simple Verification
Optimization Verification
FINDING MINIMUM SPANNING TREES
Design Ideas
Greedy Approach
Cuts
Greedy-Grow Lemma
Correctness of G
ENERIC
-MST
Efficient Implementation
KRUSKAL'S ALGORITHM
Recap
Algorithm
Correctness
Implementation
Simple Implementation: DFS
Better Implementation
Implementation
Running Time: Bound One
Running Time: Tighter Bound
FAST UNION-FIND
Quick Aside
Clever Data Structure
Culture
Next:
MINIMUM SPANNING TREES
