BFS cu coada.pop() în loc de popleft(): distanțele ies prea mari
pop() scoate ultimul element, deci coada ta funcționează ca o stivă și parcurgerea devine DFS. Nodurile sunt descoperite pe drumuri lungi și primesc distanțe prea mari. La BFS folosește deque și scoate cu popleft() (cel mai vechi element).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
BFS găsește cele mai scurte drumuri într-un graf fără costuri pentru că procesează nodurile în ordinea descoperirii: întâi toate nodurile la distanța 1, apoi la distanța 2 și așa mai departe. Asta cere o coadă FIFO: adaugi la coadă (append) și scoți de la început (popleft).
Dacă scoți cu pop(), iei cel mai nou element, adică o stivă (LIFO). Parcurgerea devine o formă de DFS: merge cât de adânc poate pe o ramură, iar un nod poate fi descoperit întâi pe un drum lung. Dacă marchezi distanța la descoperire, ea rămâne prea mare. Nu primești nicio eroare: toate nodurile sunt vizitate, doar distanțele sunt greșite.
Aceeași problemă apare cu list.pop() în loc de list.pop(0). Pentru BFS, deque cu popleft() e varianta corectă și rapidă (O(1)).
De ce apare: cauzele frecvente
1pop() pe deque
coada = deque([start])
while coada:
u = coada.pop()coada = deque([start])
while coada:
u = coada.popleft()popleft scoate cel mai vechi nod, deci nivelurile sunt procesate în ordine.
2Listă folosită ca stivă
coada = [start]
while coada:
u = coada.pop()from collections import deque
coada = deque([start])
while coada:
u = coada.popleft()list.pop(0) ar fi corect ca ordine, dar e O(n). deque.popleft() e O(1).
Repară eroarea, direct în pagină
Funcția distante(graf, start) calculează cu BFS la câte stații distanță se află fiecare stație. Testul cu assert pică: stația 4 apare la distanța 3, deși drumul 1 → 2 → 4 are 2 pași. Repar-o ca testul să treacă și să afișeze {1: 0, 2: 1, 3: 1, 4: 2, 5: 2}.
from collections import deque
def distante(graf, start):
dist = {start: 0}
coada = deque([start])
while coada:
u = coada.pop()
for v in graf[u]:
if v not in dist:
dist[v] = dist[u] + 1
coada.append(v)
return dict(sorted(dist.items()))
graf = {1: [2, 3], 2: [4], 3: [5], 5: [4], 4: []}
rez = distante(graf, 1)
assert rez == {1: 0, 2: 1, 3: 1, 4: 2, 5: 2}, f'distante gresite: {rez}'
print(rez){1: 0, 2: 1, 3: 1, 4: 2, 5: 2}Indiciu
O coadă BFS scoate elementul cel mai vechi: popleft().
Reparația
from collections import deque
def distante(graf, start):
dist = {start: 0}
coada = deque([start])
while coada:
u = coada.popleft()
for v in graf[u]:
if v not in dist:
dist[v] = dist[u] + 1
coada.append(v)
return dict(sorted(dist.items()))
graf = {1: [2, 3], 2: [4], 3: [5], 5: [4], 4: []}
rez = distante(graf, 1)
assert rez == {1: 0, 2: 1, 3: 1, 4: 2, 5: 2}, f'distante gresite: {rez}'
print(rez)De ce merge
Cu pop(), după stația 1 se procesa întâi 3 (ultima adăugată), apoi 5, care descoperea stația 4 pe drumul 1 → 3 → 5 → 4, cu distanța 3. Stația 2, care ar fi dat distanța 2, venea abia după. Cu popleft() nodurile ies în ordinea în care au intrat: întâi toate stațiile la distanța 1, apoi cele la distanța 2, deci prima descoperire e mereu pe cel mai scurt drum.
Cum o eviți pe viitor
Asociază mereu: BFS = coadă = deque + append + popleft; DFS = stivă = listă + append + pop. Dacă ai nevoie de distanțe minime fără costuri, nu e negociabil: trebuie FIFO. Testează pe un graf în care un nod e accesibil atât printr-un drum scurt, cât și printr-unul lung, cu drumul lung explorat primul.
Întrebări frecvente
Dacă doar număr nodurile accesibile, contează?
Nu. Pentru „ce noduri pot atinge” merge și stiva, și coada. Ordinea contează doar pentru distanțe și nivele.
Pot folosi queue.Queue?
Merge, dar e făcută pentru fire de execuție și e mai lentă. Pentru algoritmi, collections.deque e alegerea standard.
Erori înrudite
AttributeError: 'list' object has no attribute 'popleft' popleft() există doar la collections.deque, nu la liste. Creează coada cu from collections import deque și coada = deque([start]); lista.pop(0) ar merge, dar e O(n) la fiecare scoatere. BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate) BFS-ul pune în coadă vecinii fără să verifice dacă au mai fost descoperiți, iar pe un graf cu ciclu (sau neorientat) aceleași noduri intră în coadă la nesfârșit; editorul oprește programul după limita de timp. Marchează nodul ca vizitat când îl pui în coadă. Graful neorientat are muchiile adăugate doar într-un sens: BFS nu ajunge la toate nodurile Pentru un graf neorientat (drumuri, prietenii, cabluri), fiecare muchie u-v trebuie adăugată în ambele liste: graf[u].append(v) și graf[v].append(u). Cu un singur sens, din v nu mai poți ajunge înapoi la u, iar BFS/DFS ratează noduri. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
