Articole

În unele situații se cere gruparea elementelor unei mulțimi date într-o colecție de submulțimi disjuncte. Pentru o astfel de colecție sunt importante următoarele operații:

• stabilirea submulțimii din care face parte un anumit element
• pentru două elemente date, reuniunea submulțimilor din care fac parte aceste elemente

Pentru fiecare submulțime se stabilește un reprezentant – unul dintre elementele submulțimii. Fiecare element al submulțimii este asociat într-un anumit mod cu reprezentantul acesteia. În acest fel, operația de stabilire a submulțimii din care face parte un anumit element constă în simpla identificare a reprezentantului, iar operația de reuniune a două submulțimii constă în asocierea elementelor unei submulțimii cu reprezentantul celeilalte. Două elemente fac parte din aceeași submulțime dacă sunt asociate cu același reprezentant.

Utilizări

Operațiile cu mulțimi disjuncte pot fi folosite pentru determinarea componentelor conexe ale unui graf, astfel:

• inițial fiecare nod face parte din propria sa submulțime;
• pentru fiecare muchie (x,y) stabilim dacă x și y fac parte din submulțimi diferite, caz în care reunim cele două submulțimi;
• la final, fiecare submulțime reprezintă câte o componentă conexă a grafului dat.

O altă aplicație a acestor structuri de date este Algoritmul lui Kruskal pentru determinarea arborelui parțial de cost minim a unui graf neorientat cu costuri.

Păduri de mulțimi disjuncte

O modalitate eficientă de gestionare a submulțimilor și a operațiilor cu acestea este utilizarea unor structuri arborescente (a unei păduri), numite pădure de mulțimi disjuncte, în care:

• fiecare submulțime este reprezentată printr-un arbore cu rădăcină
• rădăcina fiecărui arbore este reprezentantul submulțimii
• operațiile se implementează astfel:
  • stabilirea submulțimii din care face parte un anumit element constă de regulă în identificarea rădăcinii arborelui din care face parte
  • reuniunea a două submulțimi constă în concatenarea arborilor: rădăcina unuia dintre arbore i se stabilește devine tată pentru rădăcina celuilalt

Gestionarea arborilor se poate face prin intermediul unui vector de tați:

• T[k] = 0, dacă k este rădăcină a unui arbore (și reprezentant al submulțimii corespunzătoare)
• T[k] = tatăl lui k în arborele din care face parte

Exemplu

Fie mulțimea {1,2,3,4,5,6,7, 8} cu submulțimile disjuncte {1,3,4}, {2,5,7} și {6,8}. O reprezentare prin păduri de mulțimi disjuncte poate fi:

Ei îi corespunde următorul vector de tați:

Dacă reunim submulțimile {2,5,7} și {6,8}, pădurea devine:

și îi corespunde următorul vector de tați:

Ambele operații (stabilirea submulțimii din care face parte un anumit element și reuniunea a două submulțimi) presupun identificarea reprezentantului unei submulțimii, adică a rădăcinii arborelui asociat submulțimii, operație ce presupune parcurgerea arborelui de la un nod spre rădăcină.

Implementare C++

Următoarea secvență C++ gestionează vectorul de tați T[], declarat global, prin intermediul a două funcții: int Radacina(int k), care determină rădăcina arborelui din care face parte nodul k (reprezentantul lui k) și void Unire(int k, int p), care realizează operația de reuniune a submulțimilor din care face parte k și p.

int T[...];

int Radacina(int k){
    if(T[k] == 0)
        return k;
    else
        return Radacina(T[k]);
}

void Unire(int k, int p)
{
    int rk = Radacina(k), rp = Radacina(p);
    if(rk != rp)
        T[rk] = rp;
}

Îmbunătățirea operațiilor

Această implementare a operațiilor poate conduce la arbori cu înălțime mare. Acest fapt are efect asupra operației de determinare a rădăcinii arborelui din care face parte un nod dat, care este cu atât mai rapidă cu cât lungimea lanțului de la nod la rădăcină este mai mică. În gestionarea pădurilor de mulțimi disjuncte se pot folosi două euristici care duc la complexitate aproape liniară în raport cu numărul total de operații:

• reuniunea după rang – se va păstra pentru fiecare arbore o aproximare a dimensiunii sale, numită rang. La reuniunea a doi arbori, cel cu rangul mai mic va deveni subarbore al celui cu rangul mai mare. Dacă cei doi arbori au același rang, rangul arborelui obținut va crește cu o unitate;
• comprimarea drumului – în funcția de determinare a rădăcinii pentru un nod dat, modificăm tații nodurilor de pe lanțul spre rădăcină, astfel încât acestea să devină fii ai rădăcinii. Altfel spus, legăm nodurile direct de rădăcină.

Următoarea secvență C++ îmbunătățește operațiile de mai sus cu ajutorul celor două euristici. Pentru determinarea rangurilor folosim un vector suplimentar, Rang[]:

int t[...];

int Radacina(int k){
    if(T[k] == 0)
        return k;
    else
    {
        int x = Radacina(T[k]);
        T[k] = x;
        return x;
    }
}

void Unire(int k, int p)
{
    int rk = Radacina(k), rp = Radacina(p);
    if(rk != rp)
    {
        if(Rang[rk] > Rang[rp])
            T[rp] = rk;
        else
        {
            T[rk] = rp;
            if(Rang[rk] == Rang[rp])
                Rang[rp] ++;
        }
    }
}

Bibliografie:

1. Cormen T, Leiserson C., Rivest R., Introducere în algoritmi, Editura Libris, 2000
2. Lucanu D., Craus M., Proiectarea algoritmilor, Editura Polirom, 2008
3. Giumale C., Introducere în analiza algoritmilor, Editura Polirom, 2004

Arbore liber

Un arbore este un graf conex și aciclic. Se mai numește și arbore liber.

Următoarele propoziții sunt adevărate:

• Un arbore cu n vârfuri are n-1 muchii.
• Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex.
• Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, s-ar obține un ciclu.
• Între oricare două vârfuri ale unui arbore există un lanț elementar unic.

Arbori cu rădăcină

Pentru un arbore se poate stabili un nod special, numit rădăcină. Putem spune că “agățăm” arborele în rădăcină, iar restul nodurilor cad.

Mai jos avem trei arbori cu rădăcină. Toți pornesc de la arborele de mai sus, dar diferă prin alegerea rădăcinii.

Terminologie

Fie un arbore cu rădăcina r și x un nod în acest arbore. Atunci:

• se numește ascendent al lui x orice nod y, diferit de x, aflat pe lanțul de la rădăcină la x;
  • rădăcina nu are ascendenți;
  • rădăcina este ascendent pentru toate nodurile din arbore;
• dacă y este ascendent al lui x și există muchia (y,x), atunci y se numește ascendent direct al lui x sau tatăl lui x;
  • rădăcina este singurul nod din arbore care nu are tată;
• un nod y este descendent al nodului x, diferit de y, dacă x aparține lanțului de la r la y;
  • dacă în plus există muchia (x,y), atunci y este descendent direct sau fiu al lui x;
  • un nod care nu are niciun descendent se numește frunză;
• două noduri care au același tată se numesc frați;
• lungimea unui lanț de la rădăcina arborelui la un nod x reprezintă nivelul sau adâncimea nodului x;
• lungimea maximă a unui lanț de la rădăcină la un nod al arborelui reprezintă înălțimea arborelui;
• un nod al arborelui împreună cu toți descendenții săi formează un subarbore;

Exemplu

Fie arborele următor:

• rădăcina arborelui este nodul 3;
• ascendenții nodului 4 sunt 5, 2 și 3. Ascendentul direct (tatăl) al nodului 4 este nodul 5;
• descendenții nodului 2 sunt 1 7 10 5 4 6. Descendenții direcți ai nodului 2 sunt 1 5;
• nodurile 1 și 5 sunt frați;
• nodurile 6 7 8 10 12 sunt frunze;
• descompunerea pe niveluri:
  • Nivelul 0 conține doar rădăcina: 3;
  • Nivelul 1 conține nodurile 2 9;
  • Nivelul 2 conține nodurile 1 5 8 11;
  • Nivelul 3 conține nodurile 7 10 4 12;
  • Nivelul 4 conține nodul 6;
• Înălțimea arborelui este 4;
• Nodurile 9 8 11 12 formează un subarbore;

Reprezentarea arborilor

Reprezentarea prin referințe descendente

Pentru fiecare nod al arborelui se memorează informații despre descendenții săi direcți. Este similară cu reprezentarea prin liste de adiacențe a grafurilor. Pentru arborele de mai sus avem:

• F[1]={7,10}
• F[2]={1,5}
• F[3]={2,9}
• F[4]={6}
• F[5]={4}
• F[6]={}
• F[7]={}
• F[8]={}
• F[9]={8,11}
• F[10]={}
• F[11]={12}
• F[12]={}

Reprezentarea prin referințe ascendente

Pentru fiecare nod se memorează informații despre ascendenții direcți. Vom obține un vector de tați, în care:

• t[r] = 0, unde r este rădăcina arborelui
• t[k] = tatăl nodului k

Pentru arborele de mai sus avem:

Observații

• În vectorul de tați există o singură valoare 0, corespunzătoare rădăcinii;
• Frunzele corespund valorilor care nu apar în vectorul de tați.
• Vectorul de tați ne permite să determinăm lanțuri în arbore, de la un nod oarecare spre rădăcină:
  • Pornim de la un nod dat x
  • Identificăm tatăl lui x, y = t[x];
  • Identificăm tatăl lui y, t[y]
  • ș.a.m.d.
  • Ajungem într-un nod z pentru care t[z]=0. acesta va fi rădăcina și ne oprim.

Exerciții și probleme

• exerciții
• probleme