Topologinen järjestäminen järjestää DAG:n (suunnattu syklitön grafi) pisteet lineaarisesti niin, että jokaiselle reunalle u->v pätee u ennen v:tä. Se vastaa kysymykseen "missä järjestyksessä voin suorittaa nämä tehtävät niiden riippuvuuksien perusteella?"
Kaksi tavallista lähestymistapaa: (toista poista pisteet, joiden sisääntuloaste on 0) tai (käänteinen post-järjestys). Kelvollinen järjestys on olemassa .
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
Käytä järjestelmän kääntämiseen, tehtävien ajoitukseen, kurssien esitietovaatimuksiin ja riippuvuuksien ratkaisuun. Jos tulos on lyhyempi kuin V, graafissa on sykli (kelvollista järjestystä ei ole). Järjestys ei yleensä ole yksikäsitteinen.
Riippuvuuksien järjestäminen on kaikkialla — kääntäjissä, paketinhallinnassa, taulukkolaskentajen uudelleenlaskennassa, CI-putkissa.
Topologinen järjestäminen toimii myös syklintunnistuksena suuntautuneille graafeille.
Ongelman tunnistaminen "järjestämiseksi rajoituksien alaisena" ja topologisen järjestämisen käyttö on vahva senioriteetin merkki.