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

BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate)

Pe scurt

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

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

BFS-ul scoate un nod din coadă și adaugă vecinii lui. Bucla while coada se termină doar când coada se golește. Într-un graf cu cicluri, fără un set de vizitate, fiecare nod își adaugă din nou vecinii, care îl adaugă înapoi pe el, iar coada nu se golește niciodată. Pe grafuri mai dense, coada chiar crește exponențial și programul rămâne fără memorie.

Python nu dă o excepție. În editorul nostru vezi „Programul a rulat prea mult și a fost oprit”; pe calculatorul tău programul pare blocat.

Detaliu important: la BFS, nodul se marchează când e pus în coadă, nu când e scos. Dacă marchezi la scoatere, același nod poate intra de mai multe ori în coadă (din vecini diferiți) înainte să fie procesat. Rezultatul rămâne corect pentru vizitare, dar distanțele se pot strica și algoritmul face muncă în plus.

De ce apare: cauzele frecvente

1Fără set de vizitate

Greșit
PYTHON
coada = deque([start])
while coada:
    nod = coada.popleft()
    for v in graf[nod]:
        coada.append(v)
Corect
PYTHON
coada = deque([start])
vazut = {start}
while coada:
    nod = coada.popleft()
    for v in graf[nod]:
        if v not in vazut:
            vazut.add(v)
            coada.append(v)

Fiecare nod intră o singură dată în coadă, deci coada se golește după ce toate nodurile accesibile au fost procesate.

2Marcare la scoatere, nu la adăugare

Greșit
PYTHON
while coada:
    nod = coada.popleft()
    vazut.add(nod)
    for v in graf[nod]:
        if v not in vazut:
            coada.append(v)
Corect
PYTHON
while coada:
    nod = coada.popleft()
    for v in graf[nod]:
        if v not in vazut:
            vazut.add(v)
            coada.append(v)

În prima variantă un nod poate fi pus în coadă de mai multe ori înainte să fie scos. Marcarea la adăugare garantează o singură intrare per nod.

Repară tu

Repară eroarea, direct în pagină

Funcția cel_mai_scurt(graf, start, tinta) calculează cu BFS numărul minim de stații de metrou între start și tinta (sau -1). Rețeaua are un ciclu, iar programul nu se mai termină și e oprit după limita de timp. Repar-o ca să afișeze 2, 0 și -1.

Codul care dă eroarea
PYTHON
from collections import deque

def cel_mai_scurt(graf, start, tinta):
    coada = deque([(start, 0)])
    while coada:
        nod, d = coada.popleft()
        if nod == tinta:
            return d
        for v in graf[nod]:
            coada.append((v, d + 1))
    return -1

metrou = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C'], 'E': []}
print(cel_mai_scurt(metrou, 'A', 'D'))
print(cel_mai_scurt(metrou, 'B', 'B'))
print(cel_mai_scurt(metrou, 'A', 'E'))
După reparație, programul afișează
2
0
-1
Indiciu

Ține minte stațiile deja descoperite și nu le mai pune în coadă.

Alte forme ale mesajului

  • Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.
  • MemoryError

Cum o eviți pe viitor

Scrie BFS-ul din șablonul fix: coada și setul vazut pornesc amândouă cu start; un vecin nou e adăugat în același timp în vazut și în coadă. Pentru distanțe, un dicționar dist poate ține și rolul de vazut (if v not in dist). Testează pe un graf neorientat cu un ciclu mic (A-B-C-A) înainte de datele mari.

Întrebări frecvente

Cum îmi dau seama că problema e coada, nu altceva?

Afișează len(coada) la fiecare pas pentru primii 20 de pași. Dacă lungimea nu scade spre 0 și vezi aceleași noduri repetându-se, lipsește verificarea de vizitate.

La grile (hărți) cum marchez celulele?

Cu un set de tupluri (r, c), sau modificând celula direct în hartă (de exemplu din '.' în '#') în momentul în care o pui în coadă.

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.