Java icon indicating copy to clipboard operation
Java copied to clipboard

Feature/kruskal mst

Open prasanth-30011 opened this issue 2 weeks ago • 1 comments

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.java under com.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.java that 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:

prasanth-30011 avatar Nov 21 '25 06:11 prasanth-30011