Repository: TheAlgorithms/Java
Pull request #4964 (2023-11-19 18:32:59)

Added Boruvka's algorithm to find Minimum Spanning Tree
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

This PR consists of an implementation for the Borůvka's algorithm (https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm) for finding a MST in graphs.

<!-- For completed items, change [ ] to [x] -->

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized it.
- [X] All filenames are in PascalCase.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [X] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

itakurah: @siriak added JUnit tests.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 6de51661..89f08c27 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -19,6 +19,7 @@
             * [PowerSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/PowerSum.java)
             * [WordSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/WordSearch.java)
           * bitmanipulation
+            * [BitSwap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/BitSwap.java)
             * [HighestSetBit](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/HighestSetBit.java)
             * [IndexOfRightMostSetBit](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IndexOfRightMostSetBit.java)
             * [IsEven](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsEven.java)
@@ -81,6 +82,8 @@
               * [LFUCache](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java)
               * [LRUCache](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java)
               * [MRUCache](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java)
+            * crdt
+              * [GCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GCounter.java)
             * disjointsetunion
               * [DisjointSetUnion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java)
               * [Node](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java)
@@ -90,6 +93,7 @@
               * [A Star](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/A_Star.java)
               * [BellmanFord](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/BellmanFord.java)
               * [BipartiteGrapfDFS](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/BipartiteGrapfDFS.java)
+              * [BoruvkaAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithm.java)
               * [ConnectedComponent](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/ConnectedComponent.java)
               * [Cycles](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/Cycles.java)
               * [DIJSKSTRAS ALGORITHM](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/graphs/DIJSKSTRAS_ALGORITHM.java)
@@ -239,6 +243,7 @@
             * [SubsetCount](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/SubsetCount.java)
             * [SubsetSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java)
             * [Sum Of Subset](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/Sum_Of_Subset.java)
+            * [Tribonacci](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/Tribonacci.java)
             * [UniquePaths](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/UniquePaths.java)
             * [WildcardMatching](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java)
             * [WineProblem](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/WineProblem.java)
@@ -281,7 +286,9 @@
             * [FFT](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FFT.java)
             * [FFTBluestein](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FFTBluestein.java)
             * [FibonacciJavaStreams](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FibonacciJavaStreams.java)
+            * [FibonacciLoop](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FibonacciLoop.java)
             * [FibonacciNumberCheck](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FibonacciNumberCheck.java)
+            * [FibonacciNumberGoldenRation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java)
             * [FindKthNumber](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FindKthNumber.java)
             * [FindMax](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FindMax.java)
             * [FindMaxRecursion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/FindMaxRecursion.java)
@@ -307,6 +314,7 @@
             * [LongDivision](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/LongDivision.java)
             * [LucasSeries](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/LucasSeries.java)
             * [MagicSquare](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/MagicSquare.java)
+            * [MatrixRank](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/MatrixRank.java)
             * [MatrixUtil](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/MatrixUtil.java)
             * [MaxValue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/MaxValue.java)
             * [Means](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/Means.java)
@@ -359,6 +367,7 @@
           * misc
             * [ColorContrastRatio](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/ColorContrastRatio.java)
             * [InverseOfMatrix](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/InverseOfMatrix.java)
+            * [MapReduce](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MapReduce.java)
             * [matrixTranspose](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/matrixTranspose.java)
             * [MedianOfMatrix](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfMatrix.java)
             * [MedianOfRunningArray](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java)
@@ -564,6 +573,7 @@
             * [PowerSumTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PowerSumTest.java)
             * [WordSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/WordSearchTest.java)
           * bitmanipulation
+            * [BitSwapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/BitSwapTest.java)
             * [HighestSetBitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/HighestSetBitTest.java)
             * [IndexOfRightMostSetBitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IndexOfRightMostSetBitTest.java)
             * [IsEvenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsEvenTest.java)
@@ -605,9 +615,12 @@
               * [LFUCacheTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java)
               * [LRUCacheTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/caches/LRUCacheTest.java)
               * [MRUCacheTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/caches/MRUCacheTest.java)
+            * crdt
+              * [GCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GCounterTest.java)
             * disjointsetunion
               * [DisjointSetUnionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java)
             * graphs
+              * [BoruvkaAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java)
               * [HamiltonianCycleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java)
               * [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
               * [TarjansAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithmTest.java)
@@ -666,6 +679,7 @@
             * [OptimalJobSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/OptimalJobSchedulingTest.java)
             * [PartitionProblemTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/PartitionProblemTest.java)
             * [SubsetCountTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/SubsetCountTest.java)
+            * [TribonacciTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/TribonacciTest.java)
             * [UniquePathsTests](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/UniquePathsTests.java)
             * [WildcardMatchingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java)
           * geometry
@@ -700,7 +714,9 @@
             * [FastInverseSqrtTests](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FastInverseSqrtTests.java)
             * [FFTTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FFTTest.java)
             * [FibonacciJavaStreamsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FibonacciJavaStreamsTest.java)
+            * [FibonacciLoopTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FibonacciLoopTest.java)
             * [FibonacciNumberCheckTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FibonacciNumberCheckTest.java)
+            * [FibonacciNumberGoldenRationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FibonacciNumberGoldenRationTest.java)
             * [FindMaxRecursionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FindMaxRecursionTest.java)
             * [FindMaxTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FindMaxTest.java)
             * [FindMinRecursionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/FindMinRecursionTest.java)
@@ -719,6 +735,7 @@
             * [LiouvilleLambdaFunctionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/LiouvilleLambdaFunctionTest.java)
             * [LongDivisionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/LongDivisionTest.java)
             * [LucasSeriesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/LucasSeriesTest.java)
+            * [MatrixRankTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/MatrixRankTest.java)
             * [MaxValueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/MaxValueTest.java)
             * [MeansTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/MeansTest.java)
             * [MedianTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/MedianTest.java)
@@ -755,6 +772,7 @@
             * [TwinPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/TwinPrimeTest.java)
             * [VolumeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/VolumeTest.java)
           * misc
+            * [MapReduceTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/misc/MapReduceTest.java)
             * [MedianOfMatrixtest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/misc/MedianOfMatrixtest.java)
             * [MedianOfRunningArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java)
             * [MirrorOfMatrixTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/misc/MirrorOfMatrixTest.java)
@@ -763,6 +781,7 @@
           * others
             * [ArrayLeftRotationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/ArrayLeftRotationTest.java)
             * [BestFitCPUTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/BestFitCPUTest.java)
+            * [BoyerMooreTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/BoyerMooreTest.java)
             * cn
               * [HammingDistanceTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/cn/HammingDistanceTest.java)
             * [ConwayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/ConwayTest.java)
@@ -798,6 +817,7 @@
             * [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
             * [KMPSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/KMPSearchTest.java)
             * [OrderAgnosticBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/OrderAgnosticBinarySearchTest.java)
+            * [PerfectBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/PerfectBinarySearchTest.java)
             * [QuickSelectTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/QuickSelectTest.java)
             * [RabinKarpAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/RabinKarpAlgorithmTest.java)
             * [RecursiveBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/RecursiveBinarySearchTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithm.java b/src/main/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithm.java
new file mode 100644
index 00000000..dcdb08ad
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithm.java
@@ -0,0 +1,217 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Boruvka's algorithm to find Minimum Spanning Tree
+ * (https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm)
+ *
+ * @author itakurah (https://github.com/itakurah)
+ */
+
+final class BoruvkaAlgorithm {
+    private BoruvkaAlgorithm() {
+    }
+
+    /**
+     * Represents an edge in the graph
+     */
+    static class Edge {
+        final int src;
+        final int dest;
+        final int weight;
+
+        Edge(final int src, final int dest, final int weight) {
+            this.src = src;
+            this.dest = dest;
+            this.weight = weight;
+        }
+    }
+
+    /**
+     * Represents the graph
+     */
+    static class Graph {
+        final int vertex;
+        final List<Edge> edges;
+
+        /**
+         * Constructor for the graph
+         *
+         * @param vertex number of vertices
+         * @param edges  list of edges
+         */
+        Graph(final int vertex, final List<Edge> edges) {
+            if (vertex < 0) {
+                throw new IllegalArgumentException("Number of vertices must be positive");
+            }
+            if (edges == null || edges.isEmpty()) {
+                throw new IllegalArgumentException("Edges list must not be null or empty");
+            }
+            for (final var edge : edges) {
+                checkEdgeVertices(edge.src, vertex);
+                checkEdgeVertices(edge.dest, vertex);
+            }
+
+            this.vertex = vertex;
+            this.edges = edges;
+        }
+    }
+
+    /**
+     * Represents a subset for Union-Find operations
+     */
+    private static class Component {
+        int parent;
+        int rank;
+
+        Component(final int parent, final int rank) {
+            this.parent = parent;
+            this.rank = rank;
+        }
+    }
+
+    /**
+     * Represents the state of Union-Find components and the result list
+     */
+    private static class BoruvkaState {
+        List<Edge> result;
+        Component[] components;
+        final Graph graph;
+
+        BoruvkaState(final Graph graph) {
+            this.result = new ArrayList<>();
+            this.components = initializeComponents(graph);
+            this.graph = graph;
+        }
+
+        /**
+         * Adds the cheapest edges to the result list and performs Union operation on the subsets.
+         *
+         * @param cheapest Array containing the cheapest edge for each subset.
+         */
+        void merge(final Edge[] cheapest) {
+            for (int i = 0; i < graph.vertex; ++i) {
+                if (cheapest[i] != null) {
+                    final var component1 = find(components, cheapest[i].src);
+                    final var component2 = find(components, cheapest[i].dest);
+
+                    if (component1 != component2) {
+                        result.add(cheapest[i]);
+                        union(components, component1, component2);
+                    }
+                }
+            }
+        }
+
+        /**
+         * Checks if there are more edges to add to the result list
+         *
+         * @return true if there are more edges to add, false otherwise
+         */
+        boolean hasMoreEdgesToAdd() {
+            return result.size() < graph.vertex - 1;
+        }
+
+        /**
+         * Computes the cheapest edges for each subset in the Union-Find structure.
+         *
+         * @return an array containing the cheapest edge for each subset.
+         */
+        private Edge[] computeCheapestEdges() {
+            Edge[] cheapest = new Edge[graph.vertex];
+            for (final var edge : graph.edges) {
+                final var set1 = find(components, edge.src);
+                final var set2 = find(components, edge.dest);
+
+                if (set1 != set2) {
+                    if (cheapest[set1] == null || edge.weight < cheapest[set1].weight) {
+                        cheapest[set1] = edge;
+                    }
+                    if (cheapest[set2] == null || edge.weight < cheapest[set2].weight) {
+                        cheapest[set2] = edge;
+                    }
+                }
+            }
+            return cheapest;
+        }
+
+        /**
+         * Initializes subsets for Union-Find
+         *
+         * @param graph the graph
+         * @return the initialized subsets
+         */
+        private static Component[] initializeComponents(final Graph graph) {
+            Component[] components = new Component[graph.vertex];
+            for (int v = 0; v < graph.vertex; ++v) {
+                components[v] = new Component(v, 0);
+            }
+            return components;
+        }
+    }
+
+    /**
+     * Finds the parent of the subset using path compression
+     *
+     * @param components array of subsets
+     * @param i          index of the subset
+     * @return the parent of the subset
+     */
+    static int find(final Component[] components, final int i) {
+        if (components[i].parent != i) {
+            components[i].parent = find(components, components[i].parent);
+        }
+        return components[i].parent;
+    }
+
+    /**
+     * Performs the Union operation for Union-Find
+     *
+     * @param components array of subsets
+     * @param x          index of the first subset
+     * @param y          index of the second subset
+     */
+    static void union(Component[] components, final int x, final int y) {
+        final int xroot = find(components, x);
+        final int yroot = find(components, y);
+
+        if (components[xroot].rank < components[yroot].rank) {
+            components[xroot].parent = yroot;
+        } else if (components[xroot].rank > components[yroot].rank) {
+            components[yroot].parent = xroot;
+        } else {
+            components[yroot].parent = xroot;
+            components[xroot].rank++;
+        }
+    }
+
+    /**
+     * Boruvka's algorithm to find the Minimum Spanning Tree
+     *
+     * @param graph the graph
+     * @return list of edges in the Minimum Spanning Tree
+     */
+    static List<Edge> boruvkaMST(final Graph graph) {
+        var boruvkaState = new BoruvkaState(graph);
+
+        while (boruvkaState.hasMoreEdgesToAdd()) {
+            final var cheapest = boruvkaState.computeCheapestEdges();
+            boruvkaState.merge(cheapest);
+        }
+        return boruvkaState.result;
+    }
+
+    /**
+     * Checks if the edge vertices are in a valid range
+     *
+     * @param vertex     the vertex to check
+     * @param upperBound the upper bound for the vertex range
+     */
+    private static void checkEdgeVertices(final int vertex, final int upperBound) {
+        if (vertex < 0 || vertex >= upperBound) {
+            throw new IllegalArgumentException("Edge vertex out of range");
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java
new file mode 100644
index 00000000..b5f75f5e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java
@@ -0,0 +1,191 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.thealgorithms.datastructures.graphs.BoruvkaAlgorithm.Graph;
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+public class BoruvkaAlgorithmTest {
+    @Test
+    public void testBoruvkaMSTV9E14() {
+        List<BoruvkaAlgorithm.Edge> edges = new ArrayList<>();
+
+        edges.add(new BoruvkaAlgorithm.Edge(0, 1, 10));
+        edges.add(new BoruvkaAlgorithm.Edge(0, 2, 12));
+        edges.add(new BoruvkaAlgorithm.Edge(1, 2, 9));
+        edges.add(new BoruvkaAlgorithm.Edge(1, 3, 8));
+        edges.add(new BoruvkaAlgorithm.Edge(2, 4, 3));
+        edges.add(new BoruvkaAlgorithm.Edge(2, 5, 1));
+        edges.add(new BoruvkaAlgorithm.Edge(4, 5, 3));
+        edges.add(new BoruvkaAlgorithm.Edge(4, 3, 7));
+        edges.add(new BoruvkaAlgorithm.Edge(3, 6, 8));
+        edges.add(new BoruvkaAlgorithm.Edge(3, 7, 5));
+        edges.add(new BoruvkaAlgorithm.Edge(5, 7, 6));
+        edges.add(new BoruvkaAlgorithm.Edge(6, 7, 9));
+        edges.add(new BoruvkaAlgorithm.Edge(6, 8, 2));
+        edges.add(new BoruvkaAlgorithm.Edge(7, 8, 11));
+
+        final var graph = new Graph(9, edges);
+        /**
+         * Adjacency matrix
+         *    0   1   2   3   4   5   6   7   8
+         * 0  0  10  12   0   0   0   0   0   0
+         * 1 10   0   9   8   0   0   0   0   0
+         * 2 12   9   0   0   3   1   0   0   0
+         * 3  0   8   0   0   7   0   8   5   0
+         * 4  0   0   3   7   0   3   0   0   0
+         * 5  0   0   1   0   3   0   0   6   0
+         * 6  0   0   0   8   0   0   0   9   2
+         * 7  0   0   0   5   0   6   9   0  11
+         * 8  0   0   0   0   0   0   2  11   0
+         */
+        final var result = BoruvkaAlgorithm.boruvkaMST(graph);
+        assertEquals(8, result.size());
+        assertEquals(43, computeTotalWeight(result));
+    }
+
+    @Test
+    void testBoruvkaMSTV2E1() {
+        List<BoruvkaAlgorithm.Edge> edges = new ArrayList<>();
+
+        edges.add(new BoruvkaAlgorithm.Edge(0, 1, 10));
+
+        final var graph = new Graph(2, edges);
+
+        /**
+         * Adjacency matrix
+         *    0  1
+         * 0  0  10
+         * 1  10  0
+         */
+        final var result = BoruvkaAlgorithm.boruvkaMST(graph);
+        assertEquals(1, result.size());
+        assertEquals(10, computeTotalWeight(result));
+    }
+
+    @Test
+    void testCompleteGraphK4() {
+        List<BoruvkaAlgorithm.Edge> edges = new ArrayList<>();
+        edges.add(new BoruvkaAlgorithm.Edge(0, 1, 7));
+        edges.add(new BoruvkaAlgorithm.Edge(0, 2, 2));
+        edges.add(new BoruvkaAlgorithm.Edge(0, 3, 5));
+        edges.add(new BoruvkaAlgorithm.Edge(1, 2, 3));
+        edges.add(new BoruvkaAlgorithm.Edge(1, 3, 4));
+        edges.add(new BoruvkaAlgorithm.Edge(2, 3, 1));
+
+        final var graph = new Graph(4, edges);
+
+        /**
+         * Adjacency matrix
+         *    0  1  2  3
+         * 0  0  7  2  5
+         * 1  7  0  3  4
+         * 2  2  3  0  1
+         * 3  5  4  1  0
+         */
+        final var result = BoruvkaAlgorithm.boruvkaMST(graph);
+        assertEquals(3, result.size());
+        assertEquals(6, computeTotalWeight(result));
+    }
+
+    @Test
+    void testNegativeVertices() {
+        Exception exception1 = assertThrows(IllegalArgumentException.class, () -> new Graph(-1, null));
+        String expectedMessage = "Number of vertices must be positive";
+        String actualMessage = exception1.getMessage();
+
+        assertTrue(actualMessage.contains(expectedMessage));
+    }
+
+    @Test
+    void testEdgesNull() {
+        Exception exception = assertThrows(IllegalArgumentException.class, () -> new Graph(0, null));
+        String expectedMessage = "Edges list must not be null or empty";
+        String actualMessage = exception.getMessage();
+
+        assertTrue(actualMessage.contains(expectedMessage));
+    }
+
+    @Test
+    void testEdgesEmpty() {
+        Exception exception = assertThrows(IllegalArgumentException.class, () -> new Graph(0, new ArrayList<>()));
+        String expectedMessage = "Edges list must not be null or empty";
+        String actualMessage = exception.getMessage();
+
+        assertTrue(actualMessage.contains(expectedMessage));
+    }
+
+    @Test
+    void testEdgesRange() {
+        // Valid input
+        List<BoruvkaAlgorithm.Edge> validEdges = new ArrayList<>();
+        validEdges.add(new BoruvkaAlgorithm.Edge(0, 1, 2));
+        validEdges.add(new BoruvkaAlgorithm.Edge(1, 2, 3));
+        final var validGraph = new BoruvkaAlgorithm.Graph(3, validEdges);
+        assertEquals(validEdges, validGraph.edges);
+
+        // Edge source out of range
+        Exception exception1 = assertThrows(IllegalArgumentException.class, () -> {
+            List<BoruvkaAlgorithm.Edge> invalidEdges = new ArrayList<>();
+            invalidEdges.add(new BoruvkaAlgorithm.Edge(-1, 1, 2));
+            final var invalidGraph = new BoruvkaAlgorithm.Graph(1, invalidEdges);
+            assertEquals(invalidEdges, invalidGraph.edges);
+        });
+        String expectedMessage1 = "Edge vertex out of range";
+        String actualMessage1 = exception1.getMessage();
+
+        assertTrue(actualMessage1.contains(expectedMessage1));
+
+        // Edge source out of range
+        Exception exception2 = assertThrows(IllegalArgumentException.class, () -> {
+            List<BoruvkaAlgorithm.Edge> invalidEdges = new ArrayList<>();
+            invalidEdges.add(new BoruvkaAlgorithm.Edge(1, 0, 2));
+            final var invalidGraph = new BoruvkaAlgorithm.Graph(1, invalidEdges);
+            assertEquals(invalidEdges, invalidGraph.edges);
+        });
+        String expectedMessage2 = "Edge vertex out of range";
+        String actualMessage2 = exception2.getMessage();
+
+        assertTrue(actualMessage2.contains(expectedMessage2));
+
+        // Edge destination out of range
+        Exception exception3 = assertThrows(IllegalArgumentException.class, () -> {
+            List<BoruvkaAlgorithm.Edge> invalidEdges = new ArrayList<>();
+            invalidEdges.add(new BoruvkaAlgorithm.Edge(0, -1, 2));
+            final var invalidGraph = new BoruvkaAlgorithm.Graph(1, invalidEdges);
+            assertEquals(invalidEdges, invalidGraph.edges);
+        });
+        String expectedMessage3 = "Edge vertex out of range";
+        String actualMessage3 = exception3.getMessage();
+
+        assertTrue(actualMessage3.contains(expectedMessage3));
+
+        // Edge destination out of range
+        Exception exception4 = assertThrows(IllegalArgumentException.class, () -> {
+            List<BoruvkaAlgorithm.Edge> invalidEdges = new ArrayList<>();
+            invalidEdges.add(new BoruvkaAlgorithm.Edge(0, 1, 2));
+            final var invalidGraph = new BoruvkaAlgorithm.Graph(1, invalidEdges);
+            assertEquals(invalidEdges, invalidGraph.edges);
+        });
+        String expectedMessage4 = "Edge vertex out of range";
+        String actualMessage4 = exception4.getMessage();
+
+        assertTrue(actualMessage4.contains(expectedMessage4));
+    }
+
+    /**
+     * Computes the total weight of the Minimum Spanning Tree
+     *
+     * @param result list of edges in the Minimum Spanning Tree
+     * @return the total weight of the Minimum Spanning Tree
+     */
+    int computeTotalWeight(final List<BoruvkaAlgorithm.Edge> result) {
+        int totalWeight = 0;
+        for (final var edge : result) {
+            totalWeight += edge.weight;
+        }
+        return totalWeight;
+    }
+}