Kruskal's algorithm for finding the Minimum Spanning Tree (MST).
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning forest of an undirected edge-weighted graph. It sorts all edges by weight and adds them one by one if they don't form a cycle, using a Disjoint Set Union (DSU) data structure for efficient connectivity checks.
Performance
- Time Complexity: O(E log E) or O(E log V) due to sorting, where E is the number of edges and V is the number of vertices.
- Space Complexity: O(V) to store the disjoint set.
Summary
Functions
Computes the Minimum Spanning Tree (MST) using Kruskal's algorithm.
Functions
@spec compute(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) :: {:ok, Yog.MST.Result.t()}
Computes the Minimum Spanning Tree (MST) using Kruskal'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.Kruskal.compute(graph, &Yog.Utils.compare/2)
iex> result.total_weight
15
iex> Enum.map(result.edges, fn e -> {e.from, e.to} end) |> Enum.sort()
[{1, 2}, {2, 3}]