CS Wiki | Cedric Schwyter

Minimum Spanning Trees (MSTs)

Minimum Spanning Trees (MSTs)
General
Boruvka’s Algorithm
Kruskal’s Algorithm
Prim’s Algorithm

Minimum Spanning Trees (MSTs)

General

A minimum spanning tree for a graph $G = (V, E)$ has the following defining properties:

it contains all $v \in V$
it does not contain any cycles

📖 Let $G = (V, E)$ be a weighted graph with nonnegative weights ( $\forall e \in E w (e) \geq 0$ ) such that all edge weights are different ( $\forall e \neq = e^{'}$ in $E$ , $w (e) \neq = w (e^{'})$ ). Then the minimum spanning tree of $G$ is unique.

Boruvka’s Algorithm

Runtime

$O ((∣ V ∣ + ∣ E ∣) \cdot lo g ∣ V ∣)$

Pseudocode

Python/minimum_spanning_tree_boruvka.py at master · TheAlgorithms/Python

Further Resources

Borůvka’s algorithm - Wikipedia

Kruskal’s Algorithm

Runtime

$O ((∣ V ∣ + ∣ E ∣) \cdot lo g ∣ V ∣)$

Pseudocode

Python/minimum_spanning_tree_kruskal.py at master · TheAlgorithms/Python

Further Resources

Kruskal’s algorithm - Wikipedia

Prim’s Algorithm

Runtime

$O ((∣ V ∣ + ∣ E ∣) \cdot lo g ∣ V ∣)$

Pseudocode

Python/minimum_spanning_tree_prims.py at master · TheAlgorithms/Python

Further Resources

Prim’s algorithm - Wikipedia

This project is maintained by D3PSI