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 Kruskal

Explicarea algoritmului
Pasul 1: Initial, fiecare nod va fi un arbore. Vom avea deci o padure de n arbori.
Apoi, se executa de n-1 ori pasul urmator:
Pasul 2: Se cauta muchia de cost minim care uneste noduri care apartin la doi arbori diferiti. Se selecteaza muchia respectiva.
Dupa selectarea a n-1 muchii, se obtine APM.

Prezentarea video a algoritmului:


Simularea algoritmului

Programul in C++
#include<fstream.h>
int a[20][20], n, m;
int arb[20], cost[20];
const infinit = 10000;
struct muchie
  {
  int x, y, c;
  };
muchie edge[20];
 
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;
     edge[i].x=x;
     edge[i].y=y;
     edge[i].c=c;
   }
  f.close();
}
void init()
{
  int i;
  for (i=1; i<=n; i++)
    arb[i]=i;
}
 
void sort()
{
  int i, j;
  muchie aux;
  for(i=1; i<m; i++)
    for(j=i+1; j<=m; j++)
      if(edge[i].c>edge[j].c)
    { aux=edge[i]; edge[i]=edge[j]; edge[j]=aux;}
}
 
void apm_k()
{ cout<<endl;
  int ct=0, k=0, i=1, j;
  while(k<n-1)
  {
    if(arb[edge[i].x]!=arb[edge[i].y])
     {
       k++; //numar muchiile adaugate
       ct=ct+edge[i].c;
       cout<<"["<<edge[i].x<<" "<<edge[i].y<<"]"<<" ";
       //"colorez" toate nodurile de culoarea v in culoarea w
       int v=arb[edge[i].y]; int w=arb[edge[i].x];
       for(j=1; j<=n; j++)
         if(arb[j]==v) arb[j]=w;
     }
    i++;
  }
 cout<<endl<<"cost total al apm:"<<ct;
}
 
void main()
{
  citiregraf();
  init();
  sort();
  apm_k();
}