Java
Java copied to clipboard
Add Kruskal's Algorithm implementation
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.javaundersrc/main/java/com/thealgorithms/graph/ - Includes:
-
Edgeclass 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 - 1edges. - The smallest edges are correctly selected.
- The algorithm avoids cycles.
- The MST has exactly
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
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.