Guest User

Boruvka Algorithm class

a guest
Mar 15th, 2018
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.43 KB | None | 0 0
  1. package boruvka_mst;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.PriorityQueue;
  6.  
  7. public class TestGraphs {
  8.  
  9.     public static void main(String[] args) {
  10.         Graph g = new Graph(5);
  11.  
  12.         System.out.println("Graph:");
  13.         // add Edges
  14.         g.addEdge(0, 1, 5.2f);
  15.         g.addEdge(0, 3, 7.1f);
  16.         g.addEdge(1, 3, 5.9f);
  17.         g.addEdge(1, 4, 3.4f);
  18.         g.addEdge(2, 1, 1.5f);
  19.         g.addEdge(2, 3, 2.3f);
  20.         g.addEdge(3, 4, 8.5f);
  21.         g.addEdge(4, 2, 2.7f);
  22.  
  23.         // print Graph
  24.         g.printGraph();
  25.  
  26.         // Boruvka Algorithm
  27.         System.out.println("\nBoruvka MST:");
  28.         Graph mst = Boruvka(g);
  29.         mst.printGraph();
  30.     }
  31.  
  32.     public static Graph Boruvka(Graph g) {
  33.         int v = g.getvCount();
  34.  
  35.         // initialize mst
  36.         Graph mst = new Graph(v);
  37.  
  38.         // loop until everything is connected
  39.         while (!mst.isConnected()) {
  40.    
  41.             // loop through all vertices
  42.             for (int i = 0; i < v; i++) {
  43.                
  44.                 // check if all nodes are reachable
  45.                 if (mst.CountReachableNodes(i) < v) {
  46.                    
  47.                     // iterate through all the edges of the current node
  48.                     Iterator<Edge> it = g.neighbours(i).iterator();
  49.                     while(it.hasNext()){
  50.                         Edge e = it.next();
  51.                        
  52.                         // add edge to mst if not added already
  53.                         // AND
  54.                         // endPoint is not reachable from elsewhere (no cycles allowed!)
  55.                         if(!mst.hasEdge(e) && !mst.Reachable(i, e.getEndPoint())){
  56.                             mst.addEdge(e);
  57.                             break;
  58.                         }
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.  
  64.         return mst;
  65.     }
  66.  
  67. }
Add Comment
Please, Sign In to add comment