Topologické řazení

Topologické třídění je řazení vrcholů bezkonturového orientovaného grafu podle dílčího řádu daného hranami digrafu na množině jeho vrcholů.

Příklad

Pro hraběte $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 )}$

existuje několik konzistentních sekvencí jeho vrcholů, které lze získat pomocí topologického řazení, například:

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

Je vidět, že libovolné dva sousední vrcholy, které nejsou zahrnuty ve vztahu částečného řádu, mohou být v posloupnosti permutovány . $E$

Kahnův algoritmus (1962)

Jeden z prvních algoritmů a nejvhodnější pro ruční provádění.

Nechť je dán bezkonturový orientovaný jednoduchý graf . Označme množinou vrcholů tak, že . Tedy množina všech vrcholů, ze kterých vede oblouk k vrcholu . Nechť je požadovaná posloupnost vrcholů. $G=(V,E)$ $A(v),v\in V$ $u\in V$ $\exists ~(u,v)\in E$ $A(v)$ $proti$ $P$

pro tuto chvíli vyberte libovolný vrchol a odstraňte ze všech

|P|<|V|

proti

A(v)=\varnonic

v\notin P

P\gets P,v

proti

A(u),u\neq v

Přítomnost alespoň jedné kontury v grafu povede k tomu, že při určité iteraci cyklu nebude možné vybrat nový vrchol . $proti$

Příklad toho, jak algoritmus funguje

Nechť je uveden graf . V tomto případě bude algoritmus probíhat následovně: $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 )}$

krok	$proti$	$A(a)$	$A(b)$	$A(c)$	$Inzerát)$	$A(e)$	$P$
0	$-$	$\varno nic$	$A$	$A$	$a,b,c$	$a,c,d$	$\varno nic$
jeden	$A$	$\varno nic$	$\varno nic$	$\varno nic$	$před naším letopočtem$	$c, d$	$A$
2	$C$	$\varno nic$	$\varno nic$	$\varno nic$	$b$	$d$	$a,c$
3	$b$	$\varno nic$	$\varno nic$	$\varno nic$	$\varno nic$	$d$	$a,c,b$
čtyři	$d$	$\varno nic$	$\varno nic$	$\varno nic$	$\varno nic$	$\varno nic$	$a,c,b,d$
5	$E$	$\varno nic$	$\varno nic$	$\varno nic$	$\varno nic$	$\varno nic$	$a,c,b,d,e$

Ve druhém kroku lze zvolit vrchol místo , protože pořadí mezi a není určeno. $C$ $b$ $b$ $C$

Tarjanův algoritmus ( 1976)

Na počítači lze topologické řazení provést v čase a paměti O( n ) procházením všech vrcholů pomocí vyhledávání do hloubky a výstupem vrcholů na výstupním bodě.

Jinými slovy, algoritmus je následující:

Zpočátku jsou všechny vrcholy bílé.
Pro každý vrchol uděláme krok algoritmu.

Krok algoritmu:

Pokud je vrchol černý, není třeba nic dělat.
Pokud je vrchol šedý, je nalezen cyklus, topologické řazení není možné.
Pokud je vršek bílý
- Natřete to šedou barvou
- Krok algoritmu aplikujeme na všechny vrcholy, které lze dosáhnout z proudu
- Vybarvěte vrchol černě a umístěte jej na začátek konečného seznamu.

Příklad

Příklad bude na stejném grafu, ale pořadí, ve kterém vybíráme vrcholy, které se mají obejít, je c, d, e, a, b.

Krok	Proud	Bílý	Zásobník (šedá)	Odejít (černá)
0	—	a, b, c, d, e	—	—
jeden	C	a, b, d, e	C	—
2	d	a, b, e	c, d	—
3	E	a, b	c, d, e	—
čtyři	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
osm	E	a, b	—	c, d, e
9	A	b	A	c, d, e
deset	b	—	a, b	c, d, e
jedenáct	A	—	A	b, c, d, e
12	—	—	—	a, b, c, d, e
13	b	—	—	a, b, c, d, e

Aplikace

Pomocí topologického třídění je sestavena správná posloupnost akcí, z nichž každá může záviset na druhé: posloupnost absolvování školení studenty, instalace programů pomocí správce balíčků , vytváření zdrojových kódů programů pomocí Makefiles .

Je možné sestavit seznam zobrazení objektů v izometrické projekci se znalostí párových ordinálních vztahů mezi objekty (který z těchto dvou objektů by měl být nakreslen jako první).

Viz také

Demucronův algoritmus

Odkazy

Literatura

Levitin A. V. Kapitola 5. Metoda redukce velikosti problému: Topologické třídění // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 220-224. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitola 22.4. Topologické řazení // Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M .: Williams, 2005. - S. 632-635. — ISBN 5-8459-0857-4 .

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý