Algoritmul lui Kruskal

#include <iostream>

using namespace std;

int main()
{
    struct muchie
{
int x,y;
float cost;
} b[30],f;
int n,m,i,k,ct,l[30],j;

cout<<"nr. de varfuri"; cin>>n;
cout<<"nr. de muchii"; cin>>m;
for(i=1;i<=m;i++)
{
cout<<"muchia "<<i<<"( x,";
cin>>b[i].x;
cout<<"y) = ";
cin>>b[i].y;
cout<<"costul muchiei = ";
cin>>b[i].cost;
}
for(i=1;i<=n;i++)
l[i]=i;
// ordonarea muchiilor dupa cost
for(i=1;i<m;i++)
for(j=i+1;j<=m;j++)
if(b[i].cost>b[j].cost)
{
f=b[i];
b[i]=b[j];
b[j]=f;
}
k=0;
ct=0;
i=1;
// nr. de muchii selectate
// costul total
while(k<n-1)
{
if(l[b[i].x]!=l[b[i].y])
{
k++;
ct+=b[i].cost;
for(j=1;j<=n;j++)
if(l[j]==l[b[i].x])
l[j]=l[b[i].y];
cout<<b[i].x<<" "<<b[i].y<<endl;
}
i++;
}
cout<<"Costul total = "<<ct<<endl;
    return 0;
}
%d bloggers like this: