Function petgraph::algo::min_spanning_tree[−][src]

pub fn min_spanning_tree<G>(g: G) -> MinSpanningTree<G>ⓘ
Notable traits for MinSpanningTree<G>
impl<G> Iterator for MinSpanningTree<G> where
    G: IntoNodeReferences + NodeIndexable,
    G::NodeWeight: Clone,
    G::EdgeWeight: PartialOrd,     type Item = Element<G::NodeWeight, G::EdgeWeight>;
 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.