05 - Grafuri
17
Grafuri
-
Upload
mihaescu-florin -
Category
Documents
-
view
137 -
download
9
Transcript of 05 - Grafuri
Grafuri
Grafuri
• Definiţii• Reprezentări• Parcurgere în lăţime• Parcurgere în adîncime• Drumuri în grafuri. Conexitate
– Matricea existenţei drumurilor. Algoritmul Roy-Warshall
– Componente conexe– Drumuri de cost minim. Algoritmul Dijkstra. Algoritmul
Roy-Floyd
• Circuite şi cicluri– Algoritmul Marimont
Definiţii
• Se numeşte graf sau graf neorientat o structură
G=(V,E), unde V este o mulţime nevidă iar E este o
submulţime posibil vidă a mulţimii perechilor
neordonate cu componente distincte din V.
• Vîrfurile u, v sînt adiacente în G dacă uv E.
• Graful G=(V,E) este graf finit, dacă V este o mulţime
finită.
• Fie Gi =(V i,Ei), i=1,2 grafuri. G2 este un subgraf al
grafului G1 dacă V2 e inclus în V1 şi E2 e inclus în E1. G2
este este un graf parţial al lui G1 dacă V2=V1 şi G2 este
subgraf al lui G1.
Definiţii
• Un digraf este o structură D=(V,E), unde V este o mulţime nevidă de
vîrfuri, iar E este o mulţime posibil vidă de perechi ordonate cu
componente elemente distincte din V. Elementele mulţimii E sînt
numite arce sau muchii ordonate. Un graf direcţionat este o
structură D=(V,E), unde V este o mulţime nevidă de vîrfuri, iar E este
o mulţime posibil vidă de perechi ordonate cu componente
elemente din V, nu neapărat distincte. Evident, orice digraf este un
graf direcţionat.
• Se numeşte graf ponderat o structură (V,E,W), unde G=(V,E) este
graf şi W este o funcţie numită pondere care asociază fiecărei
muchii a grafului un cost/cîştig al parcurgerii ei.
• Fie G=(V,E) un graf, u,vV. Secvenţa de vîrfuri u0, u1, .., un este un u-
v drum dacă u0=u, un=v, uiui+1E pentru toţi i.
• Fie G=(V,E) un graf. Elementul vV se numeşte vîrf izolat dacă,
pentru orice e E, v nu este incident cu e.
Reprezentări• Intuitivă, grafică
– G=(V,E) graf cu V={1,2,3,4,5,6}, E={(1,2),(1,3),(2,5),(3,5),(5,6)}.
– D=(V,E) digraf, V={1,…,5}, E={(1,2), (1,3), (1,5), (2,5), (3,5), (4,1), (5,4)}.
1
2
3
4
5
6
1
2
3
5
4
Reprezentare
• D=(V,E) graf direcţionat, V={1,2,3,4,5}, E={(1,2), (1,3), (1,5) (2,5), (3,5), (4,4)}.
• G=(V,E,W) graf ponderat, V={1,2,3,4}, E={(1,2), (1,3), (1,4), (2,3), (2,4)}, W((1,2))=5, W((1,3))=1, W((1,4))=7, W((2,3))=4, W((2,4))=2.
1
3 2
4
5 1
2 7
4
1
2
3
4
5
Reprezentări
• Matricea de adiacenţă
altfel,0
Ev,vdacă,1a ji
ij
altfel
Evvdacăa
ji
ij,0
,,1
1
2
3
4
5
6
010000
100110
000000
010001
010001
000110
A
11000
00001
10000
10000
10110
A
1
2
3
5
4
1
2
3
4
5
00000
01000
10000
10000
10110
A
Reprezentare
altfel,
Ev,vdacă,)v,v(Ww jiji
j,i
27
41
245
715
W
1
3 2
4
5 1
2 7
4
• Matricea de adiacenţă pentru graf ponderat
Rprezentare
• Tabelară
65
53
52
31
21
A
45
14
53
52
51
31
21
A
44
53
52
51
31
21
A
242
741
432
131
521
A
Reprezentare
• Liste dinamice
Parcurgere (traversare)
• În lăţime• Fie G=(V,E) un graf.
– A - matricea de adiacenţă a grafului;– C - o structură de tip coadă, în care sînt introduse vîrfurile
ce urmează a fi vizitate şi procesate – V - un vector cu n componente (iniţializate cu 0), unde
• Algoritm– coada C este iniţializată cu vîrful v0; – cît timp C ≠ Ø,
• Se extrage şi vizitează un vîrf i din coadă,• Se introduc în coadă vecinii lui i care nu au fost deja
introduşi (acele vîrfuri k cu proprietatea că c[k]=0 şi a[i][k]=1). Vîrfurile i ce au fost introduse în coadă sînt marcate prin v[i]=1.
,0
,1ic
Parcurgere (traversare) în lăţime
• Fie graful:
• Rezultatul parcurgerii, pornind de la 1, este:– 1, 2, 3, 4, 6, 5, 7
1
2 3
4
5 7
6
8
9 10
11
Parcurgere (traversare) în lăţime
void BF(int vi,int a[10][10],int n,int rez[10],int* nr){ TNOD* cap=NULL; int v[10], i, r, k; for(i=0; i<n; v[i++]=0); push(&cap,vi); v[vi]=1; *nr=0; while(cap) { r=pop(&cap, &i); rez[(*nr)++]=i+1; for(k=0; k<n; k++) if((a[i][k]==1)&&(v[k]==0)) { push(&cap,k); v[k]=1; } }}
Parcurgere (traversare)
• În adîncime• Fie G=(V,E) un graf.
– A - matricea de adiacenţă a grafului;– S - o structură de tip stivă, în care sînt introduse vîrfurile
ce urmează a fi vizitate şi procesate – V - un vector cu n componente (iniţializate cu 0), unde
• Algoritm– stiva S este iniţializată cu vîrful v0; – cît timp S ≠ Ø,
• Se extrage şi vizitează un vîrf i din stivă,• Se introduc în stivă vecinii lui i care nu au fost deja
introduşi (acele vîrfuri k cu proprietatea că c[k]=0 şi a[i][k]=1). Vîrfurile i ce au fost introduse în stivă sînt marcate prin v[i]=1.
,0
,1ic
Parcurgere (traversare) în adîncime
• Fie graful:
• Rezultatul parcurgerii, pornind de la 1, este:– 1, 3, 6, 7, 4, 5, 2
1
2 3
4
5 7
6
8
9 10
11
Parcurgere (traversare) în lăţime
void DF(int vi,int a[10][10],int n,int rez[10],int* nr){ TNOD* cap=NULL; int v[10], i, r, k; for(i=0; i<n; v[i++]=0); push(&cap,vi); v[vi]=1; *nr=0; while(cap) { r=pop(&cap, &i); rez[(*nr)++]=i+1; for(k=0; k<n; k++) if((a[i][k]==1)&&(v[k]==0)) { push(&cap,k); v[k]=1; } }}
Parcurgerea DF generalizată
