0Pricing
Competitive Programming Academy · Pelajaran

BFS untuk Jalur Terpendek Tanpa Bobot

Jarak berlapis dari sebuah sumber

BFS untuk Jalur Terpendek Tanpa Bobot adalah pelajaran Competitive Programming Academy 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang Dilakukan BFS

BFS menjelajahi graf dalam lingkaran: pertama simpul awal, lalu semua simpul yang berjarak satu langkah, kemudian dua langkah, dan seterusnya. 🌊

Mengapa Lingkaran Berarti Terpendek

Karena BFS menyelesaikan setiap lingkaran sebelum beralih ke lingkaran berikutnya, saat pertama kali mencapai sebuah simpul, jalur tanpa bobot ke simpul tersebut adalah jalur terpendek.

Antrean adalah Mesinnya

BFS menggunakan antrean: yang masuk pertama keluar pertama. Anda menambahkan tetangga baru di bagian belakang, lalu memproses bagian depan berikutnya.

from collections import deque
q = deque([start])

Melacak yang Sudah Dilihat

Simpan penanda status kunjungan agar Anda tidak pernah memasukkan simpul yang sama ke antrean dua kali. Ini membuat BFS tetap cepat dan berhingga.

visited = [False] * (n + 1)
visited[start] = True

Menyimpan Jarak

Sebuah larik jarak menyimpan lapisan setiap simpul. Simpul awal mendapat nilai 0; setiap tetangga berjarak satu lebih jauh daripada induknya.

dist = [-1] * (n + 1)
dist[start] = 0

Mengambil dari Bagian Depan

Pada setiap langkah, ambil simpul di bagian depan antrean. Simpul tersebut adalah simpul terdekat yang belum diproses, jadi tangani sekarang.

u = q.popleft()

Memperluas Tetangga

Untuk setiap tetangga u yang belum dikunjungi, tandai, atur jaraknya, lalu tambahkan ke bagian belakang antrean.

for v in adj[u]:
    if dist[v] == -1:
        dist[v] = dist[u] + 1
        q.append(v)

Perulangan Lengkap

Terus ambil dan perluas simpul selama antrean belum kosong. Saat antrean habis, Anda telah mengunjungi setiap simpul yang dapat dicapai.

while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

Menandai Saat Memasukkan ke Antrean

Atur status kunjungan tepat saat memasukkan simpul ke antrean, bukan saat mengambilnya. Penandaan yang terlambat memungkinkan duplikat masuk ke antrean.

Simpul yang Tak Terjangkau Tetap -1

Simpul mana pun yang masih memiliki jarak -1 setelah BFS berarti tidak dapat dicapai dari titik awal Anda. Jawaban itu juga memiliki makna.

BFS Bersifat Linear

BFS menyentuh setiap simpul dan sisi satu kali, sehingga berjalan dalam O(n + m). Ini dengan mudah memenuhi sebagian besar batas kompetisi.

Pemeriksaan Singkat

Mengapa BFS biasa menghasilkan jalur terpendek?

Ringkasan

Anda menjalankan BFS dengan antrean dan larik jarak: tandai saat memasukkan ke antrean, perluas tetangga, lalu baca jarak terpendek setelah selesai. 🎉

Pertanyaan yang Sering Diajukan

Apakah pelajaran “BFS untuk Jalur Terpendek Tanpa Bobot” gratis?

Ya — teks lengkap “BFS untuk Jalur Terpendek Tanpa Bobot” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “BFS untuk Jalur Terpendek Tanpa Bobot”?

Jarak berlapis dari sebuah sumber Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 “BFS untuk Jalur Terpendek Tanpa Bobot” 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 Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy 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

  1. Adjacency List dari Input
  2. BFS untuk Jalur Terpendek Tanpa Bobot
  3. DFS, Rekursi & Stack Iteratif
  4. Komponen Terhubung & Flood Fill
← Kembali ke Competitive Programming Academy