Arbori partiali de cost minim

Fie un graf G, neorientat, conex. Fiecare muchie (i,j) are asociat un cost Ci,j>=0. Arborele partial de cost minim (APM) asociat grafului G va cuprinde numai acele muchii pentru care suma costurilor acestora sa fie minima.

Pentru gasirea APM se pot folosi doi algoritmi.
Primul este algoritmul lui Kruskal, ce are complexitatea O(m log m), unde m e numarul de muchii, iar al doilea este algoritmul lui Prim, care are complexitatea de O(n^2), unde n e numarul de noduri. In functie de numarul de muchii vom alege un algoritm sau altul.
De exemplu, daca numarul de muchii este mic, vom prefera algoritmul lui Kruskal.
Daca insa numarul de muchii e mare si numarul lor se apropie de n^2, atunci e de preferat sa folosim algoritmul lui Prim.

Ambii algoritmi au la baza tehnica Greedy.


Algoritmul lui Prim

Explicarea algoritmului


Simularea algoritmului

Programul in C++
#include<fstream.h>
int a[20][20], n, m;
int viz[20], cost[20], tata[20];
const infinit = 10000;
 
void citiregraf()
{
  int i,x, y, j, c;
  ifstream f ("apm_prim.in");
  f>>n>>m;
  for(i=1; i<=m; i++)
   { f>>x>>y>>c;
    a[x][y]=a[y][x]=c;
   }
  for (i=1; i<=n; i++)
    for(j=1; j<=n; j++)
      if(a[i][j]==0) a[i][j]=infinit;
  f.close();
}
 
void main()
{ int i, j, s, k, min, x, y;
  citiregraf();
  cout<<"dati nodul de start"; cin>>s;
 
  for(i=1; i<=n; i++)
    {
      viz[i]=0;
      cost[i]=0;
      tata[i]=0;
    }
  viz[s]=1;
 
  for(k=2; k<=n; k++)
    {
     min=infinit;
     for(i=1; i<=n; i++)
       for(j=1; j<=n; j++)
     if( (viz[i]==1) && (viz[j]==0) && (a[i][j]<min) )
       {
         min=a[i][j];
         x=i; y=j;
       }
     viz[y]=1; tata[y]=x;
     cost[y]=a[x][y];
    }
  for(i=1; i<=n; i++)
    cout<<tata[i]<<" ";
  cout<<endl;
  for(i=1; i<=n; i++)
    cout<<cost[i]<<" ";
}