Sortare topologică

Sortarea topologică este ordonarea vârfurilor unui graf direcționat fără contur în funcție de ordinea parțială dată de muchiile digrafului pe mulțimea vârfurilor acestuia.

Exemplu

Pentru Conte $G={\Bigl (}{\bigl \{}2,3,5,7,8,9,10,11{\bigr \)),{\bigl \{}(3,8),(3, 10),(5,11),(7,11),(7,8),(8,9),(11,2),(11,9),(11,10){\bigr \)) {\Bigr )}$

există mai multe secvențe consistente ale vârfurilor sale, care pot fi obținute folosind o sortare topologică, de exemplu:

$7,5,11,3,8,2,9,10$
$3,7,5,8,11,10,9,2$

Se poate observa că oricare două vârfuri adiacente care nu sunt incluse în relația de ordine parțială pot fi permutate în succesiune . $E$

Algoritmul lui Kahn (1962)

Unul dintre primii algoritmi și cel mai potrivit pentru execuția manuală.

Să fie dat un grafic simplu orientat fără contur . Se notează prin mulțimea de vârfuri astfel încât . Adică , mulțimea tuturor vârfurilor de la care există un arc până la vârf . Fie șirul dorit de vârfuri. $G=(V,E)$ $A(v),v\în V$ $u\in V$ $\exists ~(u,v)\in E$ $A(v)$ $v$ $P$

pentru moment alege orice vârf astfel încât și șterge din toate

|P|<|V|

v

A(v)=\varnothing

v\notin P

P\getează P,v

v

A(u),u\neq v

Prezența a cel puțin unui contur în grafic va duce la faptul că la o anumită iterație a ciclului nu va fi posibilă selectarea unui nou vârf . $v$

Un exemplu despre cum funcționează algoritmul

Să fie dat un grafic . În acest caz, algoritmul va rula după cum urmează: $G={\Bigl (}{\bigl \{}a,b,c,d,e{\bigr \)),{\bigl \{}(a,b),(a,c),(a, d),(a,e),(b,d),(c,d),(c,e),(d,e){\bigr \}}{\Bigr )}$

Etapa	$v$	$A(a)$	$A(b)$	$A(c)$	$Anunț)$	$A(e)$	$P$
0	$-$	$\varnothing$	$A$	$A$	$a,b,c$	$a,c,d$	$\varnothing$
unu	$A$	$\varnothing$	$\varnothing$	$\varnothing$	$b,c$	$c, d$	$A$
2	$c$	$\varnothing$	$\varnothing$	$\varnothing$	$b$	$d$	$a,c$
3	$b$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$d$	$a,c,b$
patru	$d$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a,c,b,d$
5	$e$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a,c,b,d,e$

În al doilea pas , vârful poate fi ales în loc de , deoarece ordinea dintre și nu este specificată. $c$ $b$ $b$ $c$

Algoritmul lui Tarjan ( 1976)

Pe un computer, o sortare topologică poate fi făcută în timp și memorie O( n ) prin parcurgerea tuturor nodurilor folosind căutarea depth-first și scoaterea vârfurilor la punctul de ieșire.

Cu alte cuvinte, algoritmul este următorul:

Inițial, toate vârfurile sunt albe.
Pentru fiecare vârf facem un pas al algoritmului.

Pasul algoritmului:

Dacă vârful este negru, nu trebuie făcut nimic.
Dacă vârful este gri, se găsește un ciclu, sortarea topologică nu este posibilă.
Dacă vârful este alb
- Vopsește-l cu gri
- Aplicăm pasul algoritmului tuturor vârfurilor la care se poate ajunge din curent
- Colorează vârful în negru și plasează-l în partea de sus a listei finale.

Exemplu

Exemplul va fi pe același grafic, dar ordinea în care selectăm vârfurile de ocolit este c, d, e, a, b.

Etapa	Actual	alb	Stivă (gri)	Ieșire (negru)
0	—	a, b, c, d, e	—	—
unu	c	a, b, d, e	c	—
2	d	a fi	c, d	—
3	e	a, b	c, d, e	—
patru	d	a, b	c, d	e
5	c	a, b	c	d, e
6	—	a, b	—	c, d, e
7	d	a, b	—	c, d, e
opt	e	a, b	—	c, d, e
9	A	b	A	c, d, e
zece	b	—	a, b	c, d, e
unsprezece	A	—	A	b, c, d, e
12	—	—	—	a, b, c, d, e
13	b	—	—	a, b, c, d, e

Aplicație

Cu ajutorul sortării topologice, se construiește o secvență corectă de acțiuni, fiecare dintre acestea putând depinde de cealaltă: succesiunea de promovare a cursurilor de formare de către studenți, instalarea programelor folosind managerul de pachete , construirea codurilor sursă a programelor folosind Makefiles .

Este posibil să construiți o listă de afișare a obiectelor într- o proiecție izometrică cunoscând relațiile ordinale pereche dintre obiecte (care dintre cele două obiecte ar trebui desenat primul).

Vezi și

algoritmul lui Demucron

Link -uri

Literatură

Levitin A. V. Capitolul 5. Metoda de reducere a dimensiunii problemei: Sortare topologică // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 220-224. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capitolul 22.4. Sortare topologică // Algoritmi: construcție și analiză = Introducere în algoritmi / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - S. 632-635. — ISBN 5-8459-0857-4 .

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet