h2. Aplicatii

Algoritmul de parcurgere in latime (Breadth First Search) poate fi adaptat intr-o multime de probleme. De exemplu, la problema "Muzeu":/problema/muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema "CrazySwitches":http://www.topcoder.com/stat?c=problem_statement&pm=6071&rd=9812 de pe topcoder, graful este reprezentat de stari binare, iar muchiile de posibilitatea de a ne deplasa dintr-o stare in alta. Un tip mai aparte de BFS, prezent si in problema anterioara, este acela cand costurile de pe muchii sunt mici si pentru a rezolva problema folosim mai multe cozi (complexitatea fiind mai mica decat daca am folosi algoritmul "Dijkstra":/problema/dijkstra). Mai multe explicatii asupra acestui procedeu gasiti in acest "articol":/preoni-2005/runda-2/solutii, la problema "Car":/problema/car. Alte probleme ce folosesc acest algoritm in rezolvare sunt:

Algoritmul de parcurgere in latime (Breadth First Search) poate fi adaptat intr-o multime de probleme. De exemplu, la problema "Muzeu":/problema/muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema "CrazySwitches":http://www.topcoder.com/stat?c=problem_statement&pm=6071&rd=9812 de pe topcoder, graful este reprezentat de stari binare, iar muchiile de posibilitatea de a ne deplasa dintr-o stare in alta. Un tip mai aparte de BFS, prezent si in problema anterioara, este acela cand costurile de pe muchii sunt mici si pentru a rezolva problema folosim mai multe cozi (complexitatea fiind mai mica decat daca am folosi algoritmul "Dijkstra":/problema/dijkstra). Mai multe explicatii asupra acestui procedeu gasiti in acest "articol":/preoni-2005/runda-2/solutii, la problema "car":/problema/car. Alte probleme ce folosesc acest algoritm in rezolvare sunt:

* "Graf":/problema/graf (infoarena)
* "Sate":/problema/sate (infoarena)