Java
Java copied to clipboard
Feature/kruskal mst
This PR adds an implementation of Kruskal’s Algorithm for computing the Minimum Spanning Tree (MST) of a weighted undirected graph, addressing Issue #7067.
✔ What’s Included
- Added
KruskalMST.javaundercom.thealgorithms.greedyalgorithms - Added a clean and efficient implementation using:
- Greedy approach
- Disjoint Set Union (Union-Find) with path compression
- Edge class with comparable interface for sorting
- Added unit tests
KruskalMSTTest.javathat verify:- Correct MST weight for a sample connected graph
- Correct handling of disconnected graphs (returns -1)
✔ Why This is Useful
- Kruskal’s Algorithm is a core greedy technique frequently used in:
- Competitive programming
- Graph theory education
- Interview preparation
- Adds missing MST support to the greedy algorithms library
- Completes the request made in Issue #7067
🧪 Tests
All tests pass successfully using: