Kruskal - rFronteddu/general_wiki GitHub Wiki

MST-KRUSKAL(G,w)
    A = {}
    for each v in G.V
        MAKE-SET(V)
    sort G.E in nondecreasing order by weight w
    
    for each (u,v) in G.E, taken in nondecreasing order by weight
        // check whether u,v belong to the same tree i.e. whether we would add a cycle
        if FIND_SET(u) != FIND_SET(v) // FIND_SET returns a representative element from the set that contains u
            add (u,v) to A
            // UNION merges the vertices of two clusters to determine 
            // if adding a future edge will produce a cycle
            UNION(u,v) 
    return A

// Java program for Kruskal's algorithm 

import java.util.ArrayList; 
import java.util.List; 
import lombok.AllArgsConstructor;

public class KruskalsMST { 
    @AllArgsConstructor
    static class Edge { 
        int src, dest, weight; 
    }

    @AllArgsConstructor
    static class Subset { 
	int parent, rank; 
    } 

    // Starting point of program execution 
    public static void main(String[] args) { 
        // ... init edges and vertices 
        // List<Edge> graphEdges = ...
        // int V = ...
	kruskals(V, graphEdges); 
    } 

    // Function to find the MST 
    private static void kruskals(int V, List<Edge> edges) { 
	// Sort the edges in non-decreasing order 
	graphEdges.sort((e1, e2) -> { return e1.w - e2.w; })

	Subset subsets[] = new Subset[V]; 
	Edge results[] = new Edge[V]; 

	// Create V subsets with single elements 
	for (int i = 0; i < V; i++) { 
	    subsets[i] = new Subset(i, 0); 
	} 

        int j = 0; 
	int noOfEdges = 0;
 
	// Number of edges to be taken is equal to V-1 
	while (noOfEdges < V - 1) { 
            // Pick the smallest edge. And increment the index for next iteration 
	    Edge nextEdge = edges.get(j); 
	    int x = findSet(subsets, nextEdge.src); 
	    int y = findSet(subsets, nextEdge.dest); 

	    // If including this edge doesn't cause cycle, include it in result and increment the index 
	    // of result for next edge 
	    if (x != y) { 
	        results[noOfEdges] = nextEdge; 
		union(subsets, x, y); 
		noOfEdges++; 
	    } 
	    j++; 
	} 

        printResult (results, noOfEdges);
    } 

    // Function to find parent of a set 
    private static int findSet(Subset[] subsets, int i) { 
        if (subsets[i].parent == i) 
	    return i; 

	subsets[i].parent = findSet (subsets, subsets[i].parent); 
	return subsets[i].parent; 
    } 

    // Function to unite two disjoint sets 
    private static void union(Subset[] subsets, int x, int y) { 
        int rootX = findSet(subsets, x); 
	int rootY = findSet(subsets, y); 

	if (subsets[rootY].rank < subsets[rootX].rank) { 
	    subsets[rootY].parent = rootX; 
	} 
	else if (subsets[rootX].rank < subsets[rootY].rank) { 
	    subsets[rootX].parent = rootY; 
	} 
	else { 
	    subsets[rootY].parent = rootX; 
	    subsets[rootX].rank++; 
	} 
    } 

    private static void printResult(Edge[] results, int noOfEdges) {
	// Print the contents of result to display the  built MST 
	System.out.println ("Following are the edges of the constructed MST:"); 
	int minCost = 0; 
	for (int i = 0; i < noOfEdges; i++) { 
	    System.out.println (results[i].src + " -- "+ results[i].dest + " == "+ results[i].weight); 
	    minCost += results[i].weight; 
	} 
        System.out.println ("Total cost of MST: " + minCost);  
    }
}