//Program to implement Prim’s Algorithm
import java.util.*;
import java.io.*;
class Graph
{
int g[][],v,e;
void create_graph() throws IOException
{
int a,b,i,j,w;
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter no of vertices");
v=Integer.parseInt(in.readLine());
System.out.println("Enter no of edges");
e=Integer.parseInt(in.readLine());
g=new int [v+1][v+1];
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
g[i][j]=0;
for(i=1;i<=e;i++)
{
System.out.println("Enter no of information");
a=Integer.parseInt(in.readLine());
b=Integer.parseInt(in.readLine());
System.out.println("Enter weight");
w=Integer.parseInt(in.readLine());
g[a][b]=g[b][a]=w;
}
}
void prim()
{
int current,d[],p[],visited[];
d=new int[v+1];
p=new int[v+1];
visited=new int[v+1];
for(int i=1;i<=v;i++)
{
d[i]=32767;
p[i]=0;
visited[i]=0;
}
current=1;
d[current]=0;
visited[current]=1;
int c=1;
while (c!=v)
{
for(int i=1;i<=v;i++)
{
if(g[current][i]!=0 && visited[i]!=1)
if (g[current][i]
{
d[i]=g[current][i];
p[i]=current;
}
}
int min=32767;
for(int i=1;i<=v;i++)
{
if (visited[i]!=1 && d[i]
{
min=d[i];
current=i;
}
}
visited[current]=1;
c=c+1;
}
int mincost=0;
for(int i=1;i<=v;i++)
mincost=mincost+d[i];
System.out.println("Minimum cost ="+mincost);
}
}
class Graphtest
{
public static void main(String args[]) throws IOException
{
Graph G1=new Graph();
G1.create_graph();
G1.prim();
}
}
/*OUTPUT:
Enter no of vertices 5
Enter no of edges 10
Enter no of information 1
2
Enter weight 5
Enter no of information 1
3
Enter weight 50
Enter no of information 2
3
Enter weight 15
Enter no of information 5
1
Enter weight 20
Enter no of information 5
3
Enter weight 25
Enter no of information 4
1
Enter weight 25
Enter no of information 1
3
Enter weight 55
Enter no of information 4
2
Enter weight 56
Enter no of information 2
5
Enter weight 58
Enter no of information 3
5
Enter weight 58
Minimum cost =65 Process Exit...*/
Posts
ShareThis
0 comments:
Post a Comment