Algoritmul lui Prim
Algoritmul este urmatorul: -Se porneste de la un nod al grafului. -La fiecare pas din cei n-1, se va adauga arborlui obtinut la pasul anterior o muchie de cost minim.Minimul se refera la muchiile care au o singura extremitate in arborele obtinut la pasul anterior. |
#include<iostream>
#include<fstream> using namespace std; ifstream f("graf.txt"); int n,S[50],i,j,k,C,lin,col; float Min,c[50][50]; const float PInfinit = 1.e10; void Citesc() { f>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) c[i][j]=0; else c[i][j]=c[j][i]=PInfinit; while(f>>i>>j>>C) c[i][j]=c[j][i]=C; f.close(); } main() { Citesc(); S[1]=1; for(k=1;k<=n-1;k++) { Min=PInfinit; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(S[i]==1 && S[j]==0 && Min>c[i][j]) { Min=c[i][j]; lin=i; col=j; } cout<<lin<<" "<<col<<" "<<Min<<endl; S[col]=1; } } |