Topológiai rendezés

A topológiai rendezés egy kontúr nélküli irányított gráf csúcsainak rendezése a digráf élei által adott részleges sorrend szerint a csúcsok halmazán.

Példa

Grófnak $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 )}$

csúcsainak számos konzisztens sorozata van, amelyeket topológiai rendezéssel kaphatunk meg, például:

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

Látható, hogy bármely két szomszédos csúcs, amely nem szerepel a részleges sorrendű relációban, permutálható a sorozatban . $E$

Kahn algoritmusa (1962)

Az egyik első algoritmus, és a legalkalmasabb a kézi végrehajtásra.

Legyen adott egy kontúrmentes orientált egyszerű gráf . Jelölje a csúcsok halmazával , hogy . Azaz az összes csúcs halmaza, ahonnan ív van a csúcsra . Legyen a kívánt csúcssorozat. $G=(V,E)$ $A(v),v\in V$ $u\in V$ $\exists ~(u,v)\in E$ $A(v)$ $v$ $P$

egyelőre válasszon egy ilyen csúcsot , és törölje az összesből

|P|<|V|

v

A(v)=\varnothing

v\notin P

P\gets P,v

v

A(u),u\neq v

Legalább egy kontúr jelenléte a gráfban ahhoz a tényhez vezet, hogy a ciklus egy bizonyos iterációjánál nem lehet új csúcsot kiválasztani . $v$

Példa az algoritmus működésére

Legyen adott egy gráf . Ebben az esetben az algoritmus a következőképpen fut: $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 )}$

lépés	$v$	$A(a)$	$A(b)$	$A(c)$	$Hirdetés)$	$A(e)$	$P$
0	$-$	$\varnothing$	$a$	$a$	$ABC$	$a,c,d$	$\varnothing$
egy	$a$	$\varnothing$	$\varnothing$	$\varnothing$	$időszámításunk előtt$	$c, d$	$a$
2	$c$	$\varnothing$	$\varnothing$	$\varnothing$	$b$	$d$	$a,c$
3	$b$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$d$	$a,c,b$
négy	$d$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a,c,b,d$
5	$e$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$a,c,b,d,e$

A második lépésben a csúcs helyett választható , mivel a és közötti sorrend nincs megadva. $c$ $b$ $b$ $c$

Tarján algoritmusa ( 1976)

Számítógépen a topológiai rendezés O( n ) időben és memóriában végezhető úgy, hogy az összes csúcsot bejárjuk mélységi kereséssel , és kiadjuk a csúcsokat a kilépési ponton.

Más szavakkal, az algoritmus a következő:

Kezdetben minden csúcs fehér.
Minden csúcshoz elkészítjük az algoritmus egy lépését.

Az algoritmus lépése:

Ha a csúcs fekete, semmit sem kell tenni.
Ha a csúcs szürke, akkor ciklus található, a topológiai rendezés nem lehetséges.
Ha a teteje fehér
- Fesd szürkére
- Az algoritmus lépését minden áramból elérhető csúcsra alkalmazzuk
- Színezd ki a csúcsot feketére, és helyezd a végső lista elejére.

Példa

A példa ugyanazon a gráfon lesz, de a kikerülendő csúcsok kiválasztásának sorrendje: c, d, e, a, b.

Lépés	Jelenlegi	fehér	Stack (szürke)	Kilépés (fekete)
0	—	a, b, c, d, e	—	—
egy	c	a, b, d, e	c	—
2	d	a, b, e	c, d	—
3	e	a, b	c, d, e	—
négy	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
nyolc	e	a, b	—	c, d, e
9	a	b	a	c, d, e
tíz	b	—	a, b	c, d, e
tizenegy	a	—	a	b, c, d, e
12	—	—	—	a, b, c, d, e
13	b	—	—	a, b, c, d, e

Alkalmazás

A topológiai rendezés segítségével a műveletek helyes sorrendje épül fel, amelyek mindegyike függhet egymástól: a hallgatók tanfolyamok teljesítésének sorrendje, programok telepítése a csomagkezelő segítségével , programforráskódok létrehozása a Makefiles segítségével .

Lehetőség van objektumok megjelenítési listájának felépítésére izometrikus vetületben az objektumok közötti páros ordinális relációk ismeretében (a két objektum közül melyiket kell először megrajzolni).

Lásd még

Demucron algoritmusa

Linkek

Irodalom

Levitin A. V. Fejezet 5. Problémaméret-csökkentési módszer: Topológiai rendezés // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 220-224. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 22.4. fejezet. Topológiai rendezés // Algoritmusok: szerkesztés és elemzés = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - S. 632-635. — ISBN 5-8459-0857-4 .

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú