Minimum spanning tree

Input

1. An undirected graph [math]\displaystyle{ G = (V,E) }[/math], not necessarily connected.
2. An edge length [math]\displaystyle{ l(e) \in \mathbb{R}_0^+ }[/math] for each edge [math]\displaystyle{ e \in E }[/math].

Output

An undirected tree [math]\displaystyle{ T= (V,E_F) }[/math] such that [math]\displaystyle{ E_T \subseteq E }[/math].

Objective

Minimize: [math]\displaystyle{ \sum{}{}_{e \in E_F}l(e) }[/math].

Complexity

Polynomial.

Known algorithms

Prim