structuri arborescente

Structuri arborescente

(grafuri de tip arbore)


• Definiţie. Graful este arbore dacă este aciclic şi conex.

1

2 3 4

5 6

7

1

2

3

4

5

7

7

1

2

3

4

5

6

7

8

9


• Definiţie. Fie graf arbore. Subgraful al lui este subarbore al lui dacă este graf arbore.

12

34

56 7

8

9

12

34

56

9

12

34

56 7

8

9

12

34

𝑮 𝑯𝟏

𝑯𝟐 𝑯𝟑


• Fie un graf. Următoarele afirmaţii sînt echivalente:– este graf arbore (aciclic şi conex);– este graf conex minimal: prin eliminarea oricărei muchii,

graful rezultat nu este conex;– este graf aciclic maximal: prin adăugarea unei noi muchii

în graf rezultă cel puţin un ciclu.

• Cum verificăm dacă un graf este arbore?– Verificare conexitate + verificare aciclicitate (alg. Marimont)– Verificare aciclicitate şi 1 (n – nr. vîrfuri, m – nr. muchii)– Verificare conexitate şi 1

12

34

56 7

8

9


• Definiţie. Se numeşte graf asimetric un digraf cu proprietatea că pentru orice , .

• Digraful D este simetric dacă pentru orice şi .

1

2

3

4

5 6

7

Graf asimetric

1

2

3

4

5 6

7

Graf simetric


• Definiţie. Fie digraf netrivial. Graful , unde se numeşte graf suport al digrafului D.

1

2

3

4

5 6

7

1

2

3

4

5 6

7

Graf suport


• Definiţie. Un arbore direcţionat este un graf orientat asimetric pentru care graful suport corespunzător este graf arbore.

• Definiţie. Arborele direcţionat este arbore cu rădăcină dacă există astfel încît, pentru orice , , există r-u drum în . Vîrful r se numeşte rădăcina arborelui direcţionat (drumurile sînt unice, rădăcina este unică; lungimea unui drum este egală cu numărul de arce).

• Definiţie. Fie arbore direcţionat. Arborele este subarbore al lui T dacă , şi T1 este arbore direcţionat. Graf orientat asimetric

1

2

3

4

5

6

7

8

9

10

G1 1

2

3

4

5

6

7

8

9

10

Graf suport

GS

Arbore direcţionat

1

2

3

4

5

6

7

8

9

10

G2

Graf orientat asimetricArbore direcţionat cu rădăcină

1

2

3

4

5

6

7

8

9

10

Subarbori (G1, G1/G2)

Pentru un arbore cu rădăcină, orice nod este rădăcina unui subarbore.

Reprezentări şi parcurgeri (arbori orientaţi)

• Definiţie. Un arbore orientat este un arbore direcţionat cu rădăcină.

• Definiţie. Fie un arbore orientat cu rădăcină r. Un vîrf v este situat pe nivelul i al arborelui T, dacă distanţa de la vîrf la rădăcină este egală cu i. Rădăcina arborelui este considerată pe nivelul 0.

• Se pot folosi toate tipurile de reprezentare a grafurilor, plus metode specifice arborilor.

“…lungimea unui drum este egală cu numărul de arce.”

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

Reprezentarea Fiu-Frate

• N: numărul de noduri

• R: eticheta nodul rădăcină

• FIU(i): eticheta primului descendent al vîrfului i

• FRATE(i): eticheta vîrfului descendent al tatălui vîrfului i şi

care urmează imediat lui i

• INF(i): informaţia ataşată vîrfului i

• adesea informaţia e chiar valoarea i, caz în care

vectorul INF nu mai e necesar

• Valoare lipsă (fiu, frate): se foloseşte o valoare

convenţională (0, -1…)

din partea stîngă, conform reprezentării grafice

spre dreapta, conform reprezentării grafice

Atenție la translația etichetă indice vector

Reprezentarea Fiu-Frate

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

FIU =(2,5,0,8,0,9,0,14, 0, 0, 0, 0, 0, 0, 0, 0)

FRATE =(0,3,4,0,6,7,0, 0,10,11,12,13, 0,15,16, 0)

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

N = 16,

R = 1

Putem afla tatăl unui nod?

Putem afla descendenţii unui nod?

Reprezentare folosind structuri dinamice

• Presupunînd că fiecare vîrf al arborelui are cel mult n descendenţi, fiecărui vîrf îi este asociată structura

,

identificator vîrf

vector de legături către descendenţii vîrfului

adresă fiu 1 … adresă fiu n

1 Adr.fiu 1

Adr.fiu 2

Adr.fiu 3

Null Null

2 Adr.fiu 1

Adr.fiu 2

Adr.fiu 3

Null Null 3 Null Null Null Null Null 4 Adr.fiu 1

Null Null Null Null

5 Null Null Null Null Null

6 Adr.fiu 1

Adr.fiu 2

Adr.fiu 3

Adr.fiu 4

Adr.fiu 5







8 Adr.fiu 1

Adr.fiu 2

Adr.fiu 3

Null Null




Parcurgeri

• Aplicarea sistematică a unei reguli de vizitare a

vîrfurilor arborelui.

• Cele mai utilizate reguli de parcurgere a arborilor

orientaţi sînt

– A-preordine (variantă DF)

– A-postordine (variantă DF)

– parcurgerea pe niveluri (BF)

Parcurgerea în A-preordine (Fiu-Frate)

• Se vizitează vîrful curent şi se identifică descendenţii lui. Se aplică aceeaşi regulă de vizitare pentru fiecare dintre arborii avînd ca rădăcini descendenţii vîrfului curent.

void A_preordine (nod R){ if (R) { vizit (R); A_preordine(FIU[R]); A_preordine(FRATE[R]); }

} 1, 2, 5, 6, 9, 10, 11, 12, 13, 7, 3, 4, 8, 14, 15, 16

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

Parcurgerea în A-postordine (Fiu-Frate)

• Se identifică şi se vizitează descendenţii vîrfului curent, apoi se vizitează vîrful curent. Se aplică aceeaşi regulă de vizitare pentru arborii avînd ca rădăcini descendenţii vîrfului curent.

void A_postordine (nod R){ if (R) { A_postordine(FIU[R]); vizit (R); A_postordine(FRATE[R]); }

} 5, 9, 10, 11, 12, 13, 6, 7, 2, 3, 14, 15, 16, 8, 4, 1

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

Parcurgeri în adîncime (str. dinamice)

void A_preordine (nod R){ if (R) { vizit (R); for(i=0;i<n;i++) A_preordine(R->leg[i]); }}

void A_postordine (nod R){ if (R) { for(i=0;i<n;i++) A_postordine(R->leg[i]); vizit (R); }}

Parcurgerea pe niveluri (Fiu-Frate)

void parcurgere_pe_niveluri(nod R, int FIU[], int FRATE[], int n){ TNOD* C = NULL; push(C,R); while (C) { pop(C,v); VIZIT(v); v=FIU[v]; while(v) { push(C,v); v=FRATE[v]; } }}1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

Parcurgerea pe niveluri (str. dinamice)

void parcurgere_pe_niveluri(nod *R){ TNOD* C = NULL; push(C,R); while (C) { pop(C,v); VIZIT(v); for(i=0;i<n;i++) if(R->leg[i])

push(C,R->leg[i]); }

}

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

1

32 4

5 6 7 8

9 10 11 12 13 14 15 16

Arbori parţiali

• Definiţie. Fie un graf. Subgraful parţial este un arbore parţial al lui dacă este graf arbore.

• Definiţie. Fie un graf ponderat conex. Dacă este un arbore parţial al grafului , ponderea arborelui , notată , este definită prin

• Definiţie. Arborele parţial este arbore parţial minim pentru dacă , unde este mulţimea arborilor parţiali ai grafului .

Arbori parţiali1

3

2

4

5

6

3

1

278

4

7

24

3

3

3 3

1

3

2

4

5

6

1

27

4

7

3

3

1

3

2

4

5

6

1

2

7

24

33

1

3

2

4

5

6

1

8

4

7

24

3

P = 22

P = 20 P = 15

Algoritmul lui Kruskal

Problemă: determinarea arborelui parţial de cost minim al

grafului .Algoritm:

• se iniţializează iar .

• dintre arcele disponibile (neselectate anterior) se alege

arcul cu ponderea cea mai mică şi care nu formează un

ciclu prin adăugare la arbore

• repetă pasul anterior de ori

Algoritmul lui Kruskal2 3 11 6 22 4 21 5 33 4 41 2 4 4 6 85 6 83 6 93 5 12

i j arc 1 2 3 4 5 6 cost total (-1, -1, -1, -1, -1, -1) 0

1

2

34

56

1

2

34

56

42

2

8129

8

3

1

4

0 0 (2,3) (-1, -2, 2, -1, -1, -1) 1 1

1

Nr. arc curent

Nr. arce selectate

Arc curent

Vectorul Tata

v

1 1 (1,6) (-2, -2, 2, -1, -1, 1) 2 3

2

v

2

2 2 (2,4) (-2, -3, 2, 2, -1, 1) 2 5

v 3

3 3 (1,5) (-3, -3, 2, 2, 1, 1) 3 8

v4

5 4 (1,2) (-6, 1, 2, 2, 1, 1) 4 12

v

4 4 (3,4) 8

x

• Funcţie pentru determinarea rădăcinii

int radacina(int v,int tata[]){ int u = v; while(tata[u] >= 0)

u = tata[u]; return u; }Ex.: v = 4u = 4 tata[4]=2u = 2 tata[2]=1u = 1 tata[1]=-6 < 0

Algoritmul lui Kruskal

1 2 3 4 5 6

(-6, 1, 2, 2, 1, 1)

Algoritmul lui Kruskalint kruskal(int a[][3],int nm, int nv, int b[][3]){ int tata[50],i,j, v1, v2, r1, r2; int c=0; for(i=0; i<nv; i++) tata[i]=-1; for(i=j=0; j<nv-1; i++) { v1=a[i][0]; v2=a[i][1]; r1=radacina(v1,tata); r2=radacina(v2,tata); if( r1 != r2 ) { if( tata[r1] < tata[r2] ) { tata[r1]+=tata[r2]; tata[r2]=r1; } else { tata[r2]+=tata[r1]; tata[r1]=r2; } b[j][0]=a[i][0]; b[j][1]=a[i][1]; b[j][2]=a[i]

[2]; c+=a[i][2]; j++; } } return c;}

Spor la învăţat!

structuri arborescente

Documents