08 - Structuri arborescente

Structuri arborescente

(grafuri de tip arbore)


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

• Definiţie. Fie G=(V,E) graf arbore. Subgraful H=(V1,E1) al lui G este subarbore al lui G dacă H este graf arbore.

1

2 3 4

5 6

7

1

2

3

4

5

7

7

1

2

3

4

5

6

7

8

9


• Fie G=(V,E) un graf. Următoarele afirmaţii sînt echivalente:– G este graf arbore (aciclic şi conex);– G este graf conex minimal: oricare ar fi eE, prin

eliminarea muchiei e din E, graful rezultat nu este conex;

– G 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 n = m + 1– Verificare conexitate şi n = m + 1


• Definiţie. Se numeşte graf asimetric un digraf D=(V,E) cu proprietatea că pentru orice uvE, vu nu apartine E. Digraful D este simetric dacă pentru orice uvE şi vuE.

• Definiţie. Fie D=(V,E) digraf netrivial. Graful G=(V,E’), unde E’={uv / uvE sau vuE} se numeşte graf suport al digrafului D.

• 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 T=(V,E) este arbore cu rădăcină dacă există rV astfel încît, pentru orice uV, u ≠ r, există r-u drum în T. Vîrful r se numeşte rădăcina arborelui direcţionat T. (drumurile sînt unice, rădăcina este unică).

• Definiţie. Fie T=(V,E) arbore direcţionat. Arborele T1=(V1,E1) este subarbore al lui T dacă V1V, E1E şi T1 este arbore direcţionat.


1

2

3

4

5 6

7

Graf Graf asimetricasimetric

1

2

3

4

5 6

7

Graf Graf simetricsimetric1

2

3

4

5 6

7

Graf Graf suportsuport

1

2

4

5 6

8 10


1

2

3 4

5 6

7 8 9 10

1 2

3

4

5 6

7

3 4

5 6

7 8 9 10

Reprezentări şi parcurgeri

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

• Definiţie. Fie T=(V,E), 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ă de nivel 0.

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

Reprezentarea Fiu-Frate

• N, R• FIU(i): numărul ataşat primului descendent al vîrfului i; • FRATE(i): numărul ataşat vîrfului descendent al tatălui

vîrfului i şi care urmează imediat lui i;• INF(i): informaţia ataşată vîrfului i (de obicei valoarea i).

1

2 3 4

5 6 7 8

9 10 11 12 13 14 15 16

N=16, R=1 (rădăcina)

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)

Reprezentare folosind structuri dinamice

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

,

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

adresă fiu 1 … adresă fiu n

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)

• Este vizitat vîrful curent şi sînt identificaţi descendenţii lui. Se aplică aceeaşi regulă de vizitare pentru 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

2 3 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]); A_postordine(FRATE[R]); vizit (R); }

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

1

2 3 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]; } }}

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++)

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

}

}

Arbori parţiali

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

• Definiţie. Fie G=(V,E,w) un graf ponderat conex. Dacă T=(V,E0) este un arbore parţial al grafului G’=(V,E), ponderea arborelui T, notată W(T), este definită prin

W(T)=

• Definiţie. Arborele parţial T0T(G) este arbore parţial minim pentru G dacă W(T0)=min{W(T); TT(G)}, unde T(G) este mulţimea arborilor parţiali corespunzători grafului G.

0Ee

)e(w

Arbori parţiali

1

2 3 4

5 6 2

2

4 3

1 9

12

8

1

2

2 3 4

6 5

8 9

4 3

Algoritmul lui Kruskal

Problemă: determinarea arborelui parţial de cost

minim

Algoritm:

• E se iniţializează arborele ca mulţime vidă

• Selectează arcul cu ponderea cea mai mică şi

care nu formează un ciclu dacă e adăugat la

arbore

• Repetă pasul anterior de n – 1 ori

Algoritmul lui Kruskal2 3 1

1 6 2

2 4 2

1 5 3

3 4 4

1 2 4

4 6 8

5 6 8

3 6 9

3 5 12

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

11

22

3344

5566

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

22

22

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

33

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

11

22

3344

5566

4422

22

88121299

88

33

11

44

44

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

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

11


• 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;

}


int 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;}

08 - Structuri arborescente

Documents

Transcript of 08 - Structuri arborescente