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

Sortarea topologică nu detectează ciclul: returnează o ordine incompletă

Pe scurt

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

Greșit
PYTHON
return ordine
Corect
PYTHON
if len(ordine) < n:
    return None
return ordine

Dacă nu toate nodurile au fost scoase, cele rămase sunt într-un ciclu sau depind de unul.

2DFS cu doar două stări

Greșit
PYTHON
if v in vizitat:
    continue
Corect
PYTHON
if stare[v] == 'in_curs':
    return True  # ciclu
if stare[v] == 'nevizitat':
    if dfs(v):
        return True

Cu un singur set de vizitate nu poți deosebi un nod terminat de unul aflat pe drumul curent.

Repară tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[0, 1, 2, 3]
None
Indiciu

După bucla while, compară lungimea ordinii cu n.

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

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