Renditja topologjike renditet në mënyrë lineare kulmet e një DAG-u (grafik i drejtuar aciklik) në mënyrë që çdo brinjë u->v të ketë u para v. Përgjigjet pyetjes "në çfarë rendi mund të bëj këto detyra duke pasur parasysh varësitë e tyre?"
Dy qasje të zakonshme: (hiqni në mënyrë të përsëritur kulmet me in-degree 0) ose (post-order i kundërt). Një renditje e vlefshme ekziston .
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']
Përdorni për sistemet e ndërtimit, planifikimin e detyrave, përfaqësimet pararendëse të kurseve dhe zgjidhjen e varësive. Nëse rezultati është më i shkurtër se V, grafiku ka një cikël (nuk ka renditje të vlefshme). Renditja në përgjithësi nuk është unike.
Rrenditja e varësive është kudo — përpiluesit, menaxherët e paketave, rillogaritja e spreadsheet-it, CI pipelines.
Renditja topologjike vepron gjithashtu si zbulim ciklesh për grafet e drejtuar.
Theksimi i një problemi si "rend nën kufizime" dhe arritja për topo sort është një sinjal i fortë për këshilltar të lartë.