minimum spanning tree

(idea) by Hykin (2.7 mon) Sat Sep 01 2001 at 2:12:45
Given a undirected weighted graph G, the minimum spanning tree (MST) is the spanning tree such that the sum of the weights of edges used is minimized.

There are two well-studied algorithm for computing minimum spanning trees: Prim's algorithm and Kruskal's algorithm. Both are O(E lg V) on sparse graphs. There do exist linear time MST algorithms, but they remain quite complex.

del.icio.us Furl Facebook Digg StumbleUpon Reddit   (I like it!)
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.