Minimum Spanning Tree (MST)

Minimum Spanning Tree algorithms find a subset of edges that connect all nodes in a graph with the minimum possible total edge weight, without forming any cycles.

Algorithms

Prim's Algorithm

Prim's algorithm grows the MST from a starting node, adding the cheapest edge at each step.

use graphina::core::types::{Graph, NodeId};
use graphina::mst::prim_mst;
use ordered_float::OrderedFloat;

fn main() {
    let mut g = Graph::<i32, OrderedFloat<f64>>::new();
    let n1 = g.add_node(1);
    let n2 = g.add_node(2);
    let n3 = g.add_node(3);

    g.add_edge(n1, n2, OrderedFloat(1.0));
    g.add_edge(n1, n3, OrderedFloat(3.0));
    g.add_edge(n2, n3, OrderedFloat(2.0)); // Cheaper path via n2

    let (mst_edges, total_weight) = prim_mst(&g).unwrap();
    println!("Total Weight: {}", total_weight);
}

Kruskal's Algorithm

Kruskal's algorithm sorts all edges by weight and adds them if they don't form a cycle.

use graphina::mst::kruskal_mst;

let (mst_edges, total_weight) = kruskal_mst(&g).unwrap();

Borůvka's Algorithm (Parallel)

A parallel implementation that is efficient for large graphs. It works by finding the minimum weight edge incident to each component in parallel.

Parallel Feature

Requires the parallel feature and W must implement Send + Sync.

use graphina::mst::boruvka_mst;

let (mst_edges, total_weight) = boruvka_mst(&g).unwrap();

Weight Type Requirements

Edge weights W must implement Ord. For floating point numbers, use OrderedFloat or a similar wrapper to provide total ordering.

use ordered_float::OrderedFloat;
let mut g = Graph::<i32, OrderedFloat<f64>>::new();
let u = g.add_node(1);
let v = g.add_node(2);
g.add_edge(u, v, OrderedFloat(1.5));