Borůvka's algorithm for finding the Minimum Spanning Tree (MST).
Borůvka's algorithm works in stages. In each stage, for each connected component, it finds the minimum-weight edge that connects that component to a different component. All such edges are added to the MST simultaneously. This process continues until only one component remains or no more edges can be added.
Performance
- Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices.
- Space Complexity: O(V) for the disjoint set and tracking component edges.
Summary
Functions
Computes the Minimum Spanning Tree (MST) using Borůvka's algorithm.
Functions
@spec compute(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) :: {:ok, Yog.MST.Result.t()}
Computes the Minimum Spanning Tree (MST) using Borůvka's algorithm.
Returns {:ok, %Yog.MST.Result{}} containing the edges of the MST.
Parameters
graph: The undirected graph to process.compare: A comparison function(a, b -> :lt | :eq | :gt)used to order edge weights.
Examples
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 10}, {2, 3, 5}, {1, 3, 20}])
iex> {:ok, result} = Yog.MST.Boruvka.compute(graph, &Yog.Utils.compare/2)
iex> result.total_weight
15