A topológiai rendezés egy DAG (irányított aciklusos gráf) csúcsait lineárisan rendezi úgy, hogy minden u->v él u előtt v-t tartalmazzon. Arra a kérdésre válaszol: "milyen sorrendben tudom elvégezni ezeket a feladatokat a függőségek figyelembevételével?"
Két gyakori megközelítés: (ismételten eltávolítani az in-degree 0-val rendelkező csomópontokat) vagy (fordított utórendben). Érvényes sorrend .
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']
Használja fordítási rendszerekhez, feladat-ütemezéshez, tantárgy-előfeltételekhez és függőség-feloldáshoz. Ha az eredmény rövidebb, mint V, akkor a gráfnak van egy ciklusa (nincs érvényes sorrend). A sorrend általában nem egyedi.
A függőségi sorrend mindenütt jelen van — fordítók, csomagkezelők, táblázatszámítási újraszámítás, CI cső.
A topológiai rendezés a ciklus-detektálásra is szolgál az irányított gráfokra.
A problémát "megkötések alatti rendezésként" felismerni és a topológiai rendezéshez fordulni az erős senior jel.