- Saat ini
- Bebas atau sedang dikunjungi
- Ditempatkan
- Siklus
Pengurutan topologis
Kaus kaki sebelum sepatu, fondasi sebelum dinding, satu mata kuliah sebelum mata kuliah yang membutuhkannya. Pengurutan topologis menyusun simpul graf bersisi satu arah dalam satu baris tempat setiap sisi mengarah ke depan. Pilih algoritma Kahn atau metode DFS dan jalankan langkah demi langkah untuk melihat urutan bertambah, lalu tambahkan siklus untuk melihat mengapa urutan menjadi mustahil. Tekan Putar untuk melihat urutan bertambah, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Setiap sisi satu arah, seperti ditunjukkan panahnya: anggap saja artinya "ini sebelum itu". Pilih metodenya: algoritma Kahn menempatkan simpul tanpa sisi masuk lebih dulu, dan angka di tiap simpul adalah jumlah sisi masuk yang masih dimilikinya; metode DFS menempatkan tiap simpul di depan setelah semua yang ada sesudahnya ditempatkan. Baris di bawah graf adalah urutan sejauh ini. Centang Tambah siklus untuk melihat cara tiap metode menemukannya. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih algoritma Kahn atau metode DFS.
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
- Perhatikan urutan bertambah di bawah graf. Centang Tambah siklus untuk melihat cara tiap metode menemukannya.
Algoritma Kahn
Hitung, untuk setiap simpul, berapa sisi yang menunjuk ke sana. Simpul tanpa sisi masuk tidak bergantung pada apa pun, jadi bisa ditaruh lebih dulu. Tempatkan simpul seperti itu, lalu hapus sisi keluarnya: simpul yang ditunjuk kini punya satu sisi masuk lebih sedikit, dan sebagian bisa mencapai nol dan menjadi bebas. Terus tempatkan simpul bebas sampai tidak ada lagi. Jika ada simpul yang tidak pernah bebas, mereka saling menunggu dalam sebuah siklus, dan tidak ada urutan topologis.
Metode DFS
Jalankan depth-first search dari setiap simpul yang belum dikunjungi. Sebuah simpul selesai ketika semua yang bisa dicapai darinya sudah selesai, jadi semua yang harus datang sesudahnya sudah ditempatkan. Taruh setiap simpul yang selesai di depan urutan, dan urutannya akan benar. Jika pencarian mengikuti sisi ke simpul yang masih sedang ditelusuri, sisi itu menutup sebuah siklus, dan sekali lagi tidak ada urutan.
Pertanyaan yang sering diajukan
Apa itu pengurutan topologis?
Urutan simpul-simpul graf berarah di mana setiap sisi berjalan dari simpul yang lebih awal ke simpul yang lebih akhir. Jika sisi berarti "harus datang sebelum", ini adalah urutan untuk mengerjakan semua tugas.
Kapan urutan topologis ada?
Tepat ketika graf tidak punya siklus berarah: graf itu adalah graf asiklik berarah, atau DAG. Dengan siklus, setiap simpul di dalamnya harus datang sebelum dirinya sendiri.
Apakah urutan topologis unik?
Biasanya tidak. Setiap kali dua simpul tidak terhubung oleh rantai sisi, salah satunya boleh lebih dulu, jadi sebuah graf bisa punya banyak urutan yang sah. Algoritma Kahn dan metode DFS sering memberi urutan yang berbeda.
Seberapa cepat pengurutan topologis?
Kedua metode melihat setiap simpul dan setiap sisi sebanyak jumlah kali yang tetap, jadi kerjanya tumbuh sebanding jumlah simpul ditambah jumlah sisi.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan diurutkan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor