[text] mst

Viewer

  1. //import required classes and packages  
  2. import java.lang.*;   
  3. import java.util.*;   
  4. import java.io.*;   
  5.   
  6. //creating MinimumSpanningTreeExample class to implement Prim's algorithm in Java     
  7. class MinimumSpanningTreeExample {   
  8.     // Define the count of vertices available in the graph  
  9.     private static final int countOfVertices = 9;   
  10.     
  11.     // create findMinKeyVertex() method for finding the vertex v that has minimum key-value and that is not added MST yet  
  12.     int findMinKeyVertex(int keys[], Boolean setOfMST[])   
  13.     {   
  14.         // Initialize min value and its index  
  15.         int minimum_index = -1;   
  16.         int minimum_value = Integer.MAX_VALUE;  
  17.           
  18.         //iterate over all vertices to find minimum key-value vertex  
  19.         for (int vertex = 0; vertex < countOfVertices; vertex++)   
  20.             if (setOfMST[vertex] == false && keys[vertex] < minimum_value) {   
  21.                 minimum_value = keys[vertex];   
  22.                 minimum_index = vertex;   
  23.             }   
  24.     
  25.         return minimum_index;   
  26.     }   
  27.     
  28.     // create showMinimumSpanningTree for printing the constructed MST stored in mstArray[]   
  29.     void showMinimumSpanningTree(int mstArray[], int graphArray[][])   
  30.     {   
  31.         System.out.println("Edge \t\t Weight");   
  32.         for (int j = 1; j < countOfVertices; j++)   
  33.             System.out.println(mstArray[j] + " <-> " + j + "\t \t" + graphArray[j][mstArray[j]]);   
  34.     }   
  35.     
  36.     // create designMST() method for constructing and printing the MST. The graphArray[][] is an adjacency matrix that defines the graph for MST.  
  37.     void designMST(int graphArray[][])   
  38.     {   
  39.         // create array of size total number of vertices, i.e., countOfVertices for storing the MST  
  40.         int mstArray[] = new int[countOfVertices];   
  41.     
  42.         // create keys[] array for selecting an edge having minimum weight in cut   
  43.         int keys[] = new int[countOfVertices];   
  44.     
  45.         // create setOfMST array of type boolean for representing the set of vertices included in MST   
  46.         Boolean setOfMST[] = new Boolean[countOfVertices];   
  47.     
  48.         // set the value of the keys to infinite   
  49.         for (int j = 0; j < countOfVertices; j++) {   
  50.             keys[j] = Integer.MAX_VALUE;   
  51.             setOfMST[j] = false;   
  52.         }   
  53.     
  54.         // set value 0 to the 1st vertex because first vertes always include in MST.   
  55.         keys[0] = 0; // it select as first vertex   
  56.         mstArray[0] = -1; // set first value of mstArray to -1 to make it root of MST   
  57.     
  58.         // The vertices in the MST will be equal to the countOfVertices   
  59.         for (int i = 0; i < countOfVertices - 1; i++) {   
  60.             // select the vertex having minimum key and that is not added in the MST yet from the set of vertices   
  61.             int edge = findMinKeyVertex(keys, setOfMST);   
  62.     
  63.             // Add the selected minimum key vertex to the setOfMST   
  64.             setOfMST[edge] = true;   
  65.     
  66.             // change the key value and the parent index of all the adjacent vertices of the selected vertex. The vertices that are not yet included in Minimum Spanning Tree are only considered.   
  67.             for (int vertex = 0; vertex < countOfVertices; vertex++)   
  68.     
  69.                 // The value of the graphArray[edge][vertex] is non zero only for adjacent vertices of m setOfMST[vertex] is false for vertices not yet included in Minimum Spanning Tree   
  70.                 // when the value of the graphArray[edge][vertex] is smaller than key[vertex], we update the key  
  71.                 if (graphArray[edge][vertex] != 0 && setOfMST[vertex] == false && graphArray[edge][vertex] < keys[vertex]) {   
  72.                     mstArray[vertex] = edge;   
  73.                     keys[vertex] = graphArray[edge][vertex];   
  74.                 }   
  75.         }   
  76.     
  77.         // print the constructed Minimum Spanning Tree   
  78.         showMinimumSpanningTree(mstArray, graphArray);   
  79.     }   
  80.     //main() method start  
  81.     public static void main(String[] args)   
  82.     {   
  83.           
  84.         MinimumSpanningTreeExample mst = new MinimumSpanningTreeExample();   
  85.         int graphArray[][] = new int[][]{{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },   
  86.                     { 4, 0, 8, 0, 0, 0, 0, 11, 0 },   
  87.                     { 0, 8, 0, 7, 0, 4, 0, 0, 2 },   
  88.                     { 0, 0, 7, 0, 9, 14, 0, 0, 0 },   
  89.                     { 0, 0, 0, 9, 0, 10, 0, 0, 0 },  
  90.                     { 0, 0, 4, 14, 10, 0, 2, 0, 0 },  
  91.                     { 0, 0, 0, 0, 0, 2, 0, 1, 6 },  
  92.                     { 8, 11, 0, 0, 0, 0, 1, 0, 7 },  
  93.                     { 0, 0, 2, 0, 0, 0, 6, 7, 0 }};   
  94.     
  95.         // Print the Minimum Spanning Tree solution   
  96.         mst.designMST(graphArray);   
  97.     }   
  98. }  

Editor

You can edit this paste and save as new:


File Description
  • mst
  • Paste Code
  • 08 May-2024
  • 4.76 Kb
You can Share it: