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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Spre deosebire de un arbore, un graf poate avea cicluri: din A ajungi în B, din B înapoi în A. Orice graf neorientat are „cicluri” de lungime 2, pentru că fiecare muchie apare în ambele sensuri. Un DFS recursiv care nu ține minte ce noduri a vizitat va merge A → B → A → B... la nesfârșit, fiecare pas fiind un apel recursiv nou, până la RecursionError: maximum recursion depth exceeded.
Soluția este un set vazut (sau vizitat): marchezi nodul când intri în el și nu mai apelezi DFS pentru vecinii deja marcați. Marcarea se face înainte de apelurile recursive, altfel ciclul tot se repetă.
Dacă DFS-ul are deja vazut și tot primești eroarea, graful e pur și simplu prea adânc (un lanț de peste aproximativ 1000 de noduri). În acest caz, scrie DFS-ul iterativ, cu o stivă explicită.
De ce apare: cauzele frecvente
1Fără set de vizitate
def dfs(graf, nod, ordine):
ordine.append(nod)
for v in graf[nod]:
dfs(graf, v, ordine)def dfs(graf, nod, ordine, vazut):
vazut.add(nod)
ordine.append(nod)
for v in graf[nod]:
if v not in vazut:
dfs(graf, v, ordine, vazut)Nodurile din vazut nu mai sunt vizitate a doua oară, deci ciclul A-B-A se oprește.
2Marcare după apelurile recursive
def dfs(nod):
for v in graf[nod]:
if v not in vazut:
dfs(v)
vazut.add(nod)def dfs(nod):
vazut.add(nod)
for v in graf[nod]:
if v not in vazut:
dfs(v)Dacă marchezi la final, vecinul B vede că A încă nu e marcat și intră din nou în A.
3Graf prea adânc pentru recursivitate
dfs(lant_de_5000_de_noduri, 0)stiva, vazut = [0], {0}
while stiva:
nod = stiva.pop()
for v in graf[nod]:
if v not in vazut:
vazut.add(v)
stiva.append(v)Varianta iterativă nu folosește stiva de apeluri a lui Python, deci nu are limita de ~1000 de niveluri.
Repară eroarea, direct în pagină
Funcția componenta(graf, start) returnează nodurile la care poți ajunge din start, în ordinea DFS, într-o rețea de prieteni (graf neorientat). Codul dă RecursionError: maximum recursion depth exceeded. Repar-o ca să afișeze ['Ana', 'Bogdan', 'Dan', 'Cristi'] și ['Elena'].
def componenta(graf, start):
ordine = []
def dfs(nod):
ordine.append(nod)
for v in graf[nod]:
dfs(v)
dfs(start)
return ordine
prieteni = {
'Ana': ['Bogdan', 'Cristi'],
'Bogdan': ['Ana', 'Dan'],
'Cristi': ['Ana'],
'Dan': ['Bogdan'],
'Elena': [],
}
print(componenta(prieteni, 'Ana'))
print(componenta(prieteni, 'Elena'))['Ana', 'Bogdan', 'Dan', 'Cristi'] ['Elena']
Indiciu
Ține minte într-un set nodurile vizitate și nu reintra în ele.
Reparația
def componenta(graf, start):
ordine = []
vazut = set()
def dfs(nod):
vazut.add(nod)
ordine.append(nod)
for v in graf[nod]:
if v not in vazut:
dfs(v)
dfs(start)
return ordine
prieteni = {
'Ana': ['Bogdan', 'Cristi'],
'Bogdan': ['Ana', 'Dan'],
'Cristi': ['Ana'],
'Dan': ['Bogdan'],
'Elena': [],
}
print(componenta(prieteni, 'Ana'))
print(componenta(prieteni, 'Elena'))De ce merge
Graful e neorientat: Ana îl are pe Bogdan ca prieten, iar Bogdan o are pe Ana. Fără set de vizitate, DFS-ul mergea Ana → Bogdan → Ana → Bogdan, la nesfârșit, până la limita stivei. Cu vazut, marcat la intrarea în nod, Bogdan nu se mai întoarce la Ana, ci merge la Dan, apoi DFS-ul revine și vizitează Cristi. Fiecare nod e vizitat o singură dată: O(noduri + muchii).
Alte forme ale mesajului
RecursionError: maximum recursion depth exceededRecursionError: maximum recursion depth exceeded while calling a Python object
Cum o eviți pe viitor
Orice parcurgere de graf (DFS, BFS, flood fill pe grilă) are nevoie de un set de vizitate, marcat în momentul în care intri în nod (sau când îl pui în stivă/coadă). Pe grile, poți marca direct celula (de exemplu o schimbi din 1 în 0), dacă ai voie să modifici harta. Dacă numărul de noduri poate depăși câteva sute pe un singur drum, preferă varianta iterativă.
Întrebări frecvente
Graful meu nu are cicluri, dar tot primesc eroarea. De ce?
Dacă e neorientat, fiecare muchie apare în ambele liste de vecini, deci din A mergi în B și din B înapoi în A. Pentru DFS asta e un ciclu.
Pe un arbore am nevoie de set de vizitate?
Pe un arbore cu legături doar spre copii, nu. Dacă arborele e dat ca graf neorientat (listă de muchii), da: sau ține minte părintele și nu te întoarce în el.
Erori înrudite
RecursionError: maximum recursion depth exceeded Funcția recursivă s-a apelat de prea multe ori fără să se oprească, iar Python a depășit limita de aproximativ 1000 de apeluri imbricate. Adaugă un caz de bază (de exemplu if n <= 1: return 1) și verifică dacă fiecare apel se apropie de el. 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ă. UnboundLocalError: cannot access local variable 'numar' where it is not associated with a value O funcție interioară (de obicei un dfs sau backtrack definit în altă funcție) modifică cu += o variabilă a funcției din afară. Python o tratează ca variabilă locală nouă, fără valoare. Declar-o cu nonlocal numar sau folosește o listă / returnează valoarea. Î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.
