infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Rus Cristian din Martie 21, 2006, 20:07:22

Titlul: BF
Scris de: Rus Cristian din Martie 21, 2006, 20:07:22

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

Titlul: BF
Scris de: u-92 din Martie 21, 2006, 20:36:32

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

Titlul: BF
Scris de: Filip Cristian Buruiana din Martie 21, 2006, 21:53:06

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 ).

Titlul: BF
Scris de: Bogdan-Cristian Tataroiu din Martie 21, 2006, 22:04:47

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

Titlul: BF
Scris de: Filip Cristian Buruiana din Martie 22, 2006, 15:01:42

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

Titlul: BF
Scris de: Mircea Pasoi din Martie 22, 2006, 16:45:38

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