Function kruskal 

pub fn kruskal<G>(graph: &G) -> Option<SpanningTree>
where
    G: Graph<Weight = f64>,

Computes a Minimum Spanning Tree using Kruskal’s algorithm.

Kruskal’s sorts all edges by weight then greedily adds the cheapest edge that connects two previously disconnected components, using a DisjointSet to detect cycles in O(α(n)) per edge.

Works on both directed and undirected graphs. For directed graphs, edges are treated as undirected (the MST is of the underlying undirected graph).

Returns

Some(SpanningTree) if the graph is connected (a spanning tree exists), or None if the graph is disconnected or empty.

Complexity

O(E log E) dominated by sorting.

Examples

use graph_core::{AdjacencyList, Graph};
use graph_spanning::kruskal;

//   1       3
// A --- B ----- C
//  \         /
//   ----2----
let mut g: AdjacencyList<&str> = AdjacencyList::undirected();
let a = g.add_node("A");
let b = g.add_node("B");
let c = g.add_node("C");
g.add_edge(a, b, 1.0).unwrap();
g.add_edge(b, c, 3.0).unwrap();
g.add_edge(a, c, 2.0).unwrap();

let mst = kruskal(&g).unwrap();
assert_eq!(mst.edges.len(), 2);    // V-1 edges
assert_eq!(mst.total_weight, 3.0); // cheapest: A-B(1) + A-C(2)