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ă.
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
coada = deque([start])
while coada:
nod = coada.popleft()
for v in graf[nod]:
coada.append(v)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
while coada:
nod = coada.popleft()
vazut.add(nod)
for v in graf[nod]:
if v not in vazut:
coada.append(v)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ă 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.
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'))2 0 -1
Indiciu
Ține minte stațiile deja descoperite și nu le mai pune în coadă.
Reparația
from collections import deque
def cel_mai_scurt(graf, start, tinta):
coada = deque([(start, 0)])
vazut = {start}
while coada:
nod, d = coada.popleft()
if nod == tinta:
return d
for v in graf[nod]:
if v not in vazut:
vazut.add(v)
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'))De ce merge
Primele două teste se terminau și în varianta stricată, pentru că ținta e găsită înainte ca ciclul să conteze. Pentru E, care nu e legată de nimic, BFS-ul fără vazut punea la nesfârșit în coadă stațiile A, B, C, D, care se trimit una pe alta, iar coada nu se golea. Cu vazut, fiecare stație intră o singură dată în coadă; după ce A, B, C și D sunt procesate, coada se golește și funcția returnează -1.
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
RecursionError la DFS: graful are un ciclu și lipsesc nodurile vizitate DFS-ul recursiv nu ține minte nodurile vizitate, iar graful are un ciclu (sau e neorientat: A-B înseamnă și B-A), deci se plimbă la nesfârșit până la RecursionError. Adaugă un set vazut și nu reintra în nodurile din el. IndexError: pop from an empty deque Ai apelat coada.popleft() (sau pop()) pe un deque gol: bucla a continuat după ce coada s-a golit, sau ai scos de două ori pentru un singur element pus. Folosește while coada: și scoate un singur element pe iterație. Parcurgerea listei înlănțuite nu se mai oprește (lipsește curent = curent.urm) În bucla while curent: ai uitat să avansezi cu curent = curent.urm (sau avansezi doar pe o ramură a unui if), așa că nodul curent nu se schimbă și bucla rulează la nesfârșit; editorul o oprește după limita de timp. Avansează pe fiecare drum prin buclă. Î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.
