Penjelasan topological sort: cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan topological sort

Banyak tugas nyata punya prasyarat: mata kuliah membutuhkan mata kuliah sebelumnya, file sumber harus dikompilasi setelah file yang di-import-nya, paket harus diinstal setelah dependensinya, sel spreadsheet harus dihitung setelah sel yang dirujuknya. Gambarkan setiap tugas sebagai node dan setiap aturan "harus lebih dulu" sebagai edge berarah. Urutan topologis adalah setiap rangkaian tugas yang memenuhi semua edge.

Urutan hanya ada jika dan hanya jika graf tidak memiliki siklus berarah. Jika A membutuhkan B dan B membutuhkan A, tidak ada urutan yang valid, dan topological sort yang baik melaporkannya alih-alih berputar tanpa henti. Sebuah DAG biasanya punya banyak urutan valid; algoritma mengembalikan salah satunya.

Ide dasar dengan kata-kata sederhana

Algoritma Kahn (diterbitkan oleh Arthur Kahn pada 1962) bekerja dari depan:

1. Hitung edge masuk (in-degree) setiap node.
2. Masukkan setiap node dengan in-degree 0 ke queue: tugas-tugas ini tidak punya prasyarat yang belum terpenuhi.
3. Ambil sebuah node dari queue dan tambahkan ke hasil. Untuk setiap edge keluarnya, kurangi in-degree targetnya sebesar 1; jika mencapai 0, tambahkan target ke queue.
4. Ketika queue kosong, jika hasil berisi semua node, itulah urutan topologis. Jika tidak, node yang tersisa merupakan bagian dari siklus.

Metode DFS bekerja dari belakang: sebuah node selesai hanya setelah semua yang ditunjuknya selesai, sehingga mendaftar node dalam urutan selesai terbalik menempatkan setiap node sebelum semua penerusnya.

Contoh langkah demi langkah

Berpakaian: underwear → pants, pants → shoes, socks → shoes, pants → belt, shirt → belt, shirt → tie, tie → jacket, belt → jacket. Algoritma Kahn, mengambil node dalam queue dengan urutan first-in, first-out:

Urutan akhir: underwear, socks, shirt, pants, tie, shoes, belt, jacket. Ke-8 node sudah ditempatkan, jadi tidak ada siklus.

Implementasi Python

Algoritma Kahn dengan deque:

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

Versi DFS menambahkan node setelah semua penerusnya selesai, lalu membalik list:

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

Kedua hasil valid. Sejak Python 3.9, pustaka standar juga memiliki graphlib.TopologicalSorter. Perhatikan bahwa ia menerima pemetaan dari setiap node ke para pendahulunya, arah yang berlawanan dengan dictionary di atas:

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

Kompleksitas waktu dan ruang

Varian dan kesalahan umum

• Urutan terkecil lebih dulu: ganti queue dengan min-heap (heapq) agar selalu memilih node tersedia yang terkecil. Ini menghasilkan urutan terkecil secara leksikografis dalam O((V + E) log V).
• Penjadwalan paralel: jalankan algoritma Kahn per putaran, mengambil semua node ber-in-degree 0 sekaligus. Setiap putaran adalah satu batch tugas yang dapat berjalan bersamaan; jumlah putaran sama dengan panjang rantai dependensi terpanjang. graphlib.TopologicalSorter mendukung ini lewat get_ready() dan done().
• Jalur terpanjang atau terpendek pada DAG: relaksasi edge menurut urutan topologis untuk mendapatkan jawaban dalam O(V + E), bahkan dengan bobot negatif.
• Menghitung jumlah urutan yang berbeda adalah masalah yang jauh lebih sulit; jangan mencoba mendaftar semuanya untuk graf besar.

Versi DFS rekursif memiliki masalah batas rekursi yang sama seperti DFS rekursif lainnya di Python: untuk rantai ribuan node, gunakan algoritma Kahn.

Kapan memakainya dan penggunaannya di dunia nyata

• Build tool seperti Make mengurutkan target berdasarkan dependensinya, dan package manager mengurutkan instalasi berdasarkan graf dependensi.
• Spreadsheet menghitung ulang sel menurut urutan dependensi dan melaporkan referensi melingkar.
• Task scheduler dan workflow engine, misalnya pipeline data berbasis DAG, menjalankan tugas dalam urutan topologis.
• Compiler mengurutkan deklarasi dan mengevaluasi graf ekspresi; database mengurutkan pembuatan atau penghapusan foreign key.
• Soal wawancara: course schedule I dan II, alien dictionary (urutan huruf dari kata-kata terurut), parallel courses, tinggi minimum rencana build.