Simplistic Minimum Spanning Tree in Numpy [update]
![Image](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3xLXzV-_9FDMrWYvkskCGUX-Fvlw7SUJ1p3nJHCaVFRY_auUgl3CrQQvRYO4Qqj3EbTV5H7dxythCAcbAS7SKCmoaVMHs4sPqnIsnMq53F1AaYxNDJXuDM4gq8QUxuiC8nAn7btb0Mo8/s320/mst.png)
I started working with spanning trees for euclidean distance graphs today. The first think I obviously needed to do was compute the spanning tree. There are MST algorithms in Python, for example in pygraph and networkx . These use their native graph formats, though, which would have meant I'd have to construct a graph from my point set. I didn't see a way on how to do this and set the edge weights without iterating over all edges. That would probably take longer than the computation of the MST, so I decided to do my own small implementation using numpy. This is an instantiation of Prim's algorithm based on numpy matrices. The input is a dense matrix of distances, the output a list of edges. It is not as pretty as I would have hoped but still reasonably short. If any one has suggestions how to make this prettier, I'd love that. [edit] Using line_profiler I had a quick look a the code and made some minor improvements. It's now significantly faster than net