Pengurutan Topologis dengan Algoritma Kahn
Mengurutkan tugas yang bergantung pada tugas lain
Pengurutan Topologis dengan Algoritma Kahn adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Pengertian Urutan Topologis
Urutan topologis mencantumkan setiap simpul dalam graf berarah sehingga setiap sisi mengarah dari posisi yang lebih awal ke posisi yang lebih akhir. Bayangkan tugas-tugas yang harus diselesaikan sebelum tugas yang bergantung padanya.
Hanya DAG yang Diizinkan
Metode ini hanya berlaku pada DAG, yaitu graf berarah tanpa siklus. Jika terdapat siklus, tidak ada urutan sah yang dapat memenuhi semua dependensi.
Gagasan Derajat Masuk
Algoritme Kahn mengandalkan derajat masuk: jumlah sisi yang mengarah ke sebuah simpul. Simpul dengan derajat masuk nol tidak memiliki dependensi yang belum terpenuhi.
Hitung Setiap Derajat Masuk
Pada lintasan pertama, telusuri semua sisi dan hitung berapa kali setiap simpul menjadi tujuan. Dengan demikian, Anda memperoleh derajat masuk setiap simpul.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Isi Antrean Simpul Siap
Setiap simpul dengan derajat masuk nol langsung siap diproses, jadi masukkan semuanya ke dalam antrean sebagai langkah awal.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Proses Satu Simpul
Ambil simpul yang siap dengan operasi pop, lalu append simpul tersebut ke urutan Anda. Simpul itu aman diproses karena tidak ada tugas tersisa yang bergantung padanya.
u = q.popleft()
order.append(u)Lepaskan Tetangganya
Untuk setiap tetangga, kurangi derajat masuknya satu. Ketika derajat masuk tetangga menjadi nol, tetangga itu siap diproses dan masuk ke antrean.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Ulangi hingga Kosong
Terus lakukan pop dan lepaskan tetangga hingga antrean kosong. Urutan bertambah satu simpul aman setiap kali, sampai semua simpul ditempatkan.
Deteksi Siklus Secara Gratis
Jika urutan akhir Anda memuat kurang dari n simpul, sebuah siklus menjebak simpul-simpul lainnya. Algoritme Kahn memberi Anda deteksi siklus tanpa biaya tambahan.
if len(order) < n:
print('cycle exists')Waktu Eksekusi
Setiap simpul dan sisi dikunjungi satu kali, sehingga algoritme Kahn berjalan dalam O(V + E). Algoritme ini dapat menangani graf dengan jutaan sisi.
Banyak Urutan yang Sah
Ketika beberapa simpul siap sekaligus, Anda dapat memilih salah satunya untuk diproses berikutnya. Karena itu, sebuah DAG sering memiliki banyak urutan topologis yang sah, bukan hanya satu.
Uji Cepat
Anda menyelesaikan algoritme Kahn, tetapi urutannya memiliki kurang dari n simpul. Apa artinya?
Rangkuman: Algoritme Kahn
Hitung derajat masuk, masukkan simpul bernilai nol ke antrean, lakukan pop pada sebuah simpul, kurangi derajat tetangganya, lalu ulangi. Itulah pengurutan topologis yang rapi dalam O(V+E). 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pengurutan Topologis dengan Algoritma Kahn” gratis?
Ya — teks lengkap “Pengurutan Topologis dengan Algoritma Kahn” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pengurutan Topologis dengan Algoritma Kahn”?
Mengurutkan tugas yang bergantung pada tugas lain Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Pengurutan Topologis dengan Algoritma Kahn” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pengurutan Topologis dengan Algoritma Kahn
- Mendeteksi Siklus dalam Graf Berarah
- Komponen Terhubung Kuat
- Jembatan & Titik Artikulasi