Untitled
unknown
java
3 years ago
2.5 kB
6
Indexable
import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Scanner; public class KruskalMST { /** * Optimizes the provided Phorest to be as close to an MST as possible. * @param n the number of nodes in the network * @param g all edges in the full graph * @param p the edges in the Phorest * @return total edge weight of optimized Phorest */ public static String run(int n, Edge[] g, Edge[] p) { return new KruskalMST().solve(n, g, p); } public String solve(int nodes, Edge[] graph, Edge[] phorest) { int maxLoop = nodes - 1; int countLoop = 0; int total = 0; HashMap<Integer, Integer> set = new HashMap<Integer, Integer>(); for(int i = 0; i < phorest.length; i++) { set.put(i, i); } while (maxLoop != countLoop) { for (int i = 0; i < phorest.length; i++) { if (!hasCycle(phorest[i].x, phorest[i].y, set)) { countLoop++; } } } while(maxLoop != countLoop) { for(int i = 0; i < phorest.length; i++) { total += find(set, phorest[i].x); } } String ans = "" + total + ""; return ans; } public static Edge[] makeGraph(Scanner sc) { int m = sc.nextInt(); Edge[] edges = new Edge[m]; for (int i = 0; i < m; i++) edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()); Arrays.sort(edges, Comparator.comparingInt(e -> e.l)); return edges; } public static boolean hasCycle(Integer source, Integer destination, HashMap<Integer, Integer> disjointSet) { int root = find(disjointSet, source); int root2 = find(disjointSet, destination); if (root == root2) return true; else union(disjointSet, source, destination); return false; } public static Integer find(HashMap<Integer, Integer> parent, Integer v) { // Vertex is the root if (parent.get(v) == v) return v; // recursive call return find(parent, parent.get(v)); } public static void union(HashMap<Integer, Integer> parent, Integer start, Integer end) { Integer x = find(parent, start); Integer y = find(parent, end); parent.put(x, y); } }
Editor is loading...