can anyone change/edit this prims algorithm program? the output needs to be the

Question

can anyone change/edit this prims algorithm program? the output needs to be the same. I just want to find different ways to do prims algorithm. thank you.

import java.util.InputMismatchException;
import java.util.Scanner;

public class PrimsAlgorithm {
  
public boolean unsettle[]; // required variables
public boolean settle[];
public int numofv;
public int matval[][];
public int key[];
public static final int INF = 999;
public int parent[];
  
// initializes no of vertices and matrices
public PrimsAlgorithm(int numofv) {
this.numofv = numofv;
unsettle = new boolean[numofv + 1];
settle = new boolean[numofv + 1];
matval = new int[numofv + 1][numofv + 1];
key = new int[numofv + 1];
parent = new int[numofv + 1];
}

public int getUnsettledCount(boolean unsettle[]) { // method to find th weights
int count = 0;
for (int index = 0; index < unsettle.length; index++){
if (unsettle[index])
count++;
}
return count;
}
  
public void primsAlgorithm(int matval[][]){ // applying prims algo
  
int evalV;
for (int s = 1; s <= numofv; s++)
for (int d = 1; d <= numofv; d++)
this.matval[s][d] = matval[s][d];
for (int index = 1; index <= numofv; index++)
key[index] = INF;
key[1] = 0;
unsettle[1] = true;
parent[1] = 1;
  
while (getUnsettledCount(unsettle) != 0){
evalV = getMimumKeyVertexFromUnsettled(unsettle);
unsettle[evalV] = false;
settle[evalV] = true;
evaluateNeighbours(evalV);
}
}
  
private int getMimumKeyVertexFromUnsettled(boolean[] unsettle2) { // methid to find minimum weights of all the available
int min = Integer.MAX_VALUE;
int node = 0;
for (int v = 1; v <= numofv; v++){
if (unsettle[v] == true && key[v] < min){
node = v;
min = key[v];
}
}
return node;
}
  
public void evaluateNeighbours(int evalV){// method to find the nearest neighbors
for (int dv = 1; dv <= numofv; dv++){
if (settle[dv] == false){
if (matval[evalV][dv] != INF){
if (matval[evalV][dv] < key[dv]){
key[dv] = matval[evalV][dv];
parent[dv] = evalV;
}
unsettle[dv] = true;
}
}
}
}
  
// method to print Minimum spanning tree and weight.
public void printMST(){
int weight=0;
for (int v = 2; v <= numofv; v++)
weight=weight+matval[parent[v]][v];
System.out.println("The Weight of the derived MST is : "+weight);
System.out.print("The edges in the MST =");
for (int v = 2; v <= numofv; v++)
System.out.print(parent[v] + " --> " + v +", ");
}

public static void main(String... arg){
int adjancymtx[][];
int v;
Scanner c = new Scanner(System.in);
try{
System.out.println("Enter the number of vertices");
v = c.nextInt();
adjancymtx = new int[v + 1][v + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= v; i++){
for (int j = 1; j <= v; j++){
adjancymtx[i][j] = c.nextInt();
if (i == j){
adjancymtx[i][j] = 0;
continue;
}
//changes the value to infinity -0
if (adjancymtx[i][j] == 0)
adjancymtx[i][j] = INF;
}
}
// prints the adjacency matrix
System.out.println("The Adjacency Matrix : ");
System.out.print(" ");
for (int i=1;i<=v;i++ ){
System.out.print(" "+i); // columns
}
System.out.println();
for (int i = 1; i <= v; i++){
System.out.print(i); // rows
for (int j = 1; j <= v; j++)
System.out.print(" "+adjancymtx[i][j]);
System.out.println();
}
PrimsAlgorithm pa = new PrimsAlgorithm(v);
pa.primsAlgorithm(adjancymtx);
pa.printMST();

} catch (InputMismatchException inputMismatch){
System.out.println("Wrong Input Format");
}
c.close();
}
  
}

Explanation / Answer

class Prims
{
   private int vertices;
   public Prims(int vertices)
   {
       this.vertices=vertices;
   }
   public int minKey(int[] key, boolean[] mst)
   {
       int min=Integer.MAX_VALUE;
       int minIndex=-1;
       for(int i=0;i<vertices;i++)
       {
           if(!mst[i]&&key[i]<=min){
               min=key[i];
               minIndex=i;
           }
       }
       return minIndex;
   }
   public void print(int parent[],int n,int[][] G)
   {
       System.out.println("Edge Weight");
       for(int i=1;i<vertices;i++)
           System.out.println(parent[i]+" - "+i+" "+G[i][parent[i]]);
   }
   public void primMST(int[][] G)
   {
       int parent[] = new int[vertices];
       int key[]=new int [vertices];
       boolean mst[]=new boolean[vertices];
       for(int i=0;i<vertices;i++)
       {
           key[i]=Integer.MAX_VALUE;
           mst[i]=false;
       }
       key[0]=0;
       parent[0]=-1;
       for(int j=0;j<vertices-1;j++)
       {
           int u=minKey(key,mst);
           mst[u]=true;
           for(int i=0;i<vertices;i++)
           {
               if(G[u][i]!=0&&!mst[i]&&G[u][i]<key[i])
               {
                   parent[i]=u;
                   key[i]=G[u][i];
               }
           }
       }
       print(parent,vertices,G);
   }
   public static void main(String[] args)
   {
       /*
       int G[][]=new int[][]{declare weights};
       Prims obj = new Prims(NumberOfVertices);
       obj.primMST(G);
       */
   }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.