BF

[•cristy]

spuneti-mi va rog cum se face bf in 0(N)?...care e ideea?

[u-92]

tii liste cu vecinii fiecarui varf (alocate dinamic) si complexitatea o sa fie O(N+M) (mai multe detalii sunt in cormen)

[•filipb]

Iterativ e cam asa:

Cod:

q[1] = sursa; 
uz[sursa] = 1;
crt = fin = 1;
while (crt <= fin)
{
       for (f = G[q[crt]]; f; f = f->next)
            if (!uz[f->id])
            { q[++fin] = f->id; uz[f->id] = 1; }
       crt++;
}

Ai un nod x si bagi intr-o stiva toti vecinii sai si dupa aia avansezi o pozitie in stiva si repeti procedeul. Algoritmul iti garanteaza ca nodurile apar in stiva crescator in functie de distanta pana la sursa ( nu e grea demonstratia, e oarecum si intuitiva ).

[•bogdan2412]

Se poate face BFS si recursiv?   Si apropo e o coada.. nu stiva

[•filipb]

Da, e o coada
Recursiv banuiesc ca nu...

[•domino]

Se poate face BF si recursiv, aproape orice se poate face si recursiv.