KruskalSecondBestMST.java

import java.util.*;

class Edge implements Comparable<Edge> {
    int source, destination, weight;

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

class Graph {
    private int vertices;
    private List<Edge> edges;

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

    public void addEdge(int source, int destination, int weight) {
        Edge edge = new Edge();
        edge.source = source;
        edge.destination = destination;
        edge.weight = weight;
        edges.add(edge);
    }

    private int find(int[] parent, int vertex) {
        if (parent[vertex] != vertex)
            parent[vertex] = find(parent, parent[vertex]);
        return parent[vertex];
    }

    private void union(int[] parent, int x, int y) {
        int xRoot = find(parent, x);
        int yRoot = find(parent, y);
        parent[xRoot] = yRoot;
    }

    private List<Edge> getMinimumSpanningTree() {
        List<Edge> minimumSpanningTree = new ArrayList<>();
        Collections.sort(edges);
        int[] parent = new int[vertices];
        for (int i = 0; i < vertices; i++)
            parent[i] = i;
        
        int edgeCount = 0;
        int index = 0;
        while (edgeCount < vertices - 1) {
            Edge currentEdge = edges.get(index++);
            int sourceRoot = find(parent, currentEdge.source);
            int destinationRoot = find(parent, currentEdge.destination);

            if (sourceRoot != destinationRoot) {
                minimumSpanningTree.add(currentEdge);
                union(parent, sourceRoot, destinationRoot);
                edgeCount++;
            }
        }
        
        return minimumSpanningTree;
    }

    private int calculateCost(List<Edge> edges) {
        int cost = 0;
        for (Edge edge : edges)
            cost += edge.weight;
        return cost;
    }

    public int findSecondBestMinimumSpanningTree() {
        int secondBestMST = Integer.MAX_VALUE;
        List<Edge> minimumSpanningTree = getMinimumSpanningTree();
        for (Edge excludedEdge : minimumSpanningTree) {
            Graph modifiedGraph = new Graph(vertices);
            for (Edge edge : edges) {
                if (edge != excludedEdge)
                    modifiedGraph.addEdge(edge.source, edge.destination, edge.weight);
            }
            
            List<Edge> modifiedMST = modifiedGraph.getMinimumSpanningTree();
            if (modifiedMST.size() == vertices - 1) {
                int cost = calculateCost(modifiedMST);
                secondBestMST = Math.min(secondBestMST, cost);
            }
        }
        
        return secondBestMST;
    }
}

public class KruskalSecondBestMST {
    public static void main(String[] args) {
        int vertices = 6;
        Graph graph = new Graph(vertices);

        // Add edges to the graph
        graph.addEdge(0, 1, 6);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 4);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 5);
        graph.addEdge(2, 4, 7);
        graph.addEdge(3, 4, 1);
        graph.addEdge(3, 5, 5);
        graph.addEdge(4, 5, 8);

        int secondBestMSTCost = graph.findSecondBestMinimumSpanningTree();
        System.out.println("Cost of the second-best minimum spanning tree: " + secondBestMSTCost);
    }
}