Post on 24-Nov-2015
description
verman@fmi.unibuc.ro
Dat un graf G i un vrf s, care sunt toate
vrfurile accesibile din s?
Un vrf v este accesibil din s dac exist
un drum/lan de la s la v n G.
Idee: Dac
u este accesibil din s
uvE(G)
atunci v este accesibil din s.
Parcurgere = o modalitate prin care, plecnd
de la un vrf de start i mergnd pe
arce/muchii s ajungem la toate vrfurile
accesibile din s
Parcurgerea n lime (BF = breadth first)
Parcurgerea n adncime (DF = depth first)
Parcurgerea n lime: se viziteaz
- vrful de start s
- vecinii acestuia
- vecinii nevizitai ai acestora
etc
1
2
9
3
4
8
7
5
6
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
9 3 5
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
9 3 5
1 3 5 9 6 42 7 8
1
2
9
3
4
8
7
5
6
1
9 3 5
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3 5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3 5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3 5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3 5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3 5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
1 3 5 9 2 6 4 7 8
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
Vrfurile vizitate trebuie marcate:
viz[i]
Arcele/muchiile folosite pentru a descoperi
vrfuri noi accesibile din s formeaz un arbore:
tata[j] = acel vrf i din care este descoperit
(vizitat) j
1, dac i a fost vizitat=
0, altfel
Vrfurile vizitate trebuie marcate:
viz[i]
Muchiile folosite pentru a descoperi vrfuri noi
formeaz un arbore:
tata[j] = acel vrf i din care este descoperit
(vizitat) j
1, dac i a fost vizitat=
0, altfel
1
2
9
3
4
8
7
5
6
1
6
9 3
4 8 7
5
2
Vrfurile sunt vizitate n ordinea distanei fa
de vrful de start s:
d[i] = lungimea drumului determinat de
algoritm de la s la i
Propoziie
d[i] este chiar distana de la s la i
Iniializri
pentru i=1,n executa
viz[i]0
tata[i]0
d[i]
for(i=1;i
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1;
while(p
Iniializri
pentru i=1,n executa
viz[i]0
tata[i]0
d[i]
int n;
int a[20][20];
int viz[20],tata[20],d[20];
int p,u,c[20];
for(i=1;i
Iniializri
pentru i=1,n executa
viz[i]0
tata[i]0
d[i]
int n;
int a[20][20];
int viz[20],tata[20],d[20];
int p,u,c[20];
for(i=1;i
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
procedure BF(s) coada C ;
adauga(s, C)
viz[s] 1; d[s] 0
cat timp C executa
i extrage(C);
afiseaza(i);
pentru j vecin al lui i
daca viz[j]=0 atunci
adauga(j, C)
viz[j] 1
tata[j] i
d[j] d[i]+1
void bf(int s){
int p,u,i,j;
p = u = 1; c[1]=s;
viz[s]=1; d[s]=0;
while(p
Matrice de adiacen O(|V|2)
Liste de adiacen O(|V|+|E|)
Matrice de adiacen O(|V|2)
Liste de adiacen O(|V|+|E|)
Matrice de adiacen O(|V|2)
Liste de adiacen O(|V|+|E|)
Test graf conex
Determinarea numrului de componente
conexe
nrcomp=0;
for(i=1;i
Test graf conex
Determinarea numrului de componente
conexe
nrcomp=0;
for(i=1;i
Determinarea unui arbore parial al unui graf
conex
Determinarea unui arbore parial al unui graf
conex
(tata[x], x), x s
Determinarea unui drum minim de la vrful de
start s la un vrf dat x
void lant(int x){
while(x!=0){
cout
Determinarea unui drum minim de la vrful de
start s la un vrf dat x
void lant(int x){
while(x!=0){
cout
Determinarea unui drum minim de la vrful de
start s la un vrf dat x
void lant(int x){
while(x!=0){
cout
Lema 1. Dac n coada C avem: v1, v2,, vr,
atunci
d[v1] d[v2] d[vr] d[v1] +1
Lema 1. Dac n coada C avem: v1, v2,, vr,
atunci
d[v1] d[v2] d[vr] d[v1] +1
Lema 2. Dac d[v] = k, atunci exist n G un
drum de la s la v de lungime k
Lema 1. Dac n coada C avem: v1, v2,, vr,
atunci
d[v1] d[v2] d[vr] d[v1] +1
Lema 2. Dac d[v] = k, atunci exist n G un
drum de la s la v de lungime k
Consecin. d[v] d(s,v)
Propoziie. Pentru orice vrf v avem
d[v] = d(s, v) = distana de la s la v
Parcurgerea n adncimeLa un pas:
se trece la primul vecin nevizitat al vrfului
curent, dac exist
altfel
se merge napoi pe drumul de la s la vrful
curent, pn se ajunge la un vrf cu vecini
nevizitai
se trece la primul dintre acetia i se reia procesul
Se viziteaz
- Iniial: vrful de start s - devine vrf curent
La un pas:
se trece la primul vecin nevizitat al vrfului
curent, dac exist
altfel
se merge napoi pe drumul de la s la vrful
curent, pn se ajunge la un vrf cu vecini
nevizitai
se trece la primul dintre acetia i se reia
procesul
Se viziteaz
- Iniial: vrful de start s - devine vrf curent
- La un pas:
se trece la primul vecin nevizitat al vrfului
curent, dac exist
altfel
se merge napoi pe drumul de la s la vrful
curent, pn se ajunge la un vrf cu vecini
nevizitai
se trece la primul dintre acetia i se reia
procesul
Se viziteaz
- Iniial: vrful de start s - devine vrf curent
- La un pas:
se trece la primul vecin nevizitat al vrfului
curent, dac exist
altfel
se merge napoi pe drumul de la s la vrful
curent, pn se ajunge la un vrf cu vecini
nevizitai
se trece la primul dintre acetia i se reia
procesul
Se viziteaz
- Iniial: vrful de start s - devine vrf curent
- La un pas:
se trece la primul vecin nevizitat al vrfului
curent, dac exist
altfel
se merge napoi pe drumul de la s la vrful
curent, pn se ajunge la un vrf cu vecini
nevizitai
se trece la primul dintre acetia i se reia
procesul
1
2
9
3
4
8
7
5
6
1
2
9
3
4
8
7
5
6
1
1
2
9
3
4
8
7
5
6
1
3
1
2
9
3
4
8
7
5
6
1
3
2
1
2
9
3
4
8
7
5
6
1
9
3
2
1
2
9
3
4
8
7
5
6
1
9
3
4
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
5
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
5
2
1
2
9
3
4
8
7
5
6
1
6
9
3
4
8
7
5
2
void df(int i){ viz[i]=1;
cout
void df(int i){ viz[i]=1;
cout
void df(int i){ viz[i]=1;
cout
void df(int i){ viz[i]=1;
cout
void df(int i){ viz[i]=1;
cout