MST { public Set<WeightEdge<Integer>> krusal(WeightUndirectGraph<Integer> graph) { Set<WeightEdge<Integer>> mst = new HashSet<>(); Set<Vertex<Integer>> vertices = graph.allVertices(); HashMap<Integer, Vertex<Integer>> iMap = new HashMap<>(); for (Vertex<Integer> v : vertices) { iMap.put(v.t, v); } UnionFind uf = new UnionFind(vertices.size()); List<WeightEdge<Integer>> edges = graph.allWeightEdges(); edges.sort(Comparator.comparing(WeightEdge::getWeight)); int union = 0; for (WeightEdge<Integer> edge : edges) { if (union >= vertices.size() - 1) { break; } Vertex<Integer> f = edge.from, t = edge.to; int f1 = f.t - 1, t1 = t.t - 1; if (uf.findRoot(f1) != uf.findRoot(t1)) { uf.union(f1, t1); union++; mst.add(edge); } } return mst; }  Set<WeightEdge<Integer>> prim(WeightUndirectGraph<Integer> graph); Set<WeightEdge<Integer>> krusal(WeightUndirectGraph<Integer> graph);  }
@Test public void testKrusal() { MST mst = new MST(); Set<WeightEdge<Integer>> minCut = mst.krusal(graph); assertEquals(expected, minCut); }