ADSL Prims

#include <iostream>
using namespace std;

int n;
class graph
{
public:
    int cost[20][20],mincost;
    graph()
     {
    for(int i=0;i<=10;i++)
    {
    for(int j=1;j<=10;j++)

    {
    cost[i][j]=-1;
    }
     }
    mincost=0;

    } void prims();
};
int main()
{
graph g;
int c;

char ans;
do
{
cout<<"Enter total no.of houses\n";
cin>>n;
cout<<"Enter -1 if no.edge exist\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<"Enter cost between house no.\t"<<i<<"and house no.\t"<<j;
cin>>c;
g.cost[i][j]=g.cost[j][i]=c;
}
}

for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<"\n"<<g.cost[i][j];
}
}
g.prims();

cout<<"\nwant to continue?";
cin>>ans;
}while(ans=='Y'||ans=='y');
return 0;
}
void graph:: prims()
{
int min,row,col,visit[20],path[20],z;
for(int i=2;i<=n;i++)
{
visit[i]=0;
}
visit[1]=1;
z=1;
path[z++]=1;
cout<<"\nInitial cost is:"<<mincost;
for(int k=1;k<=n-1;k++)
{
min=999;
for(int i=1;i<=n;i++)
{
           for(int j=1;j<=n;j++)
           {
           if(visit[i]==1 && visit[j]==0)
           {
           if(cost[i][j]!=-1&&min>cost[i][j])
           {
           min=cost[i][j];
           row=i;
           col=j;
           }
           }
           }
}
cout<<"\nmin"<<min;
mincost=mincost+min;
visit[col]=1;
path[z++]=col;
cost[row][col]=-1;
cost[col][row]=-1;
}
cout<<"\nTotal min cost"<<mincost;
cout<<"Shorted path is";
for(int i=1;i<=n;i++)
cout<<path[i];

}

Comments

Popular Posts