arbore partial de cost minim

Arbore partial de cost minim

 

#include<fstream.h>
#include<iostream.h>
float a[20][20],min,cost;
int s[20],t[20],n,i,j,k,v;

void citire(char nume[20],float a[20][20],int &n)
{
int i,j;
float c;
fstream f(nume,ios::in);
f>>n;
for(i=1;i<=n;i++) a[i][i]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=100;
while(f>>i>>j>>c) a[i][j]=a[j][i]=c;
f.close();
}

void main()
{
cost=0;
citire(“graf2”,a,n);
cout<<n<<endl;
cout<<“nodul de pornire:”;cin>>v;
for(i=1;i<=n;i++)
if(i==v) s[i]=0;
else s[i]=v;

for(k=1;k<=n-1;k++)
{
min=100;
for(i=1;i<=n;i++)
if(s[i])
if(a[s[i]][i]<min)
{min=a[s[i]][i];
j=i;
}
t[j]=s[j];
cost+=a[s[j]][j];s[j]=0;
for(i=1;i<=n;i++)
if(s[i] && a[i][s[i]]>a[j][i]) s[i]=j;
}
cout<<“cost=”<<cost<<endl;
for(i=1;i<=n;i++) cout<<t[i]<<” “<<endl;
}

Leave a Comment