Apa itu BFS?
BFS adalah algoritma yang digunakan untuk membuat grafik data atau mencari pohon atau struktur yang melintasi. Algoritme secara efisien mengunjungi dan menandai semua node kunci dalam grafik dengan cara yang akurat secara luas.
Algoritme ini memilih satu node (titik awal atau sumber) dalam grafik dan kemudian mengunjungi semua node yang berdekatan dengan node yang dipilih. Setelah algoritme mengunjungi dan menandai node awal, lalu algoritme bergerak menuju node terdekat yang belum dikunjungi dan menganalisisnya.
Setelah dikunjungi, semua node ditandai. Iterasi ini berlanjut hingga semua node dari grafik telah berhasil dikunjungi dan ditandai. Bentuk lengkap BFS adalah pencarian Breadth-first.
Dalam BSF Vs. Tutorial pohon biner DFS, Anda akan belajar:
- Apa itu BFS?
- Apa itu DFS?
- Contoh BFS
- Contoh DFS
- Perbedaan antara BFS dan DFS Binary Tree
- Aplikasi BFS
- Aplikasi DFS
Apa itu DFS?
DFS adalah algoritma untuk menemukan atau melintasi grafik atau pohon dalam arah kedalaman-lingkungan. Eksekusi algoritme dimulai pada node root dan menjelajahi setiap cabang sebelum melakukan backtracking. Ini menggunakan struktur data tumpukan untuk mengingat, untuk mendapatkan simpul berikutnya, dan untuk memulai pencarian, setiap kali jalan buntu muncul dalam iterasi apa pun. Bentuk lengkap DFS adalah pencarian Depth-first.
Contoh BFS
Dalam contoh DFS berikut, kami telah menggunakan graf yang memiliki 6 simpul.
Contoh BFS
Langkah 1)
Anda memiliki grafik tujuh angka mulai dari 0 - 6.
Langkah 2)
0 atau nol telah ditandai sebagai simpul akar.
Langkah 3)
0 dikunjungi, ditandai, dan dimasukkan ke dalam struktur data antrian.
Langkah 4)
Sisa 0 node yang berdekatan dan belum dikunjungi dikunjungi, ditandai, dan dimasukkan ke dalam antrian.
Langkah 5)
Iterasi traverse diulang sampai semua node dikunjungi.
Contoh DFS
Dalam contoh DFS berikut, kami telah menggunakan graf tak berarah yang memiliki 5 simpul.
Langkah 1)
Kita telah mulai dari simpul 0. Algoritma dimulai dengan meletakkannya di daftar yang dikunjungi dan secara bersamaan meletakkan semua simpul yang berdekatan dalam struktur data yang disebut tumpukan.
Langkah 2)
Anda akan mengunjungi elemen, yang berada di bagian atas tumpukan, misalnya, 1 dan pergi ke node yang berdekatan. Itu karena 0 telah dikunjungi. Oleh karena itu, kami mengunjungi simpul 2.
Langkah 3)
Simpul 2 memiliki simpul terdekat yang belum dikunjungi di 4. Oleh karena itu, kami menambahkan simpul itu ke dalam tumpukan dan mengunjunginya.
Langkah 4)
Terakhir, kita akan mengunjungi simpul terakhir 3, tidak ada simpul yang berdampingan yang belum dikunjungi. Kami telah menyelesaikan traversal grafik menggunakan algoritma DFS.
Perbedaan antara BFS dan DFS Binary Tree
| BFS | DFS |
| BFS menemukan jalur terpendek ke tujuan. | DFS pergi ke bagian bawah subtree, lalu backtrack. |
| Bentuk lengkap BFS adalah Breadth-First Search. | Bentuk lengkap DFS adalah Depth First Search. |
| Ini menggunakan antrian untuk melacak lokasi berikutnya untuk dikunjungi. | Ini menggunakan tumpukan untuk melacak lokasi berikutnya untuk dikunjungi. |
| BFS melintasi menurut tingkat pohon. | DFS melintasi menurut kedalaman pohon. |
| Ini diimplementasikan menggunakan daftar FIFO. | Ini diimplementasikan menggunakan daftar LIFO. |
| Ini membutuhkan lebih banyak memori dibandingkan dengan DFS. | Ini membutuhkan lebih sedikit memori dibandingkan dengan BFS. |
| Algoritma ini memberikan solusi jalur paling dangkal. | Algoritme ini tidak menjamin solusi jalur paling dangkal. |
| Tidak perlu mundur di BFS. | Ada kebutuhan untuk mundur di DFS. |
| Anda tidak akan pernah bisa terjebak ke dalam loop yang terbatas. | Anda bisa terjebak dalam loop tak terbatas. |
| Jika Anda tidak menemukan tujuan apa pun, Anda mungkin perlu memperluas banyak node sebelum solusi ditemukan. | Jika Anda tidak menemukan tujuan apa pun, kemunduran simpul daun dapat terjadi. |
Aplikasi BFS
Berikut, Aplikasi BFS:
Grafik Tidak Berbobot:
Algoritma BFS dapat dengan mudah membuat jalur terpendek dan pohon rentang minimum untuk mengunjungi semua simpul grafik dalam waktu sesingkat mungkin dengan akurasi tinggi.
Jaringan P2P:
BFS dapat diimplementasikan untuk menemukan semua node terdekat atau tetangga dalam jaringan peer to peer. Ini akan menemukan data yang dibutuhkan lebih cepat.
Perayap Web:
Mesin telusur atau perayap web dapat dengan mudah membuat beberapa tingkat indeks dengan menggunakan BFS. Implementasi BFS dimulai dari sumber, yaitu halaman web, dan kemudian mengunjungi semua link dari sumber tersebut.
Siaran Jaringan:
Paket yang disiarkan dipandu oleh algoritma BFS untuk menemukan dan menjangkau semua node yang memiliki alamatnya.
Aplikasi DFS
Berikut adalah aplikasi penting DFS:
Grafik Tertimbang:
Dalam grafik berbobot, traversal grafik DFS menghasilkan pohon jalur terpendek dan pohon rentang minimum.
Mendeteksi Siklus dalam Grafik:
Grafik memiliki siklus jika kita menemukan tepi belakang selama DFS. Oleh karena itu, kita harus menjalankan DFS untuk grafik dan memverifikasi tepi belakang.
Menemukan jalan:
Kita dapat mengkhususkan diri pada algoritma DFS untuk mencari jalur antara dua simpul.
Penyortiran Topologis:
Ini terutama digunakan untuk menjadwalkan pekerjaan dari dependensi yang diberikan di antara kelompok pekerjaan. Dalam ilmu komputer, digunakan dalam penjadwalan instruksi, serialisasi data, sintesis logika, menentukan urutan tugas kompilasi.
Mencari Komponen Grafik yang Sangat Terhubung:
Ini digunakan dalam grafik DFS ketika ada jalur dari masing-masing dan setiap simpul dalam grafik ke simpul lain yang tersisa.
Memecahkan Teka-teki dengan Hanya Satu Solusi:
Algoritme DFS dapat dengan mudah diadaptasi untuk mencari semua solusi pada labirin dengan memasukkan node pada jalur yang ada di set yang dikunjungi.
PERBEDAAN UTAMA:
- BFS menemukan jalur terpendek ke tujuan sedangkan DFS pergi ke bawah subpohon, lalu jalur mundur.
- Bentuk lengkap BFS adalah Breadth-First Search sedangkan bentuk lengkap DFS adalah Depth First Search.
- BFS menggunakan antrian untuk melacak lokasi kunjungan berikutnya. sedangkan DFS menggunakan tumpukan untuk melacak lokasi kunjungan berikutnya.
- BFS melintasi menurut tingkat pohon sedangkan DFS melintasi menurut kedalaman pohon.
- BFS diimplementasikan menggunakan daftar FIFO sedangkan DFS diimplementasikan menggunakan daftar LIFO.
- Di BFS, Anda tidak pernah bisa terjebak ke dalam loop terbatas sedangkan di DFS Anda dapat terjebak ke dalam loop tak terbatas.