Ordonarea topologică

În teoria graficelor, o sortare topologică ( sortare topologică în limba engleză) este o linie de sortare a tuturor vârfurilor unui grafic aciclic direcționat ( grafic aciclic direcționat de DAG ). Nodurile unui grafic sunt definite topologic ordonate dacă nodurile sunt aranjate în așa fel încât fiecare nod să fie înaintea tuturor nodurilor conectate la arcurile sale de ieșire. Ordinea topologică nu este o ordonare totală , deoarece soluția poate să nu fie unică. De fapt, în cel mai rău caz pot fi avute $n!$ ${\ displaystyle n!}$ $n!$ diferite ordonări topologice care corespund tuturor permutărilor posibile ale $n$ ${\ displaystyle n}$ $n$ noduri. Este posibil să se ordoneze un grafic topologic dacă și numai dacă nu are circuite (adică numai dacă este un grafic aciclic direct ), iar algoritmii sunt cunoscuți pentru determinarea unei ordonări topologice în timp liniar.

Exemple

Aplicarea canonică a ordonării topologice se află în problema planificării execuției unei secvențe de sarcini în funcție de dependențele lor. Activitățile sunt reprezentate de nodurile unui grafic: există un arc între $X$ ${\ displaystyle x}$ $X$ Și $y$ ${\ displaystyle y}$ $y$ dacă activitatea $X$ ${\ displaystyle x}$ $X$ trebuie finalizat înainte ca sarcina să poată începe executarea $y$ ${\ displaystyle y}$ $y$ . O ordonare topologică a graficului astfel obținut oferă o ordine în care să efectueze activitățile.

Unele ordonări topologice valide pentru graficul prezentat în stânga sunt:

7, 5, 3, 11, 8, 2, 9, 10 (grafic de la stânga la dreapta și de sus în jos)
3, 5, 7, 8, 11, 2, 9, 10 (mai întâi nodurile cu cele mai mici valori ale numerotării lor)
3, 7, 8, 5, 11, 10, 2, 9
5, 7, 3, 8, 11, 10, 9, 2
7, 5, 11, 3, 10, 8, 9, 2 (mai întâi nodurile cu cele mai mari valori ale numerotării lor)
7, 5, 11, 2, 3, 8, 9, 10

Algoritmi

Unul dintre algoritmii clasici pentru ordonarea topologică a unui grafic se bazează pe conceptul de căutare în profunzime . Algoritmul de sortare topologică efectuează o vizită de adâncime a graficului (începând de la fiecare dintre noduri fără a introduce arcuri) și, odată ce vizita fiecărui vârf este terminată, îl introduce în capul unei liste legate L. La sfârșitul în execuție, această listă va conține nodurile sortate. În pseudocod:

 L ← Lista goală (va conține noduri sortate)
S ← Set de toate nodurile fără a introduce arcuri
pentru fiecare nod n din S do
    vizita (n) 
întoarce L

unde procedura de vizitare este definită ca

 vizită de funcție (nod n)
    dacă n nu a fost încă vizitat atunci
        marca n așa cum a fost vizitată
        pentru fiecare nod m cu un arc din nam do
            vizita (substantiv)
        adaugă na L

Rețineți că algoritmul pentru care este furnizat pseudocodul nu este capabil să determine cazul (eroare) în care există bucle în grafic, dar poate face acest lucru cu modificări simple.

Algoritmul harvtxt , descris de Kahn (1962), ^[1] alege vârfurile respectând ordonarea topologică. Inițial, construiește un set de vârfuri care nu au margini de intrare (grad de intrare = 0); deoarece graficul este aciclic există cel puțin unul dintre aceste noduri. Atunci:

 L ← listă goală care va conține elementele sortate
S ← set de noduri fără a introduce arcuri
în timp ce S nu este gol faceți
    scoateți un vârf u din S
    introduceți u în L
    pentru fiecare vârf v cu un arc și din uav do
        eliminați arcul și din grafic
        dacă v nu are alte margini de intrare atunci
            introduceți v în S
dacă graficul mai are margini atunci
    returnează o eroare (graficul are cel puțin o buclă)
altceva 
    returnează L (ordinea topologică)

Dacă graficul este un DAG , soluția este conținută în lista L (nu neapărat unică). În caz contrar, graficul are cel puțin un ciclu și este imposibil să se obțină o ordonare topologică.

Mulțimea S poate fi o mulțime, o coadă sau o stivă, deoarece nu contează în ce ordine sunt extrase vârfurile. Soluții diferite se datorează ordinii în care nodurile sunt extrase din S.

Complexitate

Pentru un grafic G (V, E) unde V este setul de noduri și E setul de margini, ambii algoritmi au o complexitate liniară O (| V | + | E |) , în timp ce inserarea fiecăruia dintre | V | vârfurile din partea de sus a listei conectate necesită timp constant. În general, prin urmare, algoritmii necesită timp O (| V | + | E |) .

Notă

^ (EN) Arthur B. Kahn, Sortarea topologică a rețelelor mari , în Communications of the ACM, vol. 5, nr. 11, 1962, pp. 558-562, DOI : 10.1145 / 368996.369025 .

Bibliografie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi . Jackson Books, 2003, ISBN 88-256-1421-7 .

Portal IT

Portalul de matematică

[1] (EN) Arthur B. Kahn, Sortarea topologică a rețelelor mari , în Communications of the ACM, vol. 5, nr. 11, 1962, pp. 558-562, DOI : 10.1145 / 368996.369025 .

[1]

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel