Lab9.java

import java.util.*;


class Edge implements Comparable<Edge> {
    int src, dest, weight;

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

    
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}


class Node {
    Node parent;
    int rank;

    
    public Node() {
        this.parent = this;
        this.rank = 0;
    }
}

class Graph {
    int V; // Number of vertices
    List<Edge> edges; // List of edges

    
    public Graph(int V) {
        this.V = V;
        edges = new ArrayList<>();
    }

    
    public void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }
    
    // Disjoint-set make set operation
    private Node makeSet() {
        return new Node();
    }

    // Find function with path compression
    private Node find(Node node) {
        if (node != node.parent) {
            node.parent = find(node.parent); // Path compression
        }
        return node.parent;
    }

    // Union by rank
    private void union(Node node1, Node node2) {
        Node root1 = find(node1);
        Node root2 = find(node2);

        if (root1 != root2) {
            if (root1.rank < root2.rank) {
                root1.parent = root2;
            } else if (root1.rank > root2.rank) {
                root2.parent = root1;
            } else {
                root2.parent = root1;
                root1.rank++;
            }
        }
    }

    // Kruskal's algorithm to find MST
    public List<Edge> kruskalMST() {
        List<Edge> mst = new ArrayList<>();
        Node[] subsets = new Node[V];

        // Create subset nodes for each vertex
        for (int i = 0; i < V; i++) {
            subsets[i] = makeSet();
        }

        Collections.sort(edges);

        
        for (Edge edge : edges) {
            Node rootSrc = find(subsets[edge.src]);
            Node rootDest = find(subsets[edge.dest]);

            // If including this edge doesn't form a cycle, add it to the MST
            if (rootSrc != rootDest) {
                mst.add(edge);
                union(rootSrc, rootDest);
            }
        }
        
        return mst;
    }

    
    public int calculateMSTCost(List<Edge> mst) {
        int totalWeight = 0;
        for (Edge edge : mst) {
            totalWeight += edge.weight;
        }
        return totalWeight;
    }
}

public class Lab9 {
    public static void main(String[] args) {
        int V = 4; // Number of vertices
        Graph graph = new Graph(V);

        // Add edges: (source, destination, weight)
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);

        
        List<Edge> mst = graph.kruskalMST();

       
        System.out.println("Edges in the MST:");
        for (Edge edge : mst) {
            System.out.println("Edge: " + edge.src + " - " + edge.dest + " (weight: " + edge.weight + ")");
        }

        
        int mstCost = graph.calculateMSTCost(mst);
        System.out.println("Total cost of MST: " + mstCost);
    }
}