0-1 BFS dengan Deque
Jalur terpendek saat bobotnya 0 atau 1
0-1 BFS dengan Deque adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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.
Jenis Graf Khusus
Beberapa graf hanya memiliki bobot sisi 0 atau 1. Pada graf tersebut, Anda dapat mengungguli Dijkstra dengan trik yang lebih sederhana dan cepat.
Temui 0-1 BFS
0-1 BFS menemukan jalur terpendek pada graf berbobot 0/1 dalam waktu linear, tanpa tumpukan dan tanpa faktor log sama sekali.
Alat: Dek
Ganti tumpukan dengan dek, yaitu antrean yang dapat menerima dan mengambil elemen dari bagian depan maupun belakang.
from collections import deque
dq = deque([src])Gagasan Inti
Sisi berbobot 0 mempertahankan jarak yang sama, sedangkan sisi berbobot 1 menambahkan satu. Dek mempertahankan kedua kelompok tersebut dalam urutan yang benar.
Bagian Depan untuk Sisi Nol
Melewati sisi berbobot 0? Gunakan appendleft untuk menambahkan tetangga ke bagian depan agar tetangga tersebut diproses berikutnya, karena tidak menambah jarak.
dq.appendleft(v)Bagian Belakang untuk Sisi Satu
Melewati sisi berbobot 1? Gunakan append untuk menambahkan tetangga ke bagian belakang, karena tetangga tersebut berada satu lapisan lebih jauh dari sumber.
dq.append(v)Ambil dari Bagian Depan
Selalu gunakan popleft untuk mengambil simpul saat ini. Dengan begitu, dek tetap terurut berdasarkan jarak, seperti penelusuran BFS berlapis.
u = dq.popleft()Relaksasikan dengan Bobot
Relaksasikan setiap sisi: hitung jarak baru sebagai dist[u] ditambah bobot sisi, lalu masukkan ke bagian depan atau belakang sesuai bobot tersebut.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndMengapa Tetap Terurut
Dek menampung paling banyak dua jarak berbeda pada satu waktu. Invarian inilah yang membuat penempatan di bagian depan dan belakang dapat bekerja.
Kecepatan Linear
Karena tidak menggunakan tumpukan, 0-1 BFS berjalan dalam O(V + E), sehingga terasa lebih cepat daripada Dijkstra pada graf yang sama.
Kapan Menggunakannya
Gunakan algoritme ini ketika perpindahan gratis atau berbiaya satu, misalnya pada kisi yang beberapa langkahnya terhalang dan lainnya terbuka.
Pemeriksaan Singkat
Anda merelaksasikan tetangga melalui sisi berbobot 0. Di mana tetangga tersebut ditempatkan?
Rekapitulasi: 0-1 BFS
Dengan dek, masukkan sisi berbobot 0 ke bagian depan dan sisi berbobot 1 ke bagian belakang. Anda mendapatkan jalur terpendek dalam waktu O(V+E) yang sederhana. ⚡
Pertanyaan yang Sering Diajukan
Apakah pelajaran “0-1 BFS dengan Deque” gratis?
Ya — teks lengkap “0-1 BFS dengan Deque” 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 “0-1 BFS dengan Deque”?
Jalur terpendek saat bobotnya 0 atau 1 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 2 dari 4.
Berapa lama pelajaran “0-1 BFS dengan Deque” 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
- Dijkstra dengan Heap
- 0-1 BFS dengan Deque
- Bellman-Ford & Sisi Negatif
- Floyd-Warshall untuk Semua Pasangan