Spanning Trees

A spanning tree connects all vertices with the minimum number of edges (V-1) and no cycles. A minimum spanning tree (MST) minimizes total edge weight.

Algorithm	Complexity	When to use
Kruskal	O(E log E)	MST on sparse graphs. Sorts edges by weight, adds them greedily.
Prim	O((V + E) log V)	MST on dense graphs. Grows a tree from a single root vertex.
Random Spanning Tree	O(V * E) expected	Uniformly random spanning tree. Uses loop-erased random walks.
Common Spanning Trees	Exponential	Enumerates spanning trees common to two graphs.

Algorithm

Complexity

When to use

Kruskal

O(E log E)

MST on sparse graphs. Sorts edges by weight, adds them greedily.

Prim

O((V + E) log V)

MST on dense graphs. Grows a tree from a single root vertex.

Random Spanning Tree

O(V * E) expected

Uniformly random spanning tree. Uses loop-erased random walks.

Common Spanning Trees

Exponential

Enumerates spanning trees common to two graphs.

For MST, use Kruskal when E is small relative to V (sparse), Prim when the graph is dense. Both produce the same MST (or one of several if weights are not unique).

Edit this Page