Topological sort ordonează liniar vârfurile unui DAG (directed acyclic graph) astfel încât fiecare muchie u->v să aibă u înainte de v. Raspunde la întrebarea "în ce ordine pot executa aceste sarcini ținând cont de dependențele lor?"
Două abordări comune: (elimina în mod repetat noduri cu grad de intrare 0) sau (reverse post-order). O ordonare validă există .
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']
Foloseşte pentru sisteme de compilare, planificarea sarcinilor, condiții prealabile de curs și rezolvarea dependențelor. Dacă rezultatul este mai scurt decât V, graficul are un ciclu (nicio ordine validă). Ordonarea nu este în general unică.
Ordonarea dependențelor se găsește peste tot — compilatoare, manageri de pachete, recalculare de foi de calcul, conducte CI.
Sortarea topologică funcționează și ca detecție de ciclu pentru graficele direcționate.
A recunoaște o problemă ca "ordonare sub constrângeri" și a recurge la sortarea topologică este un semnal puternic de seniori.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează