Pengurutan topologis

Setiap kali Anda memasang perangkat lunak, mem-build program, atau merencanakan proyek, sesuatu harus menentukan apa yang dikerjakan lebih dulu. Jika tugas B membutuhkan tugas A, A harus lebih awal. Pengurutan topologis mengubah jaringan aturan seperti itu menjadi satu garis lurus.

Graf berisi simpul yang dihubungkan panah satu arah, simpul yang sudah ditempatkan berwarna hijau, dan urutan sejauh ini digambar sebagai baris di bawahnya
Graf berisi simpul yang dihubungkan panah satu arah, simpul yang sudah ditempatkan berwarna hijau, dan urutan sejauh ini digambar sebagai baris di bawahnya

Idenya

Gambar setiap tugas sebagai simpul dan setiap aturan "A sebelum B" sebagai panah dari A ke B. Urutan topologis adalah baris berisi semua simpul di mana setiap panah mengarah ke kanan. Disebut pengurutan karena menyusun sesuatu secara berurutan, tetapi tidak seperti mengurutkan angka, ia hanya perlu mematuhi panah: simpul yang tidak dihubungkan rantai panah boleh datang dalam urutan mana pun.

Kapan mustahil

Jika panah membentuk siklus, misalnya A sebelum B, B sebelum C, dan C sebelum A, maka A harus datang sebelum dirinya sendiri. Jadi urutan topologis ada tepat ketika graf tidak punya siklus berarah. Graf seperti itu disebut graf asiklik berarah, atau DAG. Kedua metode di bawah menemukan siklus jika ada, jadi keduanya juga praktis untuk menguji siklus.

Contoh

Ambil panah A → C, B → C, B → D, C → E, dan D → E. Algoritma Kahn menghitung panah masuk: A dan B tidak punya, jadi A lebih dulu, lalu B. Menghapus panah B membebaskan C dan D, yang menyusul, lalu E: urutannya A, B, C, D, E. Metode DFS mengunjungi A, lalu C, lalu E; E selesai lebih dulu, lalu C, lalu A, masing-masing masuk ke depan. Lalu ia mengunjungi B dan D, yang selesai di depan mereka: urutannya B, D, A, C, E. Kedua urutan benar.

Kahn atau DFS?

Algoritma Kahn, yang diterbitkan Arthur Kahn pada 1962, bekerja maju: ia selalu tahu tugas mana yang bebas dimulai sekarang, cocok untuk penjadwalan, dan bisa memilih di antara tugas bebas dengan aturan apa pun, misalnya urutan abjad. Metode DFS, yang dipopulerkan Robert Tarjan pada 1976, bekerja mundur dari ujung dan hanya butuh depth-first search. Keduanya butuh waktu yang tumbuh sebanding jumlah simpul ditambah sisi.

Robert Tarjan, yang bersama John Hopcroft pada 1972–73 menunjukkan bahwa pencarian dalam-dahulu menyelesaikan banyak masalah graf dalam waktu linear; mereka menerima Turing Award 1986 sebagian karena karya itu.
Robert Tarjan, yang bersama John Hopcroft pada 1972–73 menunjukkan bahwa pencarian dalam-dahulu menyelesaikan banyak masalah graf dalam waktu linear; mereka menerima Turing Award 1986 sebagian karena karya itu.

Kegunaan

Alat build seperti make mengompilasi file setelah file yang menjadi dependensinya. Manajer paket memasang pustaka menurut urutan dependensi. Spreadsheet menghitung ulang sebuah sel setelah sel-sel yang dipakai rumusnya. Universitas memeriksa apakah prasyarat mata kuliah bisa dipenuhi, kompiler mengurutkan instruksi, dan pipeline data menjalankan tiap langkah setelah masukannya siap. Perintah Unix tsort melakukan pengurutan topologis dengan sendirinya.

Jelajahi

Buka aplikasinya dan tekan Langkah. Panah menunjukkan simpul mana yang harus datang sebelum simpul mana. Dengan algoritma Kahn, angka di tiap simpul menghitung panah masuk yang tersisa, dan simpul bebas berwarna biru. Dengan metode DFS, simpul biru sedang dikunjungi dan simpul hijau sudah ditempatkan. Urutan bertambah di baris bawah graf. Centang Tambah siklus dan lihat kedua metode menemukan bahwa tidak ada urutan.

Pertanyaan yang sering diajukan

Apa arti topologis di sini?

Namanya berasal dari topologi, ilmu tentang bagaimana sesuatu terhubung, bukan bentuk persisnya. Urutannya hanya bergantung pada simpul mana yang dihubungkan panah, bukan di mana simpul itu digambar.

Bagaimana menemukan siklus ketika tidak ada urutan?

Metode DFS menunjukkannya langsung: sisi ke simpul yang masih dikunjungi, bersama jalur simpul yang sedang dikunjungi, adalah siklusnya. Algoritma Kahn hanya memberi tahu simpul mana yang macet; pencarian di antara simpul itu akan menemukan siklusnya.

Bisakah saya memilih urutan tertentu di antara yang sah?

Bisa. Dalam algoritma Kahn, ketika beberapa simpul bebas, pilih yang Anda sukai, misalnya label terkecil atau tugas paling mendesak. Memakai antrean prioritas memberi urutan yang paling awal menurut abjad.

Bagaimana pengurutan topologis dipakai untuk jalur terpendek?

Pada graf asiklik berarah, merelaksasi sisi tiap simpul menurut urutan topologis menemukan semua jalur terpendek dari satu awal dalam sekali jalan, bahkan dengan sisi negatif, lebih cepat daripada Dijkstra atau Bellman–Ford.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba pengurutan topologis