Urutan topologis

Urutan topologis (topological sorting) menyusun simpul graf berarah sehingga setiap tepi mengarah ke depan, dan bentuk masalah paling terkenalnya adalah jadwal mata kuliah yang penuh prasyarat. Topik ini mendefinisikan DAG, membangun algoritma Kahn dari derajat masuk dan antrian, memakai sisa simpulnya sebagai detektor siklus, lalu memetakan semuanya ke keluarga soal jadwal. Graf prasyaratnya kecil dan tetap, sehingga setiap langkah antriannya dapat diikuti dengan tangan.

DAG dan arti urutan topologis#

DAG (directed acyclic graph) adalah graf berarah tanpa siklus, dan hanya graf seperti ini yang dijamin memiliki urutan topologis. Sebuah urutan disebut topologis bila untuk setiap tepi u menuju v, simpul u selalu muncul sebelum v dalam urutan itu. Tepi pada jadwal kuliah berarti u adalah prasyarat v, sehingga urutan topologis adalah jadwal yang sah. Satu DAG boleh memiliki lebih dari satu urutan sah, karena simpul-simpul yang tidak terhubung jalur mana pun bebas saling ditukar posisinya.

Graf contohnya berisi enam mata kuliah berlabel 0 sampai 5 dengan tepi (0, 4), (1, 4), (2, 5), (4, 3), dan (5, 3). Mata kuliah 3 menjadi penutup yang menunggu 4 dan 5, sedangkan 0, 1, dan 2 bebas diambil lebih awal. Bila tepi (3, 1) ditambahkan, siklus terbentuk dan tidak ada jadwal sah mana pun. Inilah kasus yang dideteksi di bagian berikutnya.

Algoritma Kahn dengan derajat masuk#

Algoritma Kahn menghitung derajat masuk (indegree), yaitu banyaknya tepi yang menuju setiap simpul. Simpul berderajat masuk nol tidak menunggu apa pun sehingga boleh langsung masuk antrian siap. Setiap kali satu simpul dikeluarkan dan dipasang di urutan, seluruh tepi keluarnya dicabut, yang berarti derajat masuk tetangganya berkurang satu. Tetangga yang derajatnya mencapai nol bergabung ke antrian, dan proses berjalan sampai antrian habis.

Diagram berikut menggambarkan DAG jadwal contoh beserta salah satu urutan Kahn-nya. Urutan 0, 1, 2, 4, 5, 3 sah karena setiap panah mengarah ke depan, sedangkan urutan lain seperti menukar posisi 0 dan 1 sama sahnya. Yang dituntut algoritma hanyalah satu urutan sah, bukan urutan tertentu.

Demo Kahn pada jadwal mata kuliah#

Berkas berikut membangun derajat masuk dan adjacency list dari daftar tepi, menjalankan Kahn dengan heap, lalu mengulangnya setelah tepi (3, 1) ditambahkan. Baris sisa simpul yang dicetak pada tiap percobaan menjadi kunci deteksi siklus yang dibahas berikutnya. Kedua percobaan memanggil fungsi yang sama, sehingga jalur logikanya identik.

# Algoritma Kahn: urutan topologis dari daftar prasyarat mata kuliah.
import heapq

# Tepi u -> v berarti mata kuliah u wajib diambil sebelum mata kuliah v.
tepi = [(0, 4), (1, 4), (2, 5), (4, 3), (5, 3)]
n = 6

def kahn(daftar_tepi):
    tetangga = [[] for _ in range(n)]
    derajat_masuk = [0] * n
    for u, v in daftar_tepi:
        tetangga[u].append(v)
        derajat_masuk[v] += 1
    # simpul tanpa prasyarat masuk heap, selalu diambil kode terkecil
    siap = [v for v in range(n) if derajat_masuk[v] == 0]
    heapq.heapify(siap)
    urutan = []
    while siap:
        simpul = heapq.heappop(siap)
        urutan.append(simpul)
        for t in tetangga[simpul]:
            derajat_masuk[t] -= 1
            if derajat_masuk[t] == 0:
                heapq.heappush(siap, t)
    return urutan

urutan = kahn(tepi)
print("Urutan topologis  :", urutan)
print("Sisa tak terproses:", n - len(urutan))

# Tepi (3, 1) menutup siklus 1 -> 4 -> 3 -> 1, sehingga urutan tidak ada.
urutan_siklus = kahn(tepi + [(3, 1)])
print("Dengan tepi (3,1) :", urutan_siklus)
print("Sisa tak terproses:", n - len(urutan_siklus))

Urutan topologis  : [0, 1, 2, 4, 5, 3]
Sisa tak terproses: 0
Dengan tepi (3,1) : [0, 2, 5]
Sisa tak terproses: 3

Percobaan pertama mengeluarkan urutan lengkap enam simpul dengan nol sisa, tanda DAG yang sehat. Percobaan kedua berhenti di 0, 2, 5 dan meninggalkan tiga simpul tak terproses, persis simpul-simpul yang terjerat siklus 1, 4, 3. Tidak ada pesan error yang muncul pada kasus kedua, sehingga pemeriksaan sisa inilah satu-satunya cara mengetahui bahwa jadwalnya gagal.

Deteksi siklus dari sisa simpul#

Kahn berhenti sebelum selesai bila ada siklus, karena simpul di dalam siklus tidak pernah kehabisan tepi masuk yang belum dicabut. Banyaknya simpul yang terpasang di urutan karenanya menjadi penguji kebenaran yang murah, cukup dibandingkan dengan banyaknya simpul semula. Bila keduanya sama, urutan sahnya ada, dan bila lebih kecil, sisanya adalah anggota siklus beserta simpul yang berada di hilirnya. Pada demo di atas, sisa tiga simpul tersebut langsung membuktikan bahwa jadwal kedua mustahil dibuat.

Keluarga soal jadwal memakai pola persis ini. Versi dasarnya menanyakan keberadaan jadwal, yang dijawab dengan membandingkan panjang urutan terhadap jumlah kuliah. Versi lanjutannya meminta urutannya sendiri, yang dijawab dengan mengembalikan hasil Kahn saat sisa nol dan sinyal kegagalan bila tidak.

Varian DFS dan keluarga soal#

Kahn bukan satu-satunya jalan, karena DFS juga menghasilkan urutan topologis. Simpul yang pemrosesannya selesai paling akhir harus diletakkan paling depan, sehingga urutannya adalah balikan urutan penyelesaian DFS. Versi ini menuntut deteksi siklus tersendiri lewat penanda tiga keadaan, yaitu belum dikunjungi, sedang diproses, dan sudah selesai. Kahn dipilih sebagai demo utama karena deteksi siklusnya gratis, cukup dari sisa simpul.

Kompleksitas kedua varian sama, yaitu $O(V + E)$, karena setiap simpul dan tepi hanya disentuh beberapa kali dengan jumlah yang konstan. Untuk keluarga soal jadwal, kerangka Kahn memberikan tiga jawaban siap pakai, yaitu ada tidaknya jadwal, isi jadwalnya, dan himpunan simpul yang terjerat siklus. Ketiganya berbagi satu implementasi dengan sedikit penyesuaian pada keluarannya.

Kesalahan umum#

Kesalahan ini ditularkan dari kebiasaan graf tak berarah yang memang menambahkan dua arah. Aturannya tegas, yaitu arah balik hanya ditambahkan bila hubungannya memang simetris, sedangkan prasyarat, ketergantungan, dan hierarki tidak pernah simetris. Gejalanya khas, yaitu Kahn berhenti dengan sisa simpul pada graf yang terlihat jelas berbentuk DAG. Bila urutan keluarannya juga terasa terbalik, periksa arah tepinya sebelum mencurigai algoritmanya.

Ringkasan#

• Urutan topologis hanya ada pada DAG, dan setiap tepi u menuju v harus mengarah ke depan dalam urutan itu.
• Algoritma Kahn memakai derajat masuk dan antrian, berbiaya $O(V + E)$, dan menghasilkan satu urutan sah.
• Selisih banyaknya simpul terpasang terhadap jumlah simpul semula mendeteksi siklus tanpa kode tambahan.
• Keluarga soal jadwal mata kuliah dijawab dengan Kahn, mulai dari keberadaan jadwal sampai isi urutannya.

Referensi#

• Topological sorting — Wikipedia — Definisi urutan topologis dan langkah algoritma Kahn.
• Directed acyclic graph — Wikipedia — Sifat DAG dan kaitannya dengan pengurutan topologis.