Skip to content

Minimum Spanning Trees

April 4, 2013

Definition of a minimum spanning tree (MST): a fully connected path through a graph, consisting of minimum weight edges, with no cycles (acyclic).

Cut property: for any graph cut, the crossing edge of minimum weight is in the MST. This property is used in the Greedy MST algorithm.

Kruskal’s algorithm – O(E log E). Algorithm is simply sort the edges by weight. Add all edges in ascending order of weight unless they cause a cycle.

Prim’s algorithm – O(E log E). Start with a vertex in a tree T. Add an edge at a time always adding the smallest edge connected to tree T.

Is there a linear time worst case solution? http://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm

Euclidean MST can be done in O(N log N).

Advertisements

From → Algorithms

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: