Topological sort porządkuje liniowo wierzchołki DAG (directed acyclic graph) tak, aby dla każdej krawędzi u->v wierzchołek u był przed v. Odpowiada na pytanie "w jakiej kolejności mogę wykonać te zadania biorąc pod uwagę ich zależności?"
Dwa popularne podejścia: (wielokrotnie usuwaj węzły ze stopniem wejściowym 0) lub (reverse post-order). Prawidłowe porządkowanie istnieje .
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']
Używaj do systemów budowania, planowania zadań, wymagań wstępnych do kursów i rozwiązywania zależności. Jeśli wynik jest krótszy niż V, graf ma cykl (brak prawidłowego porządku). Porządkowanie generalnie nie jest unikalne.
Porządkowanie zależności jest wszędzie — kompilatory, menedżery pakietów, przeliczanie arkuszy kalkulacyjnych, potoki CI.
Sortowanie topologiczne pełni również rolę detekcji cyklu dla grafów skierowanych.
Rozpoznanie problemu jako "porządkowanie pod ograniczeniami" i sięgnięcie po sortowanie topologiczne to mocny sygnał seniora.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj