Topological sort tiesiniu būdu išdėsto DAG (directed acyclic graph) viršūnes taip, kad kiekvienas šaltinis u->v turėtų u prieš v. Tai atsakyti į klausimą "kokia tvarka galiu atlikti šias užduotis atsižvelgiant į jų priklausomybes?"
Du bendri požiūriai: (pakartotinai pašalinti mazgus su įėjimo laipsniu 0) arba (reverse post-order). Galiojantis išdėstymas egzistuoja .
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']
Naudokite build systems, užduočių planavimą, kurso reikalavimus ir priklausomybės sprendimą. Jei rezultatas trumpesnis nei V, grafikas turi ciklą (nėra galiojančios tvarkos). Išdėstymas paprastai nėra unikalus.
Priklausomybės tvarka yra visur — kompiliatoriai, paketų valdikliai, skaičiuoklės perskaičiavimas, CI kanallai.
Topological sort taip pat naudojamas ciklo aptikimui nukreiptuose grafikuose.
Problemos atpažinimas kaip "tvarka esant apribojimams" ir topologinio rūšiavimo naudojimas yra stiprus vyresnio lygio signalas.
IT pokalbių klausimų biblioteka su išsamiais atsakymais — nuo Junior iki Senior.
Paaukoti