Function petgraph::algo::min_spanning_tree::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.