Date post: | 27-Jun-2015 |
Category: |
Documents |
Upload: | martinas-maria |
View: | 90 times |
Download: | 0 times |
Structuri arborescente
(grafuri de tip arbore)
Structuri arborescente
• 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
Structuri arborescente
• 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
Structuri arborescente
• 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.
Structuri arborescente
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
Structuri arborescente
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
Algoritmul lui Kruskal
• 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;
}
Algoritmul lui Kruskal
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;}