Skip to main content

Minimum Spanning Tree using Prim's algorithm [VERY IMPORTANT-Graphs]


CODE: 
import java.util.*;
import java.lang.*;
import java.io.*;


class GFG {
public static void main (String[] args) {
int graph[][] = new int[][] {{0, 2, 0, 6, 0},
                                    {2, 0, 3, 8, 5},
                                    {0, 3, 0, 0, 7},
                                    {6, 8, 0, 0, 9},
                                    {0, 5, 7, 9, 0},
                                   };
    primMST(graph);                                   
}
public static void primMST(int [][]graph){
   int [] parent= new int [5];
   boolean [] mstSet=new boolean [5];
   int [] key= new int [5];
   Arrays.fill(mstSet,false);
   Arrays.fill(key,Integer.MAX_VALUE);
   key[0]=0;parent[0]=-1;
   for(int i=0;i<4;i++){
       int u=minKey(key,mstSet);
       mstSet[u]=true;
       for(int v=0;v<5;v++){
           if(graph[u][v]<key[v] && graph[u][v]!=0 && mstSet[v]==false){
               parent[v]=u;
               key[v]=graph[u][v];
           }
       }
    }
    printMST(parent,5,graph);
}
public static int minKey(int [] key, boolean[] mstSet){
   int min=Integer.MAX_VALUE;int min_index=0;
   for(int v=0;v<5;v++){
       if(mstSet[v]==false && key[v]<min){
           min=key[v];
           min_index=v;
       }
   }
   return min_index;
}
public static void printMST(int [] parent, int V,int [][]graph){
   System.out.println("Edge"+"    "+"Weight");
   for(int i=1;i<V;i++){
       System.out.println(parent[i]+" "+"-"+i+"       "+graph[i][parent[i]]);
   }
}

}

Link to Code

Comments

Popular Posts

TARUNKUMAR RAWAT:Fourier Series and Fourier Transform

Tarunkumar Rawat Fourier Series: Click here to download Tarun Rawat Fourier Series Tarunkumar Rawat Fourier Transform: Click here to download TarunRawat Fourier Transform Steps to follow: 1) Click on the above link 2) Wait for 3 secs and click on the link 3) Wait for 5 secs and click on skip ad NOTE: We do require these ads to fund the site and provide books for free. Besides these are harmless and just require 5 secs waiting and nothing else. Please be patient for 5 secs and get your desired book for FREE!  IMPORTANT: We believe that every author deserves some respect and the same should be shown towards them by purchasing the books and lauding the efforts of author. Hence we recommend to buy the book. You can buy the book for an affordable rate in given below link: Using of PDF will be at your own risk and EXTC RESOURCES IS NOT RESPONSIBLE for any consequences of the same. We provide links for book and donot endorse piracy.  

Modern Digital and Analog Communication (BP Lathi,3rd ed)

Another Analog communication book: Modern Digital and Analog Communication (BP Lathi,3rd ed) : Click here to download Modern Digital and Analog Communication (BP Lathi,3rd ed) Copyright Disclaimer: This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.

Numerical methods with MATLAB

For Numerical methods along with MATLAB the best book is: Chapra Applied Numerical Methods MATLAB Engineers Scientists 3rd edition : Click here to download Steven Chapra with MATLAB For altenate link : Click here to download Steen Chapra with MATLAB