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?

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


From → Algorithms

Leave a Comment

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: