Topological sort menyusun secara linear bucu-bucu DAG (directed acyclic graph) sehingga setiap tepi u->v memiliki u sebelum v. Ia menjawab "dalam urutan apakah saya dapat melakukan tugas-tugas ini mengingat kebergantungannya?"
Dua pendekatan umum: (keluarkan berulang kali nod dengan in-degree 0) atau (reverse post-order). Urutan yang sah wujud .
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, penjadualan tugas, prasyarat kursus, dan penyelesaian kebergantungan. Jika hasilnya lebih pendek daripada V, graf mempunyai kitaran (tiada urutan sah). Urutannya pada amnya bukan unik.
Pengurutan kebergantungan terdapat di mana-mana — pengkompil, pengurus pakej, pengiraan semula hamparan, saluran CI.
Topological sort juga berfungsi sebagai pengesanan kitaran untuk graf terarah.
Mengiktiraf masalah sebagai "pesanan di bawah kekangan" dan menggunakan topo sort adalah isyarat senior yang kuat.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma