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

Detectarea ciclului într-un graf orientat găsește cicluri care nu există (doar un set vizitat)

Pe scurt

Într-un graf orientat, un nod deja vizitat nu înseamnă ciclu: poate fi atins pe două drumuri diferite. Ciclu există doar dacă revii la un nod aflat încă pe drumul curent al DFS-ului. Ține trei stări: nevizitat, pe stivă, terminat.

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

Ce înseamnă

La un graf neorientat, în DFS, întâlnirea unui nod vizitat (altul decât părintele) înseamnă ciclu. La un graf orientat regula nu mai e valabilă. În graful A → B, A → C, B → D, C → D, nodul D e atins o dată prin B și încă o dată prin C, dar nu există niciun ciclu: din D nu te poți întoarce nicăieri.

Un ciclu orientat înseamnă că, mergând pe săgeți, revii la un nod de pe drumul curent, adică la un strămoș încă neterminat în DFS. De aceea ai nevoie de trei stări: nevizitat, „pe stivă” (DFS-ul e încă în interiorul lui) și „terminat” (toți descendenții lui au fost explorați). Muchia spre un nod „pe stivă” închide un ciclu, iar muchia spre un nod „terminat” e inofensivă.

Greșeala apare des la verificarea dependențelor (cursuri cu precondiții, sarcini, pachete): programul raportează dependențe circulare false.

De ce apare: cauzele frecvente

1Un singur set de noduri vizitate

Greșit
PYTHON
def dfs(nod):
    if nod in vizitat:
        return True
    vizitat.add(nod)
    return any(dfs(v) for v in graf[nod])
Corect
PYTHON
def dfs(nod):
    stare[nod] = 1          # pe stivă
    for v in graf[nod]:
        if stare.get(v) == 1:
            return True
        if v not in stare and dfs(v):
            return True
    stare[nod] = 2          # terminat
    return False

Doar revenirea la un nod cu starea 1 înseamnă ciclu. Nodurile cu starea 2 au fost deja explorate complet și nu pot închide un ciclu cu drumul curent.

2Alternativa fără recursivitate: algoritmul lui Kahn

Greșit
PYTHON
# DFS cu set vizitat pe un graf orientat
Corect
PYTHON
intrari = {n: 0 for n in graf}
for n in graf:
    for v in graf[n]:
        intrari[v] += 1
coada = deque(n for n in graf if intrari[n] == 0)
procesate = 0
while coada:
    n = coada.popleft()
    procesate += 1
    for v in graf[n]:
        intrari[v] -= 1
        if intrari[v] == 0:
            coada.append(v)
are_ciclu = procesate < len(graf)

Sortarea topologică prin grade de intrare procesează toate nodurile doar dacă graful nu are cicluri.

Repară tu

Repară eroarea, direct în pagină

Funcția are_ciclu(graf) verifică dacă un graf orientat de dependențe are un ciclu. Testul cu assert pică: pentru graful romb A → B, A → C, B → D, C → D, care nu are ciclu, returnează True. Repar-o ca să afișeze False pentru romb și True pentru ciclul A → B → C → A.

Codul care dă eroarea
PYTHON
def are_ciclu(graf):
    vizitat = set()

    def dfs(nod):
        if nod in vizitat:
            return True
        vizitat.add(nod)
        for v in graf[nod]:
            if dfs(v):
                return True
        return False

    return any(dfs(n) for n in graf if n not in vizitat)

romb = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
ciclu = {'A': ['B'], 'B': ['C'], 'C': ['A']}
r1, r2 = are_ciclu(romb), are_ciclu(ciclu)
assert (r1, r2) == (False, True), f'ciclu gresit: {r1}, {r2}'
print(r1)
print(r2)
După reparație, programul afișează
False
True
Indiciu

Ține pentru fiecare nod o stare: pe drumul curent sau terminat. Doar revenirea la un nod de pe drumul curent înseamnă ciclu.

Cum o eviți pe viitor

Când scrii o detectare de ciclu, notează întâi dacă graful e orientat sau nu: regulile sunt diferite. Pentru grafuri orientate, folosește cele trei stări sau algoritmul lui Kahn. Testează pe un graf „romb” (două drumuri spre același nod, fără ciclu) și pe un ciclu simplu de trei noduri: primul trebuie să dea False, al doilea True.

Întrebări frecvente

De ce la grafurile neorientate merge cu un singur set?

Acolo fiecare muchie se poate parcurge în ambele sensuri, deci două drumuri diferite spre același nod formează întotdeauna un ciclu. Trebuie doar să ignori muchia spre părintele din care ai venit.

Cum aflu și care e ciclul?

Ține un dicționar parinte în DFS. Când găsești muchia spre un nod cu starea „pe stivă”, mergi înapoi prin parinte de la nodul curent până la acel nod.

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.