Repository: TheAlgorithms/Java
Pull request #5967 (2024-10-24 05:20:19)

refactor: Enhance docs, add tests in `Kruskal`
<!--
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
-->

<!-- 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`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5967?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 67.70%. Comparing base [(`be0b1d5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/be0b1d58d649dba9901214d23b0110d0ca1e9b56?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`a8831b5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/a8831b5a2a6e942d7450214cba913a213aed2bbd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 1 commits behind head on master.

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5967      +/-   ##
============================================
+ Coverage     67.43%   67.70%   +0.27%     
- Complexity     4578     4586       +8     
============================================
  Files           620      620              
  Lines         17147    17121      -26     
  Branches       3312     3307       -5     
============================================
+ Hits          11563    11592      +29     
+ Misses         5138     5082      -56     
- Partials        446      447       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5967?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 0539f0df..1def3e25 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -812,6 +812,7 @@
               * [JohnsonsAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithmTest.java)
               * [KahnsAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithmTest.java)
               * [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
+              * [KruskalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java)
               * [TarjansAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithmTest.java)
               * [WelshPowellTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/WelshPowellTest.java)
             * hashmap
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/Kruskal.java b/src/main/java/com/thealgorithms/datastructures/graphs/Kruskal.java
index eb5b65d5..25c4548d 100644
--- a/src/main/java/com/thealgorithms/datastructures/graphs/Kruskal.java
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/Kruskal.java
@@ -1,27 +1,34 @@
 package com.thealgorithms.datastructures.graphs;
 
-// Problem -> Connect all the edges with the minimum cost.
-// Possible Solution -> Kruskal Algorithm (KA), KA finds the minimum-spanning-tree, which means, the
-// group of edges with the minimum sum of their weights that connect the whole graph.
-// The graph needs to be connected, because if there are nodes impossible to reach, there are no
-// edges that could connect every node in the graph.
-// KA is a Greedy Algorithm, because edges are analysed based on their weights, that is why a
-// Priority Queue is used, to take first those less weighted.
-// This implementations below has some changes compared to conventional ones, but they are explained
-// all along the code.
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.PriorityQueue;
 
+/**
+ * The Kruskal class implements Kruskal's Algorithm to find the Minimum Spanning Tree (MST)
+ * of a connected, undirected graph. The algorithm constructs the MST by selecting edges
+ * with the least weight, ensuring no cycles are formed, and using union-find to track the
+ * connected components.
+ *
+ * <p><strong>Key Features:</strong></p>
+ * <ul>
+ *   <li>The graph is represented using an adjacency list, where each node points to a set of edges.</li>
+ *   <li>Each edge is processed in ascending order of weight using a priority queue.</li>
+ *   <li>The algorithm stops when all nodes are connected or no more edges are available.</li>
+ * </ul>
+ *
+ * <p><strong>Time Complexity:</strong> O(E log V), where E is the number of edges and V is the number of vertices.</p>
+ */
 public class Kruskal {
 
-    // Complexity: O(E log V) time, where E is the number of edges in the graph and V is the number
-    // of vertices
-    private static class Edge {
+    /**
+     * Represents an edge in the graph with a source, destination, and weight.
+     */
+    static class Edge {
 
-        private int from;
-        private int to;
-        private int weight;
+        int from;
+        int to;
+        int weight;
 
         Edge(int from, int to, int weight) {
             this.from = from;
@@ -30,51 +37,30 @@ public class Kruskal {
         }
     }
 
-    private static void addEdge(HashSet<Edge>[] graph, int from, int to, int weight) {
+    /**
+     * Adds an edge to the graph.
+     *
+     * @param graph the adjacency list representing the graph
+     * @param from the source vertex of the edge
+     * @param to the destination vertex of the edge
+     * @param weight the weight of the edge
+     */
+    static void addEdge(HashSet<Edge>[] graph, int from, int to, int weight) {
         graph[from].add(new Edge(from, to, weight));
     }
 
-    public static void main(String[] args) {
-        HashSet<Edge>[] graph = new HashSet[7];
-        for (int i = 0; i < graph.length; i++) {
-            graph[i] = new HashSet<>();
-        }
-        addEdge(graph, 0, 1, 2);
-        addEdge(graph, 0, 2, 3);
-        addEdge(graph, 0, 3, 3);
-        addEdge(graph, 1, 2, 4);
-        addEdge(graph, 2, 3, 5);
-        addEdge(graph, 1, 4, 3);
-        addEdge(graph, 2, 4, 1);
-        addEdge(graph, 3, 5, 7);
-        addEdge(graph, 4, 5, 8);
-        addEdge(graph, 5, 6, 9);
-
-        System.out.println("Initial Graph: ");
-        for (int i = 0; i < graph.length; i++) {
-            for (Edge edge : graph[i]) {
-                System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
-            }
-        }
-
-        Kruskal k = new Kruskal();
-        HashSet<Edge>[] solGraph = k.kruskal(graph);
-
-        System.out.println("\nMinimal Graph: ");
-        for (int i = 0; i < solGraph.length; i++) {
-            for (Edge edge : solGraph[i]) {
-                System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
-            }
-        }
-    }
-
+    /**
+     * Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a graph.
+     *
+     * @param graph the adjacency list representing the input graph
+     * @return the adjacency list representing the MST
+     */
     public HashSet<Edge>[] kruskal(HashSet<Edge>[] graph) {
         int nodes = graph.length;
-        int[] captain = new int[nodes];
-        // captain of i, stores the set with all the connected nodes to i
+        int[] captain = new int[nodes]; // Stores the "leader" of each node's connected component
         HashSet<Integer>[] connectedGroups = new HashSet[nodes];
         HashSet<Edge>[] minGraph = new HashSet[nodes];
-        PriorityQueue<Edge> edges = new PriorityQueue<>((Comparator.comparingInt(edge -> edge.weight)));
+        PriorityQueue<Edge> edges = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
         for (int i = 0; i < nodes; i++) {
             minGraph[i] = new HashSet<>();
             connectedGroups[i] = new HashSet<>();
@@ -83,18 +69,21 @@ public class Kruskal {
             edges.addAll(graph[i]);
         }
         int connectedElements = 0;
-        // as soon as two sets merge all the elements, the algorithm must stop
         while (connectedElements != nodes && !edges.isEmpty()) {
             Edge edge = edges.poll();
-            // This if avoids cycles
+
+            // Avoid forming cycles by checking if the nodes belong to different connected components
             if (!connectedGroups[captain[edge.from]].contains(edge.to) && !connectedGroups[captain[edge.to]].contains(edge.from)) {
-                // merge sets of the captains of each point connected by the edge
+                // Merge the two sets of nodes connected by the edge
                 connectedGroups[captain[edge.from]].addAll(connectedGroups[captain[edge.to]]);
-                // update captains of the elements merged
+
+                // Update the captain for each merged node
                 connectedGroups[captain[edge.from]].forEach(i -> captain[i] = captain[edge.from]);
-                // add Edge to minimal graph
+
+                // Add the edge to the resulting MST graph
                 addEdge(minGraph, edge.from, edge.to, edge.weight);
-                // count how many elements have been merged
+
+                // Update the count of connected nodes
                 connectedElements = connectedGroups[captain[edge.from]].size();
             }
         }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java
new file mode 100644
index 00000000..b18f161e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/KruskalTest.java
@@ -0,0 +1,112 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class KruskalTest {
+
+    private Kruskal kruskal;
+    private HashSet<Kruskal.Edge>[] graph;
+
+    @BeforeEach
+    public void setUp() {
+        kruskal = new Kruskal();
+        int n = 7;
+        graph = new HashSet[n];
+        for (int i = 0; i < n; i++) {
+            graph[i] = new HashSet<>();
+        }
+
+        // Add edges to the graph
+        Kruskal.addEdge(graph, 0, 1, 2);
+        Kruskal.addEdge(graph, 0, 2, 3);
+        Kruskal.addEdge(graph, 0, 3, 3);
+        Kruskal.addEdge(graph, 1, 2, 4);
+        Kruskal.addEdge(graph, 2, 3, 5);
+        Kruskal.addEdge(graph, 1, 4, 3);
+        Kruskal.addEdge(graph, 2, 4, 1);
+        Kruskal.addEdge(graph, 3, 5, 7);
+        Kruskal.addEdge(graph, 4, 5, 8);
+        Kruskal.addEdge(graph, 5, 6, 9);
+    }
+
+    @Test
+    public void testKruskal() {
+        int n = 6;
+        HashSet<Kruskal.Edge>[] graph = new HashSet[n];
+
+        for (int i = 0; i < n; i++) {
+            graph[i] = new HashSet<>();
+        }
+
+        Kruskal.addEdge(graph, 0, 1, 4);
+        Kruskal.addEdge(graph, 0, 2, 2);
+        Kruskal.addEdge(graph, 1, 2, 1);
+        Kruskal.addEdge(graph, 1, 3, 5);
+        Kruskal.addEdge(graph, 2, 3, 8);
+        Kruskal.addEdge(graph, 2, 4, 10);
+        Kruskal.addEdge(graph, 3, 4, 2);
+        Kruskal.addEdge(graph, 3, 5, 6);
+        Kruskal.addEdge(graph, 4, 5, 3);
+
+        HashSet<Kruskal.Edge>[] result = kruskal.kruskal(graph);
+
+        List<List<Integer>> actualEdges = new ArrayList<>();
+        for (HashSet<Kruskal.Edge> edges : result) {
+            for (Kruskal.Edge edge : edges) {
+                actualEdges.add(Arrays.asList(edge.from, edge.to, edge.weight));
+            }
+        }
+
+        List<List<Integer>> expectedEdges = Arrays.asList(Arrays.asList(1, 2, 1), Arrays.asList(0, 2, 2), Arrays.asList(3, 4, 2), Arrays.asList(4, 5, 3), Arrays.asList(1, 3, 5));
+
+        assertTrue(actualEdges.containsAll(expectedEdges) && expectedEdges.containsAll(actualEdges));
+    }
+
+    @Test
+    public void testEmptyGraph() {
+        HashSet<Kruskal.Edge>[] emptyGraph = new HashSet[0];
+        HashSet<Kruskal.Edge>[] result = kruskal.kruskal(emptyGraph);
+        assertEquals(0, result.length);
+    }
+
+    @Test
+    public void testSingleNodeGraph() {
+        HashSet<Kruskal.Edge>[] singleNodeGraph = new HashSet[1];
+        singleNodeGraph[0] = new HashSet<>();
+        HashSet<Kruskal.Edge>[] result = kruskal.kruskal(singleNodeGraph);
+        assertTrue(result[0].isEmpty());
+    }
+
+    @Test
+    public void testGraphWithDisconnectedNodes() {
+        int n = 5;
+        HashSet<Kruskal.Edge>[] disconnectedGraph = new HashSet[n];
+        for (int i = 0; i < n; i++) {
+            disconnectedGraph[i] = new HashSet<>();
+        }
+
+        Kruskal.addEdge(disconnectedGraph, 0, 1, 2);
+        Kruskal.addEdge(disconnectedGraph, 2, 3, 4);
+
+        HashSet<Kruskal.Edge>[] result = kruskal.kruskal(disconnectedGraph);
+
+        List<List<Integer>> actualEdges = new ArrayList<>();
+        for (HashSet<Kruskal.Edge> edges : result) {
+            for (Kruskal.Edge edge : edges) {
+                actualEdges.add(Arrays.asList(edge.from, edge.to, edge.weight));
+            }
+        }
+
+        List<List<Integer>> expectedEdges = Arrays.asList(Arrays.asList(0, 1, 2), Arrays.asList(2, 3, 4));
+
+        assertTrue(actualEdges.containsAll(expectedEdges) && expectedEdges.containsAll(actualEdges));
+    }
+}