# Minimum Spanning Tree problem (MST)
Last edited: 2023-11-11
# Statement
Minimum Spanning Tree problem
Given an undirected graph $G = (V,E)$ with weights $w: E \rightarrow \mathbb{R}$ can you find a spanning tree $T = (V, E')$ with minimum weight
$$w(T) = \sum_{e \in E'} w(e).$$# Solutions
- Kruskal’s algorithm
- It takes $O(\vert E \vert \log(\vert V \vert))$.
- Prim’s algorithm
- It takes $O((\vert V \vert + \vert E \vert) \log(\vert V \vert))$.