De ce contează?
Dimineața te îmbraci într-o ordine care nu e întâmplătoare: nu poți pune pantofii înainte de șosete, nici geaca înainte de tricou. Unele lucruri trebuie să vină înaintea altora — asta e o dependență. Sortarea topologică e exact arta de a aranja niște sarcini într-un șir astfel încât fiecare dependență să fie respectată: tot ce trebuie făcut „înainte” chiar apare mai devreme.
Intuiția
Imaginează-ți task-uri legate prin săgeți: un arc u → v spune „u trebuie
făcut înaintea lui v”. Vrei să așezi toate task-urile pe o singură linie,
de la stânga la dreapta, astfel încât fiecare săgeată să arate doar înainte.
Asta e o ordine topologică. Ea există numai dacă graful e orientat și fără
cicluri (un DAG) — dacă A așteaptă pe B și B așteaptă pe A, niciun șir nu-i
poate mulțumi pe amândoi.
Două fapte-cheie: există o ordine topologică exact atunci când graful e un DAG, iar pe orice DAG găsești măcar un nod cu grad interior 0 — în el nu intră nicio săgeată, deci nu depinde de nimeni și poate sta liniștit pe primul loc. Tot algoritmul e repetarea acestei observații.