...
Eroare Algoritmi și structuri de date · Grafuri: BFS și DFS

BFS cu coada.pop() în loc de popleft(): distanțele ies prea mari

Pe scurt

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

Greșit
PYTHON
coada = deque([start])
while coada:
    u = coada.pop()
Corect
PYTHON
coada = deque([start])
while coada:
    u = coada.popleft()

popleft scoate cel mai vechi nod, deci nivelurile sunt procesate în ordine.

2Listă folosită ca stivă

Greșit
PYTHON
coada = [start]
while coada:
    u = coada.pop()
Corect
PYTHON
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ă tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
Indiciu

O coadă BFS scoate elementul cel mai vechi: popleft().

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

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