Sortarea topologică
De fiecare dată când instalați un program, construiți o aplicație sau planificați un proiect, ceva trebuie să stabilească ce se face mai întâi. Dacă sarcina B are nevoie de sarcina A, A trebuie să vină mai devreme. O sortare topologică transformă o rețea de astfel de reguli într-o singură linie dreaptă.
Ideea
Desenați fiecare sarcină ca un nod și fiecare regulă "A înainte de B" ca o săgeată de la A la B. O ordine topologică este un rând cu toate nodurile în care fiecare săgeată indică spre dreapta. Se numește sortare pentru că pune lucrurile în ordine, dar, spre deosebire de sortarea numerelor, trebuie doar să respecte săgețile: nodurile pe care nu le leagă niciun lanț de săgeți pot veni în orice ordine.
Când este imposibil
Dacă săgețile formează un ciclu, de exemplu A înainte de B, B înainte de C și C înainte de A, atunci A ar trebui să vină înaintea lui însuși. Deci o ordine topologică există exact atunci când graful nu are niciun ciclu orientat. Un astfel de graf se numește graf orientat aciclic, sau DAG. Ambele metode de mai jos găsesc un ciclu dacă există unul, deci sunt și un test util pentru cicluri.
Un exemplu
Luați săgețile A → C, B → C, B → D, C → E și D → E. Algoritmul lui Kahn numără săgețile de intrare: A și B nu au niciuna, deci A vine primul, apoi B. Eliminarea săgeților lui B eliberează C și D, care urmează, apoi E: ordinea A, B, C, D, E. Metoda DFS vizitează A, apoi C, apoi E; E se termină primul, apoi C, apoi A, fiecare trecând în față. Apoi vizitează B și D, care se termină înaintea lor: ordinea B, D, A, C, E. Ambele ordini sunt corecte.
Kahn sau DFS?
Algoritmul lui Kahn, publicat de Arthur Kahn în 1962, lucrează înainte: știe mereu ce sarcini pot începe acum, ceea ce se potrivește planificării, și poate alege între sarcinile libere după orice regulă, de exemplu în ordine alfabetică. Metoda DFS, popularizată de Robert Tarjan în 1976, lucrează înapoi de la capete și are nevoie doar de o căutare în adâncime. La ambele, timpul crește cu numărul de noduri plus muchii.
Aplicații
Instrumentele de build precum make compilează fișierele după fișierele de care depind. Managerii de pachete instalează bibliotecile în ordinea dependențelor. Foile de calcul recalculează o celulă după celulele pe care le folosește formula ei. Universitățile verifică dacă cerințele preliminare ale cursurilor pot fi îndeplinite, compilatoarele ordonează instrucțiunile, iar fluxurile de date rulează fiecare pas după ce datele lui de intrare sunt gata. Comanda Unix tsort face singură o sortare topologică.
Explorați
Deschideți aplicația și apăsați Pas. Săgețile spun ce nod trebuie să vină înaintea cărui nod. Cu algoritmul lui Kahn, numărul de pe fiecare nod numără săgețile de intrare rămase, iar nodurile libere sunt albastre. Cu metoda DFS, nodurile albastre sunt în curs de vizitare, iar cele verzi sunt plasate. Ordinea crește în rândul de sub graf. Bifați Adaugă un ciclu și urmăriți cum ambele metode descoperă că nu există nicio ordine.
Întrebări frecvente
Ce înseamnă aici topologic?
Numele vine de la topologie, studiul modului în care lucrurile sunt conectate, nu al formei lor exacte. Ordinea depinde doar de ce noduri sunt legate prin săgeți, nu de locul în care sunt desenate.
Cum găsesc ciclul când nu există nicio ordine?
Metoda DFS îl arată direct: muchia spre un nod aflat încă în curs de vizitare, împreună cu drumul nodurilor în curs de vizitare, formează ciclul. Algoritmul lui Kahn spune doar ce noduri sunt blocate; o căutare printre ele găsește ciclul.
Pot alege o anumită ordine dintre cele valide?
Da. În algoritmul lui Kahn, când mai multe noduri sunt libere, alegeți-l pe cel pe care îl preferați, de exemplu cu litera cea mai mică sau sarcina cea mai urgentă. Cu o coadă de priorități obțineți ordinea care vine prima alfabetic.
Cum se folosește sortarea topologică pentru drumuri minime?
Într-un graf orientat aciclic, actualizarea distanțelor de-a lungul muchiilor fiecărui nod, în ordine topologică, găsește toate drumurile minime de la un start într-o singură trecere, chiar și cu muchii negative, mai repede decât Dijkstra sau Bellman–Ford.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați sortarea topologică