# Function petgraph::algo::min_spanning_tree

source · ```
pub fn min_spanning_tree<G>(g: G) -> MinSpanningTree<G> ⓘwhere
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
G: IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
```

## Expand description

[Generic] Compute a *minimum spanning tree* of a graph.

The input graph is treated as if undirected.

Using Kruskal’s algorithm with runtime **O(|E| log |E|)**. We actually
return a minimum spanning forest, i.e. a minimum spanning tree for each connected
component of the graph.

The resulting graph has all the vertices of the input graph (with identical node indices),
and **|V| - c** edges, where **c** is the number of connected components in `g`

.

Use `from_elements`

to create a graph from the resulting iterator.