Skip to content

Instantly share code, notes, and snippets.

@rudSarkar
Created June 18, 2023 16:33
Show Gist options
  • Save rudSarkar/28a87a70f7f68e8d922ce21e0e4f24df to your computer and use it in GitHub Desktop.
Save rudSarkar/28a87a70f7f68e8d922ce21e0e4f24df to your computer and use it in GitHub Desktop.
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment