Thursday, April 14, 2011

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