Guest User

Reverse-delete Algorithm class

a guest
Mar 15th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.57 KB | None | 0 0
  1. package reverse_delete;
  2.  
  3. import java.util.Iterator;
  4. import java.util.PriorityQueue;
  5.  
  6. public class TestGraphs {
  7.  
  8.     public static void main(String[] args) {
  9.         Graph g = new Graph(5);
  10.  
  11.         System.out.println("Graph:");
  12.         // add Edges
  13.         g.addEdge(0, 1, 5.2f);
  14.         g.addEdge(0, 3, 7.1f);
  15.         g.addEdge(1, 3, 5.9f);
  16.         g.addEdge(1, 4, 3.4f);
  17.         g.addEdge(2, 1, 1.5f);
  18.         g.addEdge(2, 3, 2.3f);
  19.         g.addEdge(3, 4, 8.5f);
  20.         g.addEdge(4, 2, 2.7f);
  21.  
  22.         // print Graph
  23.         g.printGraph();
  24.  
  25.         // Reverse-Delete Algorithm
  26.         System.out.println("\nReverse-Delete MST:");
  27.         Graph mst = Reverse_Delete(g);
  28.         mst.printGraph();
  29.     }
  30.  
  31.     public static Graph Reverse_Delete(Graph g) {
  32.         int v = g.getvCount();
  33.         int e = 0; // edge count
  34.         Graph mst = new Graph(v);
  35.  
  36.         // create queue of all edges in descending order
  37.         // AND
  38.         // initialize mst to given graph
  39.         PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
  40.         for (int i = 0; i < v; i++) {
  41.             Iterator<Edge> it = g.neighbours(i).iterator();
  42.             while (it.hasNext()) {
  43.                 Edge temp = it.next();
  44.                 if (!mst.hasEdge(temp)) {
  45.                     mst.addEdge(temp); // add edge to mst
  46.                     edges.add(temp); // add edge to queue
  47.                     e++; // increment edge count
  48.                 }
  49.             }
  50.         }
  51.  
  52.         // loop through all the edges
  53.         for (int i = 0; i < e; i++) {
  54.             // get most-weighted edge
  55.             Edge temp = edges.remove();
  56.  
  57.             // remove the edge from the mst
  58.             mst.removeEdge(temp.getStartPoint(), temp.getEndPoint());
  59.  
  60.             // check if it stays connected
  61.             if (!mst.isConnected()) {
  62.                 mst.addEdge(temp); // add edge back
  63.             }
  64.         }
  65.  
  66.         return mst;
  67.     }
  68.  
  69. }
Add Comment
Please, Sign In to add comment