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();

    }

    }

OUTPUT:-

   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