Topologinen lajittelu

Tähän artikkeliin tai sen osaan on merkitty lähteitä, mutta niihin ei viitata.
Älä poista mallinetta ennen kuin viitteet on lisätty. Voit auttaa Wikipediaa lisäämällä artikkelille asianmukaisia viitteitä. Lähteettömät tiedot voidaan kyseenalaistaa tai poistaa.

Topologinen lajittelu (engl. topological sorting) 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.

Ohjelmakirjastojen riippuvuuksia esittävä suunnattu asyklinen graafi. Solmut ovat topologisesti lajiteltuna: Glib, ATK, GTK, OpenGL. (Ei ainoa ratkaisu.)

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

Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: ”23.4 Topological sort”, Introduction to Algorithms – 2nd ed. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7.