Topologinen lajittelu

Topologinen lajittelu () tarkoittaa tietojenkäsittelytieteessä tapaa järjestää suunnatun syklittömän verkon (DAG) solmut jonoksi. Jos graafi kuvaa riippuvuuksia, niin topologisessa järjestyksessä solmun riippuvuudet tulevat aina ennen itse solmua.

Algoritmi 
Hyvä ja helppo algoritmi topologiseen lajitteluun käyttää hyväkseen syvyyssuuntaista läpikäyntiä: aina kun solmu on käyty kokonaan läpi, se lisätään listan ensimmäiseksi. Tuloksena on topologisesti lajiteltu lista.

Algoritmin asymptoottinen suoritusaika on O(n).

Lähteet 

Algoritmit