- Saat ini
- Dalam antrean
- Dikunjungi
- Jalur
Breadth-First Search (BFS)
Breadth-first search (pencarian melebar) menjelajahi graf per lingkaran: pertama semua simpul di sebelah awal, lalu semua simpul yang berjarak dua sisi, dan seterusnya. Caranya dengan antrean, pertama masuk, pertama keluar. Klik simpul untuk mulai dari sana, pilih tujuan jika mau, lalu jalankan pencarian langkah demi langkah untuk melihat antrean memanjang dan memendek, tiap simpul mendapat jaraknya, dan jalur terpendek muncul. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk mencari jalur terpendek ke sana. Angka di tiap simpul adalah jaraknya dari awal, dan baris di bawah graf adalah antrean. 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
- Klik simpul untuk menjadikannya awal. Untuk mencari jalur, ubah klik ke Tujuan lalu klik simpul lain.
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Perhatikan antrean di bawah graf dan jarak di tiap simpul. Graf baru membuat graf lain untuk dicoba.
Cara kerja breadth-first search
Masukkan simpul awal ke antrean dengan jarak 0. Lalu ulangi: ambil simpul di depan antrean dan lihat tiap tetangganya. Tetangga yang belum pernah dilihat mendapat jarak satu lebih besar dari simpul yang diambil, mengingat simpul itu sebagai jalan ia dicapai, lalu masuk ke belakang antrean. Tetangga yang sudah pernah dilihat dilewati. Saat antrean kosong, setiap simpul yang bisa dicapai sudah punya jarak.
Mengapa BFS menemukan jalur terpendek
Antrean mengeluarkan simpul sesuai urutan ditemukannya, dan simpul ditemukan lingkaran demi lingkaran: semua simpul berjarak 1 masuk antrean sebelum simpul berjarak 2 mana pun, dan seterusnya. Jadi saat pertama kali dicapai, sebuah simpul dicapai lewat jalur dengan sisi paling sedikit. Menelusuri simpul yang diingat dari tujuan kembali ke awal memberi jalur itu. Ini hanya menghitung sisi; jika panjang sisi berbeda-beda, diperlukan algoritma Dijkstra.
Pertanyaan yang sering diajukan
Apa itu breadth-first search?
Cara menjelajahi graf dari simpul awal dengan mengunjungi semua tetangganya dulu, lalu tetangga mereka, dan seterusnya, lingkaran demi lingkaran. BFS memakai antrean agar simpul tetap dalam urutan ditemukannya.
Apakah breadth-first search menemukan jalur terpendek?
Ya, jika setiap sisi bernilai sama: saat BFS pertama kali mencapai sebuah simpul, sisi yang dipakai paling sedikit. Untuk sisi dengan panjang berbeda, pakai algoritma Dijkstra.
Apa bedanya BFS dan DFS?
Breadth-first search memakai antrean dan menyebar merata, lingkaran demi lingkaran. Depth-first search memakai stack (atau rekursi) dan mengikuti satu jalur sedalam mungkin sebelum mundur. BFS menemukan jalur terpendek dalam jumlah sisi; DFS tidak, tetapi berguna untuk mencari siklus dan untuk topological sort.
Seberapa cepat breadth-first search?
BFS mengambil tiap simpul dari antrean sekali dan melihat tiap sisi dari kedua ujungnya, jadi kerjanya bertambah sesuai jumlah simpul ditambah jumlah sisi.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan dicari 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