Codificare Prufer

Consideram un arbore partial oarecare T din T(Kn). Algoritmul lui Prufer de codificare a arborelui T conduce la constructia unui (n-2)-vector

c(c1, c2,…, cn-2) peste [n] astfel incat t->c=( c1, c2,…, cn-2).El consta in repetarea de n-2 ori, respectiv pentru j=1, 2, …, n-2, a urmatorului grup de operatii:

(1) se determina multimea S a varfurilor de grad unu( a terminalelor) din T: S=term(T);

(2) se selecteaza varful minim: xj =min S;(3) se noteaza in vectorul cod varful cj adiacent lui xj;(4) se sterge varful terminal xj din arborele T : T –xj ->T.

Observatii: (1) In procesul codificarii Prufer sunt obtinute cele n-2 componente ale vectorului cod c. Determinarea fiecarei componente cj este insotita de stergerea varfului terminal minim xj din T adiacent lui cj, iar graful obtinut este de asemenea arbore T-xj -> T . In total sunt sterse n-2 astfel de varfuri. Cele doua varfuri care raman sunt adiacente, iar unul dintre ele este varful maxim n.

(2) In vectorul cod obtinut, un varf x apare de dT(x)-1 ori. Astfel, varfurile terminale sunt singurele varfuri care nu apar in codul c.

//-------------------------------------------------------------------------------------int GetInteger(const char* prompt, int min, int max, const char* err_msg=""){

int num;

for(;;){

cout << prompt ;cin >> num;if(cin.fail() || num < min || num > max){

cin.clear();cin.ignore(1024,'\n');cout << err_msg << endl;cout << "Dati un intreg intre " << min << " si " << max << endl;

}else break;

}

return num;}

//-------------------------------------------------------------------------------------int s[50]; void df_r(int **T, int nod, int vf){int k; s[nod]=1; for(k=1;k<=vf;k++) if(T[nod][k]==1) {T[k][nod]=0; if(s[k]==0) df_r(T, k, vf); }} //-------------------------------------------------------------------------------------

int GetTree(int ** T, int vf){

cout << "Introduceti cele " << vf-1 << " muchii ale arborelui : .\n";

int i, j;

for(int x = 1; x < vf; x++) //citim cele n-1 muchii{

cout << "\nMuchia #" << x << '\n';i = GetInteger("", 1, vf);j = GetInteger("", 1, vf);

if(i == j) // acest graf nu este arbore{

cout << "Un graf nu este arbore daca un varf este conectat la el insusi. Incercati din nou.";

x--;continue;

}else if(T[i][j]) // daca aceasta muchie deja a fost introdusa{

cout << "Ati introdus deja aceasta muchie.Incercati din nou.";x--;continue;

}

T[i][j] = 1;T[j][i] = 1;

}int ** a = new int* [vf + 1];

for(i=1;i<=vf;i++) {a[i] = new int[vf + 1]; for(j=1;j<=vf;j++) a[i][j]=T[i][j]; }df_r(a,1, vf);int suma=0;for(i=1;i<=vf;i++) suma+=s[i];if(suma!=vf){cout<<"Graful nu este conex, deci nu este arbore"<<endl;return 0;} return 1; }//-------------------------------------------------------------------------------------

void afisareCod(int * c, int vf){

cout << "\nCodul prufer: ( ";

for(int i = 1; i <=vf-2; i++)cout << c[i] << " ";

cout << ")\n";}//-------------------------------------------------------------------------------------void CreareCod(int ** T, int * c, int vf){

int min, adj;

for(int x = 1; x <= vf-2; x++){

// 1. gaseste varful de grad I cu valoarea cea mai micaint grad;

for(min = 1; min <= vf; min++){

grad = 0;

for(int j = 1; j <= vf; j++)//calculam gradul fiecarui varf pana gasim unul care sa aiba gradul I

if(T[min][j]!=0){

adj = j;grad++;

}

if(grad == 1)break;

}

// 2. face varful adiacent urmatorul varf din vectorul cod

c[x] = adj;for(int j = 1; j <= vf; j++){

T[min][j] = 0;T[j][min] = 0;

}

// 3. Repeta pana cand mai raman doua varfuri}

}

//-------------------------------------------------------------------------------------void af_arbore(int ** T, int vf){cout<<endl<<"afisare arbore"<<endl;

int i,j;

for(i = 1; i <= vf; i++){

for(j = i+1; j <= vf; j++)if(T[i][j])cout<<i<<" "<<j<<endl;

}cout << endl;

}//-------------------------------------------------------------------------------------int main(){int i;

int vf = GetInteger("\nDati numarul de varfuri: ", 3, INT_MAX,"Doar arborii cu cel putin 3 varfuri

au cod Prufer.");

int ** T1 = new int* [vf + 1];

for( i = 1; i <= vf ; i++){

T1[i] = new int[vf + 1];for(int j = 1; j <= vf; j++)

T1[i][j] = 0;

};

int * c = new int[vf];for(i = 0; i < vf; i++)

c[i] = 0;

int ok=GetTree(T1, vf);if(ok==0) {system("pause"); return 0;}af_arbore(T1, vf);CreareCod(T1, c, vf);afisareCod(c, vf);

delete []T1;system("pause");

return 0;}

//-------------------------------------------------------------------------------------//-------------------------------------------------------------------------------------