package Famous;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author zhengstars
 * @date 2023/12/02
 */
public class KruskalsMST {
    /**
     * Define the structure of an edge
     */
    static class Edge {
        int src, dest, weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    /**
     * Define the structure of a subset element
     */
    static class Subset {
        int parent, rank;

        public Subset(int parent, int rank) {
            this.parent = parent;
            this.rank = rank;
        }
    }

    // Function to find the Minimum Spanning Tree (MST)
    private static void kruskals(int V, ArrayList<Edge> edges) {
        int noOfEdges = 0;

        // Allocate memory to create V subsets
        Subset[] subsets = new Subset[V];

        // Allocate memory to create the result array
        Edge[] results = new Edge[V];

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

        // Sort the edges in ascending order of weights
        edges.sort(Comparator.comparingInt(o -> o.weight));

        // Index variable to traverse the sorted array of edges
        int i = 0;

        // Traverse the array of edges until V-1 edges are found
        while (noOfEdges < V - 1) {
            // Get the edge corresponding to the current index
            Edge nextEdge = edges.get(i++);

            // Find the root node of the set where the starting node of the edge belongs
            int x = findRoot(subsets, nextEdge.src);

            // Find the root node of the set where the ending node of the edge belongs
            int y = findRoot(subsets, nextEdge.dest);

            // If including this edge does not form a cycle, include it in the result and increment the result index
            if (x != y) {
                // Include the edge in the result and increment the result index
                results[noOfEdges++] = nextEdge;

                // Merge the sets of the starting and ending nodes
                union(subsets, x, y);
            }
        }

        // Print the edges and total weight of the constructed MST
        System.out.println("Edges of the constructed MST:");
        int minCost = 0;
        for (int j = 0; j < noOfEdges; j++) {
            System.out.println(results[j].src + " -- "
                    + results[j].dest + " == "
                    + results[j].weight);
            minCost += results[j].weight;
        }
        System.out.println("Total weight of MST: " + minCost);
    }

    // Function to merge two disjoint sets
    private static void union(Subset[] subsets, int x, int y) {
        int rootX = findRoot(subsets, x);
        int rootY = findRoot(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++;
        }
    }

    // Function to find the root node of a set
    private static int findRoot(Subset[] subsets, int i) {
        // If the current node is the root of the set, return it
        if (subsets[i].parent == i){
            return subsets[i].parent;
        }

        // If the current node is not the root, recursively find the root and perform path compression
        subsets[i].parent = findRoot(subsets, subsets[i].parent);

        // Return the found root node
        return subsets[i].parent;
    }

    // Main program entry point
    public static void main(String[] args) {
        int V = 4;
        ArrayList<Edge> graphEdges = new ArrayList<Edge>();
        graphEdges.add(new Edge(0, 1, 10));
        graphEdges.add(new Edge(0, 2, 6));
        graphEdges.add(new Edge(0, 3, 5));
        graphEdges.add(new Edge(1, 3, 15));
        graphEdges.add(new Edge(2, 3, 4));

        // Call the Kruskal's algorithm
        kruskals(V, graphEdges);
    }
}