Question

In: Computer Science

Java programming Trace the algorithm for minimum spanning tree (eager, lazy Prim algorithm)

  • Java programming
  • Trace the algorithm for minimum spanning tree (eager, lazy Prim algorithm)

Solutions

Expert Solution

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3.  
  4. public class Prims
  5. {
  6.     private boolean unsettled[];
  7.     private boolean settled[];
  8.     private int numberofvertices;
  9.     private int adjacencyMatrix[][];
  10.     private int key[];
  11.     public static final int INFINITE = 999;
  12.     private int parent[];
  13.     public Prims(int numberofvertices)
  14.     {
  15.         this.numberofvertices = numberofvertices;
  16.         unsettled = new boolean[numberofvertices + 1];
  17.         settled = new boolean[numberofvertices + 1];
  18.         adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
  19.         key = new int[numberofvertices + 1];
  20.         parent = new int[numberofvertices + 1];
  21.     }
  22.    public int getUnsettledCount(boolean unsettled[])
  23.     {
  24.         int count = 0;
  25.         for (int index = 0; index < unsettled.length; index++)
  26.         {
  27.             if (unsettled[index])
  28.             {
  29.                 count++;
  30.             }
  31.         }
  32.         return count;
  33.     }
  34.  
  35.     public void primsAlgorithm(int adjacencyMatrix[][])
  36.     {
  37.         int evaluationVertex;
  38.         for (int source = 1; source <= numberofvertices; source++)
  39.         {
  40.             for (int destination = 1; destination <= numberofvertices; destination++)
  41.             {
  42.                 this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
  43.             }
  44. }
  45. for (int index = 1; index <= numberofvertices; index++)
  46.         {
  47.             key[index] = INFINITE;
  48.         }
  49.         key[1] = 0;
  50.         unsettled[1] = true;
  51.         parent[1] = 1;
  52.  
  53.         while (getUnsettledCount(unsettled) != 0)
  54.         {
  55.             evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
  56.             unsettled[evaluationVertex] = false;
  57.             settled[evaluationVertex] = true;
  58.             evaluateNeighbours(evaluationVertex);
  59.         }
  60.     } 
  61.  private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
  62.     {
  63.         int min = Integer.MAX_VALUE;
  64.         int node = 0;
  65.         for (int vertex = 1; vertex <= numberofvertices; vertex++)
  66.         {
  67.             if (unsettled[vertex] == true && key[vertex] < min)
  68.             {
  69.                 node = vertex;
  70.                 min = key[vertex];
  71.             }
  72.         }
  73.         return node;
  74.     }
  75. public void evaluateNeighbours(int evaluationVertex)
  76.     {
  77.  
  78.         for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
  79.         {
  80.             if (settled[destinationvertex] == false)
  81.             {
  82.                 if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
  83.                 {
  84.                     if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
  85.                     {
  86.                         key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
  87.                         parent[destinationvertex] = evaluationVertex;
  88.                     }
  89.                     unsettled[destinationvertex] = true;
  90.                 }
  91.             }
  92.         }
  93.     }
  94. public void printMST()
  95.     {
  96.         System.out.println("SOURCE  : DESTINATION = WEIGHT");
  97.         for (int vertex = 2; vertex <= numberofvertices; vertex++)
  98.         {
  99.             System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
  100.         }
  101. public static void main(String... arg)
  102.     {
  103.         int adjacency_matrix[][];
  104.         int number_of_vertices;
  105.         Scanner scan = new Scanner(System.in);
  106.  
  107.         try
  108.         {
  109.             System.out.println("Enter the number of vertices");
  110.             number_of_vertices = scan.nextInt();
  111.             adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
  112.  
  113.             System.out.println("Enter the Weighted Matrix for the graph");
  114.             for (int i = 1; i <= number_of_vertices; i++)
  115.             {
  116.                 for (int j = 1; j <= number_of_vertices; j++)
  117.                 {
  118.                     adjacency_matrix[i][j] = scan.nextInt();
  119.                     if (i == j)
  120.                     {
  121.                         adjacency_matrix[i][j] = 0;
  122.                         continue;
  123. }
  124.                     if (adjacency_matrix[i][j] == 0)
  125.                     {
  126.                         adjacency_matrix[i][j] = INFINITE;
  127.                     }
  128.                 }
  129.             }
  130.  
  131.             Prims prims = new Prims(number_of_vertices);
  132.             prims.primsAlgorithm(adjacency_matrix);
  133.             prims.printMST();
  134.  
  135.         } catch (InputMismatchException inputMismatch)
  136.         {
  137.             System.out.println("Wrong Input Format");
  138.         }
  139.         scan.close();
  140.     }
  141. }
  142.     }

Related Solutions

Prove that Kruskal’s algorithm finds a minimum weight spanning tree.
Prove that Kruskal’s algorithm finds a minimum weight spanning tree.
Give the entire code for Minimum spanning tree using Boruvka's algorithm in java (not copy-pasted from...
Give the entire code for Minimum spanning tree using Boruvka's algorithm in java (not copy-pasted from any other website)
Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G....
Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G. (i) Show that either T contains the n-1 smallest edges, or the n-1 smallest edges form a subgraph which contains a cycle. (ii) Show that if an edge (a, b) is not in T and if P is the unique path in T from a to b, then for each edge e in P the weight of e is less than the weight of...
Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum...
Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum element in an unsorted list. Second, convert your recursive algorithm to a non-recursive (or iterative) implementation. For your input, populate an "unsorted list" with random elements between 1 and 1,000,000.
minimum spanning tree: find a connected subgraph whose total edge cost is minimized (python code)
minimum spanning tree: find a connected subgraph whose total edge cost is minimized (python code)
AVL tree; Insert and Range Minimum operation in Java code.
AVL tree; Insert and Range Minimum operation in Java code.
In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a)...
In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key...
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode. Do not use function call to either Min or delete done in the class. Write this from scratch. (No need to ensure AVL properties, just show it for a generic BST) Node * extract min(Node * x) { }
Show that a breadth-first spanning tree contains the shortest paths be- tween the root to every...
Show that a breadth-first spanning tree contains the shortest paths be- tween the root to every other vertex.
Develop a recursive algorithm to find the smallest and largest element in an array and trace...
Develop a recursive algorithm to find the smallest and largest element in an array and trace the recursive function with appropriate message. using c++ add comment to the code
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT