De ce contează?
Imaginează-ți organigrama unui proiect mare împărțit pe etape. Un task nu poate începe până când TOATE task-urile de care depinde s-au terminat. Așezi fiecare task în prima etapă posibilă: cele care nu depind de nimic intră în Etapa 0, cele care depind doar de Etapa 0 intră în Etapa 1, și tot așa. La final, „eticheta de etapă” a unui task îți spune câte runde de muncă se acumulează în spatele lui.
Intuiția
Un DAG (graf orientat fără circuite) modelează exact dependențe: o muchie u → v
înseamnă „v depinde de u”. Vrem să dăm fiecărui nod un nivel: numărul de pași
din cel mai lung lanț de dependențe care se termină în el. Nodurile fără nicio
dependență (grad interior 0) sunt sursele — ele stau pe nivelul 0. Orice alt nod
stă cu un nivel mai sus decât cel mai „adânc” predecesor al său.
Același concept, văzut din două unghiuri. Pe valuri: scoți simultan toate
nodurile cu grad interior 0 (valul 0), apoi tot ce rămâne fără predecesori
(valul 1), strat după strat. Pe formulă: nivel[v] = 1 + max(nivel[u])
peste toți predecesorii u, iar sursele au nivel = 0. Valul din care se
desprinde un nod este exact nivelul lui — cele două definiții coincid.