Transcript Minimum Spanning Trees - Baylor School of Engineering

Minimum Spanning
Trees
Easy
Terms



Node
Edge
Cut



Cut respects a set of edges
Light Edge
Minimum Spanning Tree
Generic Algorithm
1.
Start with an empty set of edges.
2.
Continuously add only edges that are part of
a minimum spanning tree
3.
Stop when we have a minimum spanning
tree.
Kruskal’s Algorithm
3.
Find the smallest edge in the graph.
If it connects two unconnected sets, add it.
Repeat for each edge.

What are the optimal data structures?

O( E lg V)
1.
2.


E = # edges
V = # nodes (vertices)
Prim’s Algorithm
1.
2.
3.


Start with a set of 1 nodes: V and empty set
of edges A
Pick a light edge and add it to A.
Repeat until all nodes are in V.
Best Data Structures?
O(E lg V) or O(E+V lg V)
Other Algorithms

Borůvka's algorithm, O( E lg V )

Bernard Chazelle, O( E α(V))

Randomized, expected O(E)

Karger, Klein, and Tarjan
Distributed MST
LAN 1
B3
B2
B1
LAN 3
B4
LAN 2