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.

MST Feature

Requires the mst feature, and the edge weight 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));