Topologinen lajittelu

Topologinen lajittelu on ääriviivattoman suunnatun graafin kärkien järjestystä sen kärkijoukossa olevan digraafin reunojen antaman osittaisen järjestyksen mukaan .

Esimerkki

Countille $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 )}$

sen kärkipisteistä on useita johdonmukaisia sekvenssejä, jotka voidaan saada topologisella lajittelulla, esimerkiksi:

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

Voidaan nähdä, että mitkä tahansa kaksi vierekkäistä kärkeä, jotka eivät sisälly osittaisjärjestyssuhteeseen, voidaan permutoida sekvenssissä . $E$

Kahnin algoritmi (1962)

Yksi ensimmäisistä algoritmeista ja sopivin manuaaliseen suorittamiseen.

Olkoon ääriviivaton orientoitu yksinkertainen graafi . Merkitään joukko pisteitä siten, että . Eli joukko kaikkia pisteitä , joista on kaari kärkeen . Antaa olla haluttu kärkijono. $G=(V,E)$ $A(v),v\in V$ $u\in V$ $\exists ~(u,v)\in E$ $A(v)$ $v$ $P$

Valitse toistaiseksi mikä tahansa huippupiste ja poista se kaikista

|P|<|V|

v

A(v)=\varnothing

v\notin P

P\saa P,v

v

A(u),u\neq v

Vähintään yhden ääriviivan läsnäolo graafissa johtaa siihen, että syklin tietyllä iteraatiolla ei ole mahdollista valita uutta kärkeä . $v$

Esimerkki algoritmin toiminnasta

Olkoon kuvaaja annettu . Tässä tapauksessa algoritmi toimii seuraavasti: $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 )}$

askel	$v$	$A(a)$	$A(b)$	$A(c)$	$Ilmoitus)$	$A(e)$	$P$
0	$-$	$\varno mitään$	$a$	$a$	$a,b,c$	$a,c,d$	$\varno mitään$
yksi	$a$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$b,c$	$c, d$	$a$
2	$c$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$b$	$d$	$a,c$
3	$b$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$d$	$a,c,b$
neljä	$d$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$a,c,b,d$
5	$e$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$\varno mitään$	$a,c,b,d,e$

Toisessa vaiheessa kärki voidaan valita sijasta , koska järjestystä ja välillä ei ole määritetty. $c$ $b$ $b$ $c$

Tarjanin algoritmi ( 1976)

Tietokoneella topologinen lajittelu voidaan tehdä O( n ) ajassa ja muistissa läpikäymällä kaikki kärjet käyttämällä syvyyshakua ja tulostamalla kärjet poistumispisteessä.

Toisin sanoen algoritmi on seuraava:

Aluksi kaikki kärjet ovat valkoisia.
Jokaiselle kärjelle teemme algoritmin askeleen.

Algoritmin vaihe:

Jos kärkipiste on musta, mitään ei tarvitse tehdä.
Jos kärki on harmaa, sykli löytyy, topologinen lajittelu ei ole mahdollista.
Jos yläosa on valkoinen
- Maalaa se harmaaksi
- Sovellamme algoritmin askelta kaikkiin virrasta saavutettaviin pisteisiin
- Väritä kärkipiste mustaksi ja aseta se lopullisen luettelon alkuun.

Esimerkki

Esimerkki on samassa graafissa, mutta järjestys, jossa valitsemme ohitettavat kärjet, on c, d, e, a, b.

Vaihe	Nykyinen	Valkoinen	Pino (harmaa)	Poistu (musta)
0	—	a, b, c, d, e	—	—
yksi	c	a, b, d, e	c	—
2	d	a, b, e	c, d	—
3	e	a, b	c, d, e	—
neljä	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
kahdeksan	e	a, b	—	c, d, e
9	a	b	a	c, d, e
kymmenen	b	—	a, b	c, d, e
yksitoista	a	—	a	b, c, d, e
12	—	—	—	a, b, c, d, e
13	b	—	—	a, b, c, d, e

Sovellus

Topologisen lajittelun avulla rakennetaan oikea toimintosarja, joista jokainen voi riippua toisistaan: opiskelijoiden suorittamien koulutuskurssien järjestys, ohjelmien asennus paketinhallinnan avulla , ohjelmien lähdekoodien rakentaminen Makefilesin avulla .

On mahdollista rakentaa näyttölista kohteista isometriseen projektioon , kun tiedetään objektien väliset järjestyssuhteet (kumpi näistä kahdesta objektista tulee piirtää ensin).

Katso myös

Demucronin algoritmi

Linkit

Kirjallisuus

Levitin A. V. Luku 5. Ongelman koon pienennysmenetelmä: Topologinen lajittelu // Algoritmit. Johdatus kehitykseen ja analyysiin - M .: Williams , 2006. - S. 220-224. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Luku 22.4. Topologinen lajittelu // Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Toim. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - S. 632-635. — ISBN 5-8459-0857-4 .

Lajittelualgoritmit
Teoria	Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto	kupla Sekoitetaan Kääpiöt Nopeasti Kampa Lajittelu parillinen-pariton Bitittain
Valinta	Valinta Pyramidin muotoinen Sileä
insertit	insertit shella puu
fuusio	fuusio
Ei vertailuja	Laskenta lohko
hybridi	introsort Timsort
Muut	Topologinen verkkoja bitonia
epäkäytännöllistä	Bogosort Stooge lajittelu pannukakku hidas