Topološko sortiranje linearno uredi vozlišča DAG-a (usmerjenega aciklličnega grafa) tako, da ima vsak rob u->v u pred v. Odgovori na vprašanje "v kakšnem vrstnem redu lahko opravim te naloge glede na njihove odvisnosti?"
Dva pogosta pristopa: (ponavljajoče odstranjevanje vozlišč z vhodno stopnjo 0) ali (obratni post-order). Veljaven vrstni red obstaja .
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']
Uporabite za sisteme gradnje, razporejanje nalog, predpogoje predmetov in razreševanje odvisnosti. Če je rezultat krajši od V, ima graf cikel (ni veljavnega reda). Vrstni red na splošno ni enoten.
Urejevanje odvisnosti je povsod — prevajalniki, upravljalniki paketov, ponovno izračunavanje preglednic, CI cevovodi.
Topološko sortiranje hkrati služi kot odkrivanje ciklov za usmerjena grafa.
Prepoznavanje problema kot "urejanja pod pogoji" in seganje po topološkem sortiranju je močan signal za starejšega programerja.
Knjižnica IT vprašanj za razgovore s podrobnimi odgovori — od začetnika do izkušenega.
Doniraj