Topolojik sıralama, DAG (yönlendirilmiş döngüsüz grafik) in köşelerini doğrusal bir şekilde sıralar, böylece her u->v kenarı u'yu v'den önce yerleştirir. "Bağımlılıkları göz önünde bulundurarak bu görevleri hangi sırayla yapabilirim?" sorusunu yanıtlar.
İki yaygın yaklaşım: (giriş derecesi 0 olan düğümleri tekrar tekrar kaldır) veya (ters post-sırası). Geçerli bir sıralama var olur.
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']
Derleme sistemleri, görev planlama, ders ön koşulları ve bağımlılık çözümleme için kullanın. Sonuç V'den daha kısa ise, grafın döngüsü vardır (geçerli sıra yoktur). Sıralama genellikle benzersiz değildir.
Bağımlılık sıralaması her yerde var — derleyiciler, paket yöneticileri, elektronik tablo yeniden hesaplama, CI boru hatları.
Topolojik sıralama aynı zamanda yönlendirilmiş grafikler için döngü algılaması olarak çalışır.
Bir sorunu "kısıtlamalar altında sıra" olarak tanımak ve topo sıralamaya yönelmek kıdemli bir sinyal.