| Fişierul intrare/ieşire: | bfs.in, bfs.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Florian Marcu •Florian |
| Timp execuţie pe test | 0.525 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
BFS - Parcurgere in latime
Se considera un graf orientat cu N varfuri si M arce.
Cerinta
Fiind dat un nod S, sa se determine, pentru fiecare nod X, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X.
Date de intrare
Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S, cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y, cu semnificatia ca exista arc orientat de la x la y.
Date de iesire
In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul S la nodul i.
Restrictii
- 2 ≤ N ≤ 100 000
- 1 ≤ M ≤ 1 000 000
- Daca nu se poate ajunge din nodul S la nodul i, atunci numarul corespunzator numarului i va fi -1.
Exemplu
| bfs.in | bfs.out |
|---|---|
| 5 7 2 1 2 2 1 2 2 3 2 2 5 5 3 4 5 | 1 0 2 -1 1 |
Indicatii de rezolvare
Initial, se insereaza nodul S intr-o coada vida, cu costul 0. La fiecare pas, se ia nodul din inceputul cozii, se elimina si apoi se adauga vecinii nevizitati la finalul cozii. Costul unui nod nou adaugat va fi costul nodului care l-a adaugat + 1. Mai multe amanunte asupra algoritmului de parcurgere in latime (Breadth First Search) puteti gasi aici si aici.
O rezolvare ce foloseste o matrice de adiacenta pentru a retine graful obtine 50 de puncte. O solutie optima ca timp si memorie - O(N+M), implementata cu ajutorul listelor de adiacenta, se gaseste aici.
Un alt algoritm pentru parcurgerea unui graf este prezentat aici.
Aplicatii
Algoritmul de parcurgere in latime (Breadth First Search) poate fi adaptat in multe probleme. De exemplu, la problema Muzeu putem consideram matricea data un graf in care celulele sunt noduri, iar laturile comune dintre celule sunt muchii. La problema CrazySwitches, 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). Mai multe explicatii asupra acestui procedeu gasiti in acest articol, la problema Car. Alte probleme ce folosesc algoritmul de parcurgere in latime in rezolvare sunt:
