### Question:
GraphAlgorithms { public static UndirectedGraph getMinimumSpanningTree(UndirectedGraph graph) { if (graph == null) { throw new IllegalArgumentException("Input graph should be not null"); } List<Edge> edges = new ArrayList<>(graph.getEdgeCount()); for (int i = 0; i < graph.getVertexCount(); i++) { Iterator<Edge> edgesIterator = graph.getEdgesForVertex(i); while (edgesIterator.hasNext()) { Edge edge = edgesIterator.next(); if (edge.getHead() < i) { edges.add(edge); } } } Collections.sort(edges, (Edge e1, Edge e2) -> e1.getWeight() > e2.getWeight() ? 1 : e1.getWeight() < e2.getWeight() ? -1 : 0); UnionFind unionFind = new UnionFind(graph.getVertexCount()); UndirectedGraph minimumSpanningTree = new UndirectedGraph(graph.getVertexCount()); for (Edge edge : edges) { if (unionFind.find(edge.getTail()) == unionFind.find(edge.getHead())) { continue; } unionFind.union(edge.getTail(), edge.getHead()); minimumSpanningTree.addEdge(edge); } return minimumSpanningTree; } private  GraphAlgorithms(); static ClusteringResult getClusteringComponents(UndirectedGraph graph,
                                                           int k); static UndirectedGraph getMinimumSpanningTree(UndirectedGraph graph);  }### Answer:
@Test(expected = IllegalArgumentException.class) public void testGetMinimumSpanningTreeNullGraph() { getMinimumSpanningTree(null); }
@Test public void testGetMinimumSpanningTree1() { UndirectedGraph graph = new UndirectedGraph(3); graph.addEdge(new Edge(0, 1, 1)); graph.addEdge(new Edge(1, 2, 1)); graph.addEdge(new Edge(2, 0, 1)); UndirectedGraph minimumSpanningTree = GraphAlgorithms.getMinimumSpanningTree(graph); assertEquals(3, minimumSpanningTree.getVertexCount()); assertEquals(2, minimumSpanningTree.getEdgeCount()); double weight = 0; for (int i = 0; i < minimumSpanningTree.getVertexCount(); i++) { Iterator<Edge> edgesIterator = minimumSpanningTree.getEdgesForVertex(i); while (edgesIterator.hasNext()) { Edge edge = edgesIterator.next(); if (edge.getHead() < i) { weight += edge.getWeight(); } } } assertEquals(2, weight, EPSILON); }
@Test public void testGetMinimumSpanningTree2() { UndirectedGraph graph = new UndirectedGraph(3); graph.addEdge(new Edge(0, 1, 1)); graph.addEdge(new Edge(1, 2, 3)); graph.addEdge(new Edge(2, 0, 3)); UndirectedGraph minimumSpanningTree = GraphAlgorithms.getMinimumSpanningTree(graph); assertEquals(3, minimumSpanningTree.getVertexCount()); assertEquals(2, minimumSpanningTree.getEdgeCount()); double weight = 0; for (int i = 0; i < minimumSpanningTree.getVertexCount(); i++) { Iterator<Edge> edgesIterator = minimumSpanningTree.getEdgesForVertex(i); while (edgesIterator.hasNext()) { Edge edge = edgesIterator.next(); if (edge.getHead() < i) { weight += edge.getWeight(); } } } assertEquals(4, weight, EPSILON); }