scipy/scipy — pull request #284 by jtaylor (2012-08-08 17:05:11+00:00)
Title: Adapted Union-Find in MST code to use Rank Heuristic and Path Compression.

* The minimum spanning tree test case now actually tests to make sure a known (trivial) MST is found.
* The MST code in csgraph used a simple disjoint-set forest (http://en.wikipedia.org/wiki/Disjoint-set_data_structure). I have adapted it to use the rank-heuristic with path compression to achieve nearly constant time (see wikipedia) amortized union/find operations.
* I achieve roughly an order of magnitude speedup on large dense matrices.