Algoritmul lui Kruskal
Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de algoritm greedy. Algoritmul funcționează în felul următor:
|
#include<iostream> #include<fstream> using namespace std; int n,nr_muchii,k=1,t[50],h[50],m[3][50],v[50],nod,cost; void citire() { ifstream f("graf.txt"); f>>n; while(f>>m[0][k]>>m[1][k]>>m[2][k]) k++; f.close(); } void sort() { int aux,i,j,inv=0; int n=k-1; while(inv==0) { inv=1; for(i=1;i<=n-1;i++) if(m[2][i]<m[2][i+1]) { aux=m[2][i]; m[2][i]=m[2][i+1]; m[2][i+1]=aux; aux=m[0][i]; m[0][i]=m[0][i+1]; m[0][i+1]=aux; aux=m[1][i]; m[1][i]=m[1][i+1]; m[1][i+1]=aux; inv=0; } } } int arb(int nod) { while(t[nod]) nod=t[nod]; return nod; } main() { citire(); sort(); k=1; do { while(arb(m[0][k])==arb(m[1][k])) k++; nr_muchii++; cout<<m[0][k]<<" "<<m[1][k]<<" "<<m[2][k]<<endl; cost=cost+m[2][k]; if(h[m[0][k]]==h[m[1][k]]) { t[m[0][k]]=m[1][k]; h[m[1][k]]++; } else if(h[m[0][k]]<h[m[1][k]]) t[m[0][k]]=m[1][k]; else t[m[1][k]]=m[0][k]; k++; }while(nr_muchii<n-1); cout<<endl<<"costul maxim= "<<cost; } |