Detectarea ciclului într-un graf orientat găsește cicluri care nu există (doar un set vizitat)
Î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
def dfs(nod):
if nod in vizitat:
return True
vizitat.add(nod)
return any(dfs(v) for v in graf[nod])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 FalseDoar 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
# DFS cu set vizitat pe un graf orientatintrari = {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ă 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.
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)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.
Reparația
def are_ciclu(graf):
stare = {}
def dfs(nod):
stare[nod] = 1
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
return False
return any(dfs(n) for n in graf if n not in stare)
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)De ce merge
În romb, DFS-ul merge A, B, D, termină D, se întoarce și apoi ajunge din C tot la D. Cu un singur set, D era deja vizitat, deci funcția raporta ciclu. Cu stări, D are starea 2 (terminat) când e atins din C, iar asta nu e un ciclu. În graful A → B → C → A, când DFS-ul ajunge din C la A, A are încă starea 1, pentru că explorarea lui nu s-a terminat, deci ciclul e real.
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
Sortarea topologică nu detectează ciclul: returnează o ordine incompletă Algoritmul lui Kahn scoate doar nodurile fără dependențe rămase; nodurile dintr-un ciclu nu ajung niciodată la gradul 0, deci lipsesc din rezultat. La final verifică len(ordine) == n și returnează None (sau o eroare) dacă nu e așa. 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. Union-Find leagă nodurile, nu rădăcinile: ciclurile nu sunt detectate La reuniune ai scris parinte[a] = b, care rupe nodul a din grupul lui vechi. Trebuie să legi rădăcinile: ra, rb = gaseste(a), gaseste(b); dacă sunt diferite, parinte[ra] = rb. Altfel grupurile se despart și găsirea ciclurilor dă rezultate greșite. Î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.
