Java icon indicating copy to clipboard operation
Java copied to clipboard

Add Kruskal's Algorithm implementation

Open RamsaiPolisetti opened this issue 3 months ago • 1 comments

Summary

This PR adds an implementation of Kruskal's Minimum Spanning Tree (MST) algorithm to the graph package.
Kruskal’s algorithm is a classic greedy algorithm that finds the MST of a connected, undirected, weighted graph by selecting edges in increasing order of weight while avoiding cycles.

Implementation Details

  • Added KruskalsAlgorithm.java under src/main/java/com/thealgorithms/graph/
  • Includes:
    • Edge class for representing edges
    • DSU (Disjoint Set Union / Union–Find) for cycle detection
    • kruskalMST() method implementing the core algorithm
  • Clean, modular, and follows project style conventions.

Tests

  • Added a corresponding JUnit test under
    src/test/java/com/thealgorithms/graph/
  • Tests verify:
    • The MST has exactly V - 1 edges.
    • The smallest edges are correctly selected.
    • The algorithm avoids cycles.

All tests pass using ./gradlew test.

Checklist

  • [x] Added implementation
  • [x] Added tests
  • [x] Code compiles successfully
  • [x] Tests pass
  • [x] Follows coding style and package structure

RamsaiPolisetti avatar Nov 25 '25 17:11 RamsaiPolisetti

Codecov Report

:x: Patch coverage is 0% with 59 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 78.29%. Comparing base (2c4bf3c) to head (8bbb886). :warning: Report is 11 commits behind head on master.

Files with missing lines Patch % Lines
...ava/com/thealgorithms/graph/KruskalsAlgorithm.java 0.00% 59 Missing :warning:
Additional details and impacted files
@@             Coverage Diff              @@
##             master    #7121      +/-   ##
============================================
- Coverage     78.51%   78.29%   -0.23%     
+ Complexity     6752     6751       -1     
============================================
  Files           759      760       +1     
  Lines         22402    22461      +59     
  Branches       4400     4410      +10     
============================================
- Hits          17589    17585       -4     
- Misses         4108     4169      +61     
- Partials        705      707       +2     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:
  • :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

codecov-commenter avatar Nov 25 '25 17:11 codecov-commenter