Trait MSTAlgorithms 

pub trait MSTAlgorithms<R: Runtime> {
    // Required method
    fn minimum_spanning_tree(
        &self,
        graph: &GraphData<R>,
    ) -> Result<MSTResult<R>>;
}

Minimum spanning tree algorithms.

Finds the subset of edges that connects all nodes with minimum total weight. Only meaningful for undirected graphs.

Required Methods

fn minimum_spanning_tree(&self, graph: &GraphData<R>) -> Result<MSTResult<R>>

Compute the minimum spanning tree using Kruskal’s algorithm.

Sorts edges by weight and greedily adds edges that don’t form cycles (using union-find). Sequential algorithm.

Complexity

O(E log E) for sorting + O(E α(V)) for union-find.

Errors

Returns error if the graph is directed.

Implementations on Foreign Types

impl MSTAlgorithms<CpuRuntime> for CpuClient

fn minimum_spanning_tree( &self, graph: &GraphData<CpuRuntime>, ) -> Result<MSTResult<CpuRuntime>>

Implementors