Merge pull request codehouseindia#156 from shivamadlakha/patch-1

codehouseindia · web-flow · commit 79782202d71c · 2020-10-15T00:52:59.000+05:30
Spanning Tree
diff --git a/spanning_tree b/spanning_tree
@@ -0,0 +1,27 @@
+ValueGraph<Integer, Double> spanningTree(ValueGraph<Integer, Double> graph, boolean minSpanningTree) {
+    Set<EndpointPair> edges = graph.edges();
+    List<EndpointPair> edgeList = new ArrayList<>(edges);
+ 
+    if (minSpanningTree) {
+        edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get()));
+    } else {
+        edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get())));
+    }
+ 
+    int totalNodes = graph.nodes().size();
+    CycleDetector cycleDetector = new CycleDetector(totalNodes);
+    int edgeCount = 0;
+ 
+    MutableValueGraph<Integer, Double> spanningTree = ValueGraphBuilder.undirected().build();
+    for (EndpointPair edge : edgeList) {
+        if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) {
+            continue;
+        }
+        spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get());
+        edgeCount++;
+        if (edgeCount == totalNodes - 1) {
+            break;
+        }
+    }
+    return spanningTree;
+}
