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 input weighted undirected graph.compare: A function that compares two edge weights.
Examples
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(1, 2, 5)
...> |> Yog.add_edge_ensure(2, 3, 10)
...> |> Yog.add_edge_ensure(1, 3, 15)
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}]