SHARE
TWEET

Untitled

a guest Sep 15th, 2019 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class KruskalMST {
  2.     public static void main(String[] args) {
  3.         // Min Cost to Connect All Nodes (Minimum Spanning Tree I)
  4.     int n = 6;
  5.     int[][] edges = new int[][] { { 1, 4 }, { 4, 5 }, { 2, 3 } };
  6.     int[][] newEdges = { { 1, 2, 5 }, { 1, 3, 10 }, { 1, 6, 2 }, { 5, 6, 5 } };
  7.     int cost = minCostToConnectAllNodes(6, edges, newEdges);
  8.  
  9.     System.out.println(String.format("Min Cost to Connect All Nodes: %d", cost));
  10.  
  11.     // Min Cost to Repair Edges (Minimum Spanning Tree II)
  12.     n = 5;
  13.     edges = new int[][] { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 1, 5 } };
  14.     int[][] edgesToRepair = { { 1, 2, 12 }, { 3, 4, 30 }, { 1, 5, 8 } };
  15.     cost = minCostToRepairEdges(n, edges, edgesToRepair);
  16.     System.out.println(String.format("Min Cost to Repair Edges: %d", cost));
  17.  
  18.     n = 6;
  19.     edges = new int[][] { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 3, 5 }, { 1, 6 }, { 2, 4 } };
  20.     edgesToRepair = new int[][] { { 1, 6, 410 }, { 2, 4, 800 } };
  21.     cost = minCostToRepairEdges(n, edges, edgesToRepair);
  22.     System.out.println(String.format("Min Cost to Repair Edges: %d", cost));
  23.  
  24.     n = 6;
  25.     edges = new int[][] { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 5, 6 }, { 1, 5 }, { 2, 4 }, { 3, 4 } };
  26.     edgesToRepair = new int[][] { { 1, 5, 110 }, { 2, 4, 84 }, { 3, 4, 79 } };
  27.     cost = minCostToRepairEdges(n, edges, edgesToRepair);
  28.     System.out.println(String.format("Min Cost to Repair Edges: %d", cost));
  29.     }  
  30.  
  31.     private static int minCostToConnectAllNodes(int n, int[][] edges, int[][] newEdges) {
  32.     int vertices = n;
  33.     Graph graph = new Graph(vertices);
  34.     for (int[] edge : edges)
  35.         graph.addEgde(edge[0], edge[1], 0);
  36.     for (int[] newEdge : newEdges)
  37.         graph.addEgde(newEdge[0], newEdge[1], newEdge[2]);
  38.  
  39.     return graph.kruskalMST();
  40.     }
  41.  
  42.     private static int minCostToRepairEdges(int n, int[][] edges, int[][] edgesToRepair) {
  43.     int vertices = n;
  44.     Set<Edge> newEdgesToRepair = new HashSet<>();
  45.     for (int[] newEdge : edgesToRepair)
  46.         newEdgesToRepair.add(new Edge(newEdge[0], newEdge[1], newEdge[2]));
  47.     Set<Edge> allEdges = new HashSet<>();
  48.     for (int[] edge : edges)
  49.         allEdges.add(new Edge(edge[0], edge[1], 0));
  50.  
  51.     newEdgesToRepair.addAll(allEdges);
  52.  
  53.     Graph graph = new Graph(vertices);
  54.     for (Edge edge : newEdgesToRepair)
  55.         graph.addEgde(edge.source, edge.destination, edge.weight);
  56.    
  57.  
  58.     return graph.kruskalMST();
  59.     }    
  60.  
  61.     static class Edge {
  62.     final int source;
  63.     final int destination;
  64.     final int weight;
  65.  
  66.     public Edge(int source, int destination, int weight) {
  67.         this.source = source;
  68.         this.destination = destination;
  69.         this.weight = weight;
  70.     }
  71.  
  72.     @Override
  73.     public boolean equals(Object o) {
  74.         if (o == this)
  75.         return true;
  76.         if (!(o instanceof Edge))
  77.         return false;
  78.         Edge e = (Edge) o;
  79.         return e.source == source && e.destination == destination;
  80.     }
  81.  
  82.     @Override
  83.     public int hashCode() {
  84.         int result = Integer.hashCode(source);
  85.         result = 31 * result + Integer.hashCode(destination);
  86.         return result;
  87.     }
  88.     }
  89.  
  90.     static class Graph {
  91.     private final int vertices;
  92.     private final List<Edge> allEdges = new ArrayList<>();
  93.  
  94.     Graph(int vertices) {
  95.         this.vertices = vertices;
  96.     }
  97.  
  98.     public int kruskalMST() {
  99.         PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(),
  100.         Comparator.comparingInt(o -> o.weight));
  101.  
  102.         for (int i = 0; i < allEdges.size(); i++) {
  103.         pq.add(allEdges.get(i));
  104.         }
  105.  
  106.         int[] parent = new int[vertices + 1];
  107.  
  108.         makeSet(parent);
  109.  
  110.         List<Edge> mst = new ArrayList<>();
  111.  
  112.         int cost = 0;
  113.  
  114.         for (int index = 0; index < vertices - 1;) {
  115.         Edge edge = pq.remove();
  116.         int x_set = find(parent, edge.source);
  117.         int y_set = find(parent, edge.destination);
  118.  
  119.         if (x_set != y_set) {
  120.             // add it to our final result
  121.             mst.add(edge);
  122.             // update the total cost
  123.             cost += edge.weight;
  124.             union(parent, x_set, y_set);
  125.             index++;
  126.         }
  127.         }
  128.  
  129.         return cost;
  130.     }
  131.  
  132.     public void addEgde(int source, int destination, int weight) {
  133.         Edge edge = new Edge(source, destination, weight);
  134.         allEdges.add(edge);
  135.     }
  136.  
  137.     public void makeSet(int[] parent) {
  138.         for (int i = 1; i <= vertices; i++)
  139.             parent[i] = i;
  140.         }
  141.  
  142.     public int find(int[] parent, int vertex) {
  143.         if (parent[vertex] != vertex)
  144.             return find(parent, parent[vertex]);
  145.  
  146.         return vertex;
  147.     }
  148.  
  149.     public void union(int[] parent, int x, int y) {
  150.         int x_set_parent = find(parent, x);
  151.         int y_set_parent = find(parent, y);
  152.         // make x as parent of y
  153.         parent[y_set_parent] = x_set_parent;
  154.     }
  155.     }
  156. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top