Se dă un graf neorientat G=(U,X), conex, ponderat cu N noduri. Se cere sa se arborele partial de cost minim asociat grafului dat.
Datele de intrare se vor citi din fisierul text graf.in, care conţine pe prima linie două numere naturale n (numărul de noduri) şi m (numărul de muchii), iar pe următoarele m linii triplete de numere naturale x, y, cost, care reprezintă muchia (x,y) şi costul asociat acesteia.
Datele de iesire vor fi afişate pe ecran în următorul format:
muchiile care formează arborele parţial de cost minim
costul arborelui partial determinat rezultatul va fi afisat pe ecran.
graf.in
9 11
3 8 1
2 3 2
1 2 1
1 3 2
1 4 1
4 5 2
5 6 3
3 6 1
3 9 2
8 9 3
7 8 3
Rezultat
Arborele parţial de cost minim conţine muchiile:
(3,8), (1,2), (1,4), (3,6), (6,9), (2,3), (4,5), (7,8)
Costul APCM:12
Indicaţii de rezolvare:
Există situaţii în care se poate asocia o valoare suplimentară unei muchii, valoare care reprezintă distanţa dintre noduri, costul asociat muchiei, timpul de parcurs al muchiei, etc. Această nouă caracteristică se mai numeşte si pondere.
Pentru a memora un graf ponderat în memoria calculatorului se pot utiliza mai multe variante :
matricea de adiacenţă: care in dreptul muchiei (x,y) va memora valoarea costului muchiei
matricea costurilor: este o matrice care are un număr de linii egal cu numărul de muchii şi trei coloane care memorează muchia (x,y) şi costul acesteia.
Definiţie: Costul grafului este suma ponderilor tuturor muchiilor din graf.
Definiţie: A
Program Code Bloks:
//Algoritmul lui KRUSKAL
#include<iostream>
#include<fstream>
using namespace std;
int a[50][4],n,m; //n-nr. de noduri, m-nr. de muchii
//citirea din fisier a informatiilo si construirea matricei costurilor
void citire(int a[50][4], int &n, int &m)
{ ifstream f("matrice.in");
f>>n>>m;
for(int i=1;i<=m;i++)
f>>a[i][1]>>a[i][2]>>a[i][3];
f.close();
}
//afisarea pe ecran
void afisare(int a[50][4], int m)
{cout<<"Maticea costurilor este:"<<endl;
for(int i=1;i<=m;i++)
{ for(int j=1;j<=3;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
//ordonarea matricei costurilor dupa ultima coloana
void ordoneaza(int a[50][4], int m)
{//Buble – sort
int ok;//presupun matricea ordonata dupa ultima coloana
do
{ok=1;
for(int i=1;i<=m-1;i++)
if(a[i][3]>a[i+1][3])
{ //se inverseaza linia i cu linia i+1
for(int j=1;j<=3;j++)
{int aux=a[i][j];
a[i][j]=a[i+1][j];
a[i+1][j]=aux;
ok=0;
}
}while(ok==0);
}
void kruskal(int a[50][4],int m,int n)
{ //construim un vector v cu un numar de elemente egal cu numarul de noduri,
// v[i]->componenta conexa a nodului i
int v[20],cost=0,nr_muchii=0,k;
for(int i=1;i<=n;i++)
v[i]=i; //fiecare nod formeaza o componenta conexa
k=1;//numarul liniei care se prelucreaza dim matrice
cout<<"APCM contine urmatoarele muchii:"<<endl;
while(nr_muchii<n-1)
{
//linia k se adauga sau nu la APCM?
int x=a[k][1];
int y=a[k][2];
if(v[x]!=v[y])//x si y fac parte din componente conexe diferite
{
cost=cost+a[k][3];
nr_muchii++;
cout<<"("<<x<<","<<y<<")";
int aux=v[y];
for(int i=1;i<=n;i++)
if (v[i]==aux)
v[i]=v[x];
}
k++;
}
cout<<"Costul APCM este "<<cost<<endl;
}
int main()
{ citire(a,n,m);
cout<<"Initial:"<<endl;
afisare(a,m);
ordoneaza(a,m);
cout<<"Dupa ordonare crescatoare a coloanei 3:"<<endl;
afisare(a,m);
kruskal(a, m, n);
return 0;
}