0-1 BFS dengan Deque
Laluan terpendek apabila pemberatnya 0 atau 1.
0-1 BFS dengan Deque ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Jenis Graf yang Istimewa
Sesetengah graf hanya mempunyai berat sisi 0 atau 1. Untuk graf ini, Anda boleh mengatasi Dijkstra dengan helah yang lebih ringkas dan pantas.
Kenali 0-1 BFS
0-1 BFS mencari laluan terpendek pada graf yang berat sisinya 0/1 dalam masa linear, tanpa timbunan dan tanpa faktor log sama sekali.
Alat: Dek
Gantikan timbunan dengan dek, iaitu baris gilir yang membolehkan Anda memasukkan dan mengeluarkan item dari bahagian depan serta belakang.
from collections import deque
dq = deque([src])Pemerhatian Teras
Sisi berat 0 mengekalkan jarak yang sama, manakala sisi berat 1 menambah satu. Dek mengekalkan kedua-dua kumpulan dalam susunan yang betul.
Bahagian Depan untuk Sisi Sifar
Melintasi sisi 0? Gunakan appendleft pada jiran supaya jiran itu diproses seterusnya, kerana tiada jarak tambahan dikenakan.
dq.appendleft(v)Bahagian Belakang untuk Sisi Satu
Melintasi sisi 1? Gunakan append pada jiran untuk memasukkannya ke bahagian belakang, kerana kedudukannya satu lapisan lebih jauh dari sumber.
dq.append(v)Keluarkan dari Bahagian Depan
Sentiasa gunakan popleft pada nod semasa. Ini memastikan dek tersusun mengikut jarak, seperti BFS berlapis.
u = dq.popleft()Longgarkan Mengikut Berat
Longgarkan setiap sisi: jarak baharu ialah dist[u] ditambah berat sisi, kemudian masukkan nod ke bahagian depan atau belakang mengikut berat itu.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndMengapa Susunannya Kekal
Dek menyimpan paling banyak dua jarak berbeza pada satu-satu masa. Invarian itulah sebab peletakan di bahagian depan dan belakang berfungsi.
Kelajuan Linear
Oleh sebab tiada timbunan digunakan, 0-1 BFS berjalan dalam O(V + E), dan ketara lebih pantas daripada Dijkstra pada graf yang sama.
Bila Patut Menggunakannya
Gunakannya apabila pergerakan adalah percuma atau berkos satu, seperti pada grid yang mempunyai langkah terhalang dan langkah terbuka.
Semakan Pantas
Anda melonggarkan jiran melalui sisi yang beratnya 0. Ke manakah jiran itu perlu dimasukkan?
Imbas Kembali: 0-1 BFS
Dengan dek, masukkan sisi 0 ke bahagian depan dan sisi 1 ke bahagian belakang. Anda memperoleh laluan terpendek dalam masa O(V+E) yang kemas. ⚡
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “0-1 BFS dengan Deque” percuma?
Ya — teks penuh “0-1 BFS dengan Deque” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “0-1 BFS dengan Deque”?
Laluan terpendek apabila pemberatnya 0 atau 1. Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “0-1 BFS dengan Deque” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Dijkstra dengan Timbunan
- 0-1 BFS dengan Deque
- Bellman-Ford dan Sisi Negatif
- Floyd-Warshall Semua Pasangan