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

pub fn min_spanning_tree<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Graph<N, E, Undirected, Ix> where E: Clone + PartialOrd<E>, Ix: IndexType, N: Clone, Ty: EdgeType

Compute a minimum spanning tree of a graph.

Treat the input graph as 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.