Other MST Algorithms
Boruvka's algorithm … complexity O(E·log V)
- the oldest MST algorithm
- start with V separate components
- join components using min cost links
- continue until only a single component
Karger, Klein, and Tarjan … complexity O(E)
- based on Boruvka, but non-deterministic
- randomly selects subset of edges to consider
- for the keen, here's the paper describing the algorithm
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}