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

RecursionError la DFS: graful are un ciclu și lipsesc nodurile vizitate

Pe scurt

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

Greșit
PYTHON
def dfs(graf, nod, ordine):
    ordine.append(nod)
    for v in graf[nod]:
        dfs(graf, v, ordine)
Corect
PYTHON
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

Greșit
PYTHON
def dfs(nod):
    for v in graf[nod]:
        if v not in vazut:
            dfs(v)
    vazut.add(nod)
Corect
PYTHON
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

Greșit
PYTHON
dfs(lant_de_5000_de_noduri, 0)
Corect
PYTHON
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ă tu

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'].

Codul care dă eroarea
PYTHON
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'))
După reparație, programul afișează
['Ana', 'Bogdan', 'Dan', 'Cristi']
['Elena']
Indiciu

Ține minte într-un set nodurile vizitate și nu reintra în ele.

Alte forme ale mesajului

  • RecursionError: maximum recursion depth exceeded
  • RecursionError: 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

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