A R B O R I
Arbore cu radacina = graf neorientat conex fara cicluri în care unul din noduri este desemnat ca radacina. Nodurile pot fi aşezate pe niveluri începand cu radacina care este plasata pe nivelul 1.
Radacina = Nod special care genereaza asezarea unui arbore pe niveluri. Aceasta operatie se efectueaza in functie de lungimea lanturilor prin care celelalte noduri sunt legate de radacina.
Descendent = intr-un arbore cu radacina nodul y este descendentul nodului x daca este situat pe un nivel mai mare decat nivelul lui x si exista un lant care le uneste si nu trece prin radacina.
Descendent fiu = intr-un arbore cu radacina nodul y este fiul nodului x daca este situat pe nivelul imediat urmator nivelului lui x si exista muchie intre x si y.
Ascendent = intr-un arbore cu radacina nodul x este ascendentul nodului y daca este situat pe un nivel mai mic decat nivelul lui y si exista un lant care le uneste si nu trece prin radacina.
Ascendent parinte = intr-un arbore cu radacina nodul x este parintele nodului y daca este situat pe nivelul imediat superior (cu numar de ordine mai mic) nivelului lui y si exista muchie între x si y.
Frati = intr-un arbore cu radacina nodul x este fratele nodului y daca au acelasi parinte.
Frunza = intr-un arbore cu radacina nodul x este frunza daca nu are nici un descendent direct
 Arbore cu radacina | - Nodul 1 este radacina. - Nodurile 5, 6, 7 sunt fii nodului 3. - Nodul 7 este parintele nodurilor 9 şi 10; - Nodul 9 este descendentul lui 3 - Nodul 3 este ascendentul lui 10 - Nodurile 8, 9 şi 10 sunt frunze - Nodurile 5, 6 şi 7 sunt frati. |
Grafurile, digrafurile si ca un caz particular al acestora - arborii - reprezinta structuri capabile sa surprinda complexitatea legaturilor dintre obiecte.
Cu ajutorul arborilor se pot descrie foarte fidel structurile de tip ierarhic (piramidal). Iata câteva exemple: structura de conducere a unei firme, organizarea administrativ teritoriala dintr-o tara, organizarea unei armate, structura unei carti, descrierea unui obiect ca o reuniune de obiecte componente care, la rândul lor, se descompun în obiecte s.a.m.d.
Definim recursiv un arbore ca un set finit de unul sau mai multe noduri, astfel încât sunt îndeplinite conditiile:
- exista un nod unic numit radacina arborelui;
- celelalte noduri sunt repartizate în k>0 seturi disjuncte, fiecare set fiind la rândul sau un arbore.
Grafic, putem reprezenta un arbore ca o multime de noduri sau vârfuri (fiecare obiect are asociat un nod) legate între ele prin arce care reflecta natura relatiei dintre obiecte.
Observatii:
In orice nod intra cel mult un arc;
In nodul radacina nu intra nici un arc;
Nodurile pot fi etichetate sau nu.
Remarci:
- nodul 1 este "radacina" si în acelasi timp "tata" pentru nodurile"fii" 2,5,6 care sunt între ele "frati";
- nodurile 9 si 10 sunt "descendenti" ai nodului "stramos" 5;
- nodurile fara nici un fiu se numesc noduri terminale sau "frunze" (exemple: 3,4,9,10,6).
Observatie:
Termenii tata, fiu, frate oglindesc relatii directe între noduri, iar termenii stramos, descendent - relatii indirecte.
Definim nivelul unui nod, recursiv, astfel:
- Nivelul nodului radacina este 1;
- Nivelul oricarui nod diferit de nodul radacina este nivelul tatalui sau +1.
Observatie. Nivelul unui nod este 1+numarul de arce care alcatuiesc un "drum" de la nodul "radacina" la el. Exemplu: nodurile 3,4,7 au nivelul 3, nodurile 9 si 10 au nivelul 5.
Un subarbore B pentru arborele A este orice arbore care îndeplineste conditiile:
1. nodurile lui B sunt si noduri în A;
2. arcele lui B sunt si arce în A;
3. orice frunza din A care poate fi atinsa din radacina arborelui B trebuie sa apartina multimii nodurilor lui B.
Un tip de arbore special, cu aplicatii interesante în tehnicile de programare este arborele binar.
Arborele binar este arborele în care un nod are cel mult doi fii. În aceasta situatie se poate vorbi (pentru un arbore nevid) de cei doi subarbori (stâng si drept) ai unui arbore.
Reprezentarea în memorie a arborilor poate fi statica sau dinamica. În cazul static arborii se pot simula cu ajutorul tablourilor.
Datorita dinamismului structurilor modelate printr-un arbore, varianta de implementare dinamica este preferabila variantei statice. In acest caz, daca arborele este binar, o celula va contine trei câmpuri: un câmp pentru memorarea informatiei specifice nodului (informatia utila) si doua câmpuri care contin adresa radacinii subarborelui stâng, respectiv drept.
Operatiile fundamentale asupra arborilor includ: parcurgerea arborelui, stergerea, cautarea sau adaugarea unui nod. Doua tipuri de parcurgere a unui arbore sunt folosite frecvent: parcurgerea în latime si parcurgerea în înaltime.
In cazul parcugerii în latime se viziteaza si prelucreaza nodurile în ordinea: radacina, nodurile de la stânga spre dreapta de pe primul nivel, de pe al doilea nivel etc. Astfel, rezultatul parcurgerii în latime a arborelui din prima figura: 1, 2, 5, 6, 3, 4, 7, 8, 9, 10.
In cazul parcurgerii în adâncime trecerea de la un nod x la fratele sau y din dreapta se face numai dupa ce s-au vizitat si prelucrat toate nodurile descendente din x. Rezultatul parcurgerii în adâncime a arborelui din prima figura este urmatoarea: 1, 2, 3, 4, 5, 7, 8, 9, 10, 6.
Pentru parcurgerea in latime sau adancime (inaltime) putem utiliza algoritmul folosit la grafuri:
//PARCURGEREA IN LATIME A GRAFURILOR NEORIENTATE
//BREADTH FIRST (BF)
#include "graf.cpp"
int a[50][50],vizitat[50],lista[50],n,j,k,p,x,y;
void PBF(int i)
{
int x=lista[i];
for (y=1;y<=n;y++)
if ((a[x][y]==1)&&(vizitat[y]==0))
{
k++;
lista[k]=y;
vizitat[y]=1;
}
if (i<n) PBF(i+1);
}
main()
{
citire_graf("graf.in",a,n);
afisare_graf(a,n);
cout<<"Nodul de plecare pentru BF: ";cin>>p;
lista[1]=p;
vizitat[p]=1;
k=1;
PBF(1);
cout<<"Lista nodurilor:"<<endl;
for (k=1;k<=n;k++) cout<<lista[k]<<" ";
}
//PARCURGEREA IN ADANCIME A GRAFURILOR NEORIENTATE
//DEPTH FIRST (DF)
#include "graf.cpp"
int a[50][50],vizitat[50],lista[50],n,x,k;
void PDF(int x)
{
int y;
lista[k++]=x; vizitat[x]=1;
for (y=1;y<=n;y++)
if(a[x][y]==1 && vizitat[y]==0) PDF(y);
}
int main()
{
citire_graf("graf.in",a,n);
afisare_graf(a,n);
cout<<"Nodul de plecare pentru DF: ";cin>>x;
k=1;
PDF(x);
cout<<"Lista nodurilor:"<<endl;
for (k=1;k<=n;k++)
cout<<lista[k]<<" ";
}
Un graf conex si fara cicluri, sau conex si m=n-1, sau fara cicluri si m=n-1 (m-muchii, n-noduri), sau fara cicluri maximal, sau conex minimal, sau orice pereche de noduri legata de un lant si numai unul - se numeste arbore.
Arbore partial de cost minim - APM
Suma costurilor muchiilor unui graf se numeste costul grafului (c).
Pentru un graf G, conex, cu functia de cost c, exista un graf partial H conex si de cost minim, care este A.P.M.
Algoritmul lui Kruskal de determinare a APM:
1. se initializeaza lista L(k)=k adica se presupune ca fiecare nod apartine unei componente conexe distincte (se elimina toate muchiile)
2. se ordoneaza crescator muchiile dupa costurii
3. se selecteaza o muchie [p,q]: daca numarul de muchii=n-1; STOP – s-a obtinut un APM, daca nu :
4. se verifica daca nodurille muchiei selectate apartin aceleasi componente conexe: L(p)=L(q), daca da (s-ar obtine un ciclu) se selecteaza urmatoarea muchie iar daca nu:
5. se va selecta muchia [p,q] ca o noua muchie a APM. Daca L(p)<L(q) atunci toate elementele din componenta conexa q trec in p (sau invers).
Se merge la pasul 3.
In final toate nodurile apartin componentei conexe 1.
Arbori binari
Definitie: Numim arbore binar un arbore in care fiecare nod are zero, unul sau cel mult doi fii (descendenti).
Definitie: Un arbore binar cu proprietatea ca fiecare nod cu exceptia frunzelor (nodurilor terminale) are exact doi descendenti se numeste arbore binar complet.
Reprezentarea arborilor binari:
1. Metoda standard: Se specifică rădăcina RAD iar pentru fiecare nod se precizează desc. Stang S[i], descendentul drept D[i] (in caz ca exista) si informatia din nod (nr. Nodului). Lipsa unui descendent se simbolizeaza cu 0.Exemplu: Pentru arborele binar urmator:
RAD = 1
ST = { 2, 0, 5, 0, 6, 0, 0 }
DR = { 3, 0, 4, 0, 7, 0, 0 }.
2. Se folosesc vectorii TATA care precizeaza pentru fiecare nod i, nodul parinelui sau TATA[i] si DESC, vector care retine valorile –1 sau 1 In functie de nodul i care este fie descendent stâng, fie descendent drept.
TATA = { 0, 1, 1, 3, 3, 5, 5 }
DESC = { 0, -1, 1, 1, -1, -1, 1 }.
3. Reprezentarea cu paranteze:
- se scrie nodul radacina;
- ficare nod va fi urmat de: paranteza rotunda, descendent stang, virgula, descendent drept si paranteza rotunda inchisa
1 ( 2 , 3 ( 5 ( 6 , 7 ) , 4 ) ) sau
1 ( 2(0,0) , 3 ( 5 ( 6(0,0) , 7(0,0))) , 4(0,0)))
Pentru arborii binari, trei tipuri de parcurgere în adâncime sunt uzuale: parcurgerea în preordine (RSD), în inordine (SRD) si în postordine (SDR).
Prescurtarile au urmatoarea semnificatie:
RSD - Radacina, Stânga, Dreapta - se prelucreaza radacina, subarborele stâng, subarborele drept;
SRD - Stânga, Radacina, Dreapta - se prelucreaza subarborele stâng, radacina, subarborele drept;
SDR - Stânga, Dreapta, Radacina - se prelucreaza subarborele stâng, subarborele drept, radacina.
Niciun comentariu:
Trimiteți un comentariu