Terminate Kruskal's algorithm when MST reaches V-1 edges

Lord-of-Algorithms · Lord-of-Algorithms · commit 73192ca028df · 2024-08-06T00:53:22.000+03:00
diff --git a/src/graph/mst/kruskal/KruskalMstMain.java b/src/graph/mst/kruskal/KruskalMstMain.java
@@ -72,6 +72,10 @@ public int compare(Edge edge1, Edge edge2) {
             if (uf.find(edge.getSource()) != uf.find(edge.getDestination())) {
                 mst.add(edge);
                 uf.union(edge.getSource(), edge.getDestination());
+                if (mst.size() == vertices.size() - 1) {
+                    // Stop when MST is complete
+                    break;
+                }
             }
         }
         return mst;

Original file line number	Diff line number	Diff line change
`@@ -72,6 +72,10 @@ public int compare(Edge edge1, Edge edge2) {`
`72`	`72`	`if (uf.find(edge.getSource()) != uf.find(edge.getDestination())) {`
`73`	`73`	`mst.add(edge);`
`74`	`74`	`uf.union(edge.getSource(), edge.getDestination());`
	`75`	`+ if (mst.size() == vertices.size() - 1) {`
	`76`	`+ // Stop when MST is complete`
	`77`	`+ break;`
	`78`	`+ }`
`75`	`79`	`}`
`76`	`80`	`}`
`77`	`81`	`return mst;`