PROGRAM TO FIND THE MINIMUM SPANNING TREE USING PRIM'S ALGORITHM

import java.io.*;
import java.util.*;


class Graph
{


int weight[][]=new int[20][20];
int visited[]=new int[20];
int d[]=new int[20];
int p[]=new int[20];
int v,e;


int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/


 void creategraph()
 {
int i,j,a,b,w;
System.out.print("\nEnter number of vertices : ");
v=getNumber();
System.out.print("\nEnter number of edges : ");
e=getNumber();


for (i=1;i<=v;i++)
for (j=1;j<=v;j++)
weight[i][j]=0;


for (i=1;i<=v;i++)
{
 p[i] = visited[i] =0;
 d[i] = 32767;
}


for (i=1;i<=e;i++)
{
 System.out.print("\nEnter edge a,b and weight w : ");
 a=getNumber();
 b=getNumber();
 w=getNumber();
 weight[a][b]=weight[b][a]=w;
}
 }
 void PrimAlgorithm()
 {
creategraph();
int current, totalvisited, mincost,i;
current=1; d[current]=0;
totalvisited =1;
visited[current]=1;


while(totalvisited!=v)
{
 for (i=1;i<=v;i++)
 {
if(weight[current][i]!=0)
if(visited[i]==0)
if(d[i]>weight[current][i])
{
d[i] = weight[current][i];
p[i] = current;
}
 }
mincost= 32767;
for (i=1;i<=v;i++)
{
if(visited[i] ==0)
if (d[i] <mincost)
{
mincost = d[i];
current = i;
}
}
visited[current] = 1;
totalvisited++;
} /*end of while loop */
mincost =0;
for (i=1;i<=v;i++)
mincost += d[i];
System.out.println("\nMinimum cost = "+mincost);
System.out.println("\nMinimum span tree is");


for (i=1;i<=v;i++)
System.out.println("\nvertex "+i+" is connected to "+p[i]);
 }   /*end of prim */
}






class Prim
{
 public static void main(String args[])
 {
Graph g=new Graph();
g.PrimAlgorithm();
 }
}


/*
Enter number of vertices : 6


Enter number of edges : 9


Enter edge a,b and weight w : 1 2 6


Enter edge a,b and weight w : 1 3 3


Enter edge a,b and weight w : 2 3 2


Enter edge a,b and weight w : 2 4 5


Enter edge a,b and weight w : 3 5 4


Enter edge a,b and weight w : 3 4 3


Enter edge a,b and weight w : 4 5 2


Enter edge a,b and weight w : 4 6 3


Enter edge a,b and weight w : 5 6 5


Minimum cost = 13


Minimum span tree is


vertex 1 is connected to 0


vertex 2 is connected to 3


vertex 3 is connected to 1


vertex 4 is connected to 3


vertex 5 is connected to 4


vertex 6 is connected to 4
*/