Topological sort mengurutkan secara linear simpul dari DAG (directed acyclic graph) sehingga setiap sisi u->v memiliki u sebelum v. Ini menjawab pertanyaan "dalam urutan apa saya dapat melakukan tugas-tugas ini mengingat ketergantungannya?"
Dua pendekatan umum: (berulang kali menghapus simpul dengan in-degree 0) atau (post-order terbalik). Urutan yang valid ada .
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']
Gunakan untuk build systems, penjadwalan tugas, prasyarat kursus, dan resolusi ketergantungan. Jika hasilnya lebih pendek dari V, grafik memiliki siklus (tidak ada urutan yang valid). Urutannya umumnya tidak unik.
Pengurutan ketergantungan ada di mana-mana — compiler, manajer paket, perhitungan ulang spreadsheet, pipeline CI.
Topological sort juga berfungsi sebagai deteksi siklus untuk grafik berarah.
Mengenali masalah sebagai "urutan di bawah batasan" dan mencapai topological sort adalah sinyal senior yang kuat.