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