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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Sortarea topologică ordonează sarcinile astfel încât fiecare vine după dependențele ei. Algoritmul lui Kahn pornește cu nodurile care nu depind de nimic (grad intern 0), le scoate pe rând și scade gradul vecinilor; când un vecin ajunge la 0, intră în coadă.
Dacă există un ciclu (A depinde de B, B depinde de A), nodurile din ciclu nu ajung niciodată la gradul 0, deci nu intră în coadă. Algoritmul se termină normal, fără eroare, dar ordinea conține doar o parte din noduri. Dacă nu verifici lungimea, codul raportează o ordine „validă” care sare peste sarcini.
În varianta cu DFS, ciclul se detectează cu trei stări (nevizitat, în curs, terminat): un nod „în curs” întâlnit din nou înseamnă ciclu.
De ce apare: cauzele frecvente
1Lipsește verificarea lungimii
return ordineif len(ordine) < n:
return None
return ordineDacă nu toate nodurile au fost scoase, cele rămase sunt într-un ciclu sau depind de unul.
2DFS cu doar două stări
if v in vizitat:
continueif stare[v] == 'in_curs':
return True # ciclu
if stare[v] == 'nevizitat':
if dfs(v):
return TrueCu un singur set de vizitate nu poți deosebi un nod terminat de unul aflat pe drumul curent.
Repară eroarea, direct în pagină
Funcția ordine_sarcini(n, dependente) ordonează n sarcini, unde (a, b) înseamnă „a înaintea lui b”, sau returnează None dacă dependențele au un ciclu. Testul cu assert pică la al doilea exemplu: codul returnează o ordine incompletă. Repar-o ca să afișeze [0, 1, 2, 3] și None.
from collections import deque
def ordine_sarcini(n, dependente):
vecini = {i: [] for i in range(n)}
grad = [0] * n
for a, b in dependente:
vecini[a].append(b)
grad[b] += 1
coada = deque(i for i in range(n) if grad[i] == 0)
ordine = []
while coada:
u = coada.popleft()
ordine.append(u)
for v in vecini[u]:
grad[v] -= 1
if grad[v] == 0:
coada.append(v)
return ordine
for n, dep, corect in [(4, [(0, 1), (0, 2), (1, 3), (2, 3)], [0, 1, 2, 3]), (3, [(0, 1), (1, 2), (2, 1)], None)]:
rez = ordine_sarcini(n, dep)
assert rez == corect, f'ciclu nedetectat: {rez}'
print(rez)[0, 1, 2, 3] None
Indiciu
După bucla while, compară lungimea ordinii cu n.
Reparația
from collections import deque
def ordine_sarcini(n, dependente):
vecini = {i: [] for i in range(n)}
grad = [0] * n
for a, b in dependente:
vecini[a].append(b)
grad[b] += 1
coada = deque(i for i in range(n) if grad[i] == 0)
ordine = []
while coada:
u = coada.popleft()
ordine.append(u)
for v in vecini[u]:
grad[v] -= 1
if grad[v] == 0:
coada.append(v)
if len(ordine) < n:
return None
return ordine
for n, dep, corect in [(4, [(0, 1), (0, 2), (1, 3), (2, 3)], [0, 1, 2, 3]), (3, [(0, 1), (1, 2), (2, 1)], None)]:
rez = ordine_sarcini(n, dep)
assert rez == corect, f'ciclu nedetectat: {rez}'
print(rez)De ce merge
În al doilea exemplu, sarcinile 1 și 2 depind una de cealaltă, deci gradul lor nu ajunge niciodată la 0 și nu intră în coadă. Algoritmul se termina cu ordinea [0] și o raporta ca validă. Verificarea len(ordine) < n recunoaște că unele sarcini n-au putut fi programate și returnează None.
Cum o eviți pe viitor
Orice funcție de sortare topologică trebuie să spună explicit ce face cu ciclurile: returnează None, aruncă o excepție cu mesaj clar sau listează nodurile rămase. Testează întotdeauna și un graf cu ciclu, nu doar unul valid. graphlib.TopologicalSorter din biblioteca standard aruncă graphlib.CycleError în acest caz.
Întrebări frecvente
De ce nu primesc o eroare?
Coada se golește pur și simplu, iar bucla se termină. Pentru algoritm nu e nimic anormal; doar tu știi că trebuiau incluse toate nodurile.
Pot afla care noduri sunt în ciclu?
Nodurile cu grad intern rămas peste 0 sunt în ciclu sau după unul. Pentru ciclul exact, folosește DFS cu stări și reține drumul curent.
Erori înrudite
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. 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. 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ă. Î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.
